本文共 3797 字,大约阅读时间需要 12 分钟。
本文大量内容系转载自以下文章,有删改,并参考其他文档资料加入了一些内容:
BitMap(位图索引)被广泛用于数据库和搜索引擎中,通过利用位级并行,它们可以显著加快查询速度。但是,位图索引会占用大量的内存,而且还存在稀疏性问题,因此我们会更喜欢压缩位图索引。 Roaring Bitmaps 就是一种十分优秀的压缩位图索引,后文统称 RBM。
压缩位图索引有很多种,比如基于 RLE(Run-Length
Encoding,运行长度编码)的WAH (Word Aligned Hybrid Compression Scheme) 和 Concise (Compressed ‘n’ Composable Integer Set)。相比较前者, RBM 能提供更优秀的压缩性能和更快的查询效率。RBM 的用途和 Bitmap 很差不多(比如说索引),只是说从性能、空间利用率各方面更优秀了。目前 RBM 已经在很多成熟的开源大数据平台中使用,简单列几个作为参考:
原理的话先直接上一段论文的原文,两三段基本把整个 RBM 的设计思想给讲清楚了。不想看英文了可以直接跳过看后面的中文总结。
We partition the range of 32-bit indexes ([0; n)) into chunks of 2^16 integers sharing the same 16 most significant digits. We use specialized containers to store their 16 least significant bits.
When a chunk contains no more than 4096 integers, we use a sorted array of packed 16-bit integers. When there are more than 4096 integers, we use a 2^16
-bit bitmap. Thus, we have two types of containers: an array container for sparse chunks and a bitmap container for dense chunks. The 4096 threshold insures that at the level of the containers, each integer uses no more than 16 bits: we either use 2^16
bits for more than 4096 integers, using less than 16 bits/integer, or else we use exactly 16 bits/integer.
The containers are stored in a dynamic array with the shared 16 most-significant bits: this serves as a first-level index. The array keeps the containers sorted by the 16 most-significant bits.We expect this first-level index to be typically small: when n = 1 000 000, it contains at most 16 entries. Thus it should often remain in the CPU cache. The containers themselves should never use much more than 8 kB.
RBM 的主要思想并不复杂,简单来讲,有如下三条:
2^16
)和低 16 位(k mod 2^16
),取高 16 位找到对应的桶,然后在低 16 位存放在相应的 Container 中;如下图,就是官网给出的一个例子,三个容器分别代表了三个数据集,container内存的低16位:
array container
2^16
, 2^16
+ 100),高16位为0x01。数量不超过4096,所以使用array container
2*2^16
, 3*2^16
),高16为0x02。数量超过4096,所以使用bitmap container
看完前面的还不知道在说什么?没关系,举个栗子说明就好了。现在我们要将 821697800 这个 32 bit 的整数插入 RBM 中,整个算法流程是这样的:
RBM 的基本原理就这些,基于这种设计原理会有一些额外的操作要提一下。
请注意上文提到的一句话:
若一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值。
先解释一下为什么这里用的 4096 这个阈值?因为一个 Integer 的低 16 位是 2Byte,因此对应到 Arrary Container 中的话就是 2Byte * 4096 = 8KB;同样,对于 Bitmap Container 来讲,2^16
个 bit 也相当于是 8KB。
论文中解释的4096的意义是使用RBM每个integer使用不超过16bit:
2^16
位的BitMap,每个integer占有的bit显然是小于16bit的然后,基于前面提到的两种 Container,在两个 Container 之间的 Union (bitwise OR,即按位或) 或者 Intersection (bitwise AND,即按位与) 操作又会出现下面三种场景:
好了,RBM 的大致原理就这些,不深入也没有简单代码的实现。仅能做一个入门的参考。
本文是参考论文,该论文中提到的是 Bitmap 和 Array 两种容器,算是包含了 RBM 的主要思想。然后,在另一篇论文《Consistently faster and smaller compressed bitmaps with Roaring》中会对 RBM 有更深入的探讨,并引入了一种新的容器: Run,感兴趣的童鞋可以深入看一看。