您现在的位置是:首页 > 编程

Roaringbitmap 算法介绍

编程作者:chenli日期:2021-12-10 14:28:27点击:249

Roaringbitmap是什么?

Roaringbitmap属于是位图的一个进化,即压缩位图,不过在roaringbitmap中不只包含bitmap这一种数据结构,而是包涵了多种存储的方式,以此来达到压缩位图的目的,具体的存储方式下面会讲到。

那么roaringbitmap有什么用呢?

在实际的业务当中我们可以使用roaringbitmap来存储用户的属性标签,增删改查这些属性标签等,以及根据这些存储的用户的标签通过并集,交集等方法来筛选出特定的用户。

举个例子.如下图有一个存储用户性别的roaringbitmap_sex,以及一个存储喜好唱歌的roaringbitmap_like,现在我们需要找出:性别为男并且喜欢唱歌的用户,那么我们便可以求roaringbitmap_sex和roaringbitmap_like的交集即可,结果中二进制为1的位便是我们需要找的用户。

roaringbitmap工作原理

  1. 首先,将 32bit int(无符号的)类型数据 划分为 2^16 个桶(即使用数据的前16位二进制作为桶的编号),每个桶有一个Container(可以理解为容器也可以理解为这个桶,容器和桶在这里可以理解为一个东西,只是说法不一样而已) 来存放一个数值的低16位。
  2. 在存储和查询数值时,将数值 k 划分为高 16 位和低 16 位,取高 16 位值找到对应的桶,然后在将低 16 位值存放在相应的 Container 中。这样说可能比较抽象不易理解,下面以一个例子来帮助大家理解。

比如我们要将31这个数放进roarigbitmap中,它的16进制为:0000001F,前16位为0000,后16为001F。所以我们先需要根据前16位的值:0,找到它对应的通的编号为0,然后根据后16位的值:31,确定这个值应该放到桶中的哪一个位置,如下图所示。

roaringbitmap中的四种小桶

在上面我们提到了大桶里装了许多的小桶(其实说container(容器)更标准),那么现在我们就来看一看小桶究竟是什么,在roaringbitmap中共有4种小桶:arraycontainer(数组容器),bitmapcontainer(位图容器),runcontainer(行程步长容器),sharedcontainer(共享容器)。下面我们分别来介绍一下这4种容器。

1. Array Container

Array Container 是 Roaring Bitmap 初始化默认的 Container。Array Container 适合存放稀疏的数据,其内部数据结构是一个有序的 Short 数组。数组初始容量为 4,数组最大容量为 4096,所以 Array Container 是动态变化的,当容量不够时,需要扩容,并且当超过最大容量 4096 时,就会转换为 Bitmap Container。由于数组是有序的,存储和查询时都可以通过二分查找快速定位其在数组中的位置。

后面会讲解为什么超过最大容量 4096 时变更 Container 类型。

下面我们具体看一下数据如何被存储的,例如,0x00020032(十进制131122)放入一个 RBM 的过程如下图所示:

0x00020032 的前 16 位是 0002,找到对应的桶 0x0002。在桶对应的 Container 中存储低 16 位,因为 Container 元素个数不足 4096,因此是一个 Array Container。低 16 位为 0032(十进制为50), 在 Array Container 中二分查找找到相应的位置插入即可(如上图50的位置)。

相较于原始的 Bitmap 需要占用 16K (131122/8/1024) 内存来存储这个数,而这种存储实际只占用了4B(桶中占 2 B,Container中占 2 B,不考虑数组的初始容量)。

2. Bitmap Container

第二种 Container 是 Bitmap Container。它的数据结构是一个 Long 数组,数组容量恒定为 1024,和上文的 Array Container 不同,Array Container 是一个动态扩容的数组。Bitmap Container 不用像 Array Container 那样需要二分查找定位位置,而是可以直接通过下标直接寻址。

由于每个 Bitmap Container 需要处理低 16 位数据,也就是需要使用 Bitmap 来存储需要 8192 B(2^16/8), 而一个 Long 值占 8 个 B,所以数组大小为 1024。因此一个 Bitmap Container 固定占用内存 8 KB。

下面我们具体看一下数据如何被存储的,例如,0xFFFF3ACB(十进制4294916811)放入一个 RBM 的过程如下图所示:


0xFFFF3ACB 的前 16 位是 FFFF,找到对应的桶 0xFFFF。在桶对应的 Container 中存储低 16 位,因为 Container 中元素个数已经超过 4096,因此是一个 Bitmap Container。低 16 位为 3ACB(十进制为15051), 因此在 Bitmap Container 中通过下标直接寻址找到相应的位置,将其置为 1 即可(如上图15051的位置)。

可以看到元素个数达到 4096 之前,Array Container 占用的空间比 Bitmap Container 的少,当 Array Container 中元素到 4096 个时,正好等于 Bitmap Container 所占用的 8 KB。当元素个数超过了 4096 时,Array Container 所占用的空间还是继续线性增长,而 Bitmap Container 的内存空间并不会增长,始终还是占用 8 KB,与数据量无关。所以当 Array Container 超过最大容量 4096 会转换为 Bitmap Container。

3. runcontainer Container

这是一种利用步长来压缩空间的方法,我们举个例子:

比如连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被 压缩为两个二元组 11, 4, 27, 2 表示:11后面紧跟着4个连续递增的值,27后面跟着2个连续递增的值,那么原先16个字节的空间,现在只需要8个字节,是不是节省了很多空间呢。不过这种容器不常用,所以在使用的时候需要我们自行调用相关的转换函数来判断是不是需要将arraycontiner,或bitmapcontainer转换为runcontainer

4. sharedcontainer Container

这种容器它本身是不存储数据的,只是用它来指向arraycontainer,bitmapcontainer或runcontainer,就好比指针的作用一样,这个指针可以被多个对象拥有,但是指针所指针的实质东西是被这多个对象所共享的。在我们进行roaringbitmap之间的拷贝的时候,有时并不需要将一个container拷贝多份,那么我们就可以使用sharedcontainer来指向实际的container,然后把sharedcontainer赋给多个roaringbitmap对象持有,这个roaringbitmap对象就可以根据sharedcontainer找到真正存储数据的container,这可以省去不必要的空间浪费。

这些container之间的关系可以用下面这幅图来表示:

文章评论