Skip to main content

One post tagged with "roaring bitmap"

View All Tags

roaring bitmap

· 3 min read

bitmap 在某个长度之后会占用内存比array小,利用这个特性,可以将数据的存储压缩成bitmap存储.

背景​

当我们有多个数字的数组,我们可以用多种方式描述一个数字.

array = [1 , 2 , 3 ,5,7]     (1)

方案1 , 直接使用数组​

假设每个数字是一个Uint32 ,也就是4字节的数字.

那么上面例子(1) 中占用的字节数:5*4 = 20 字节 , 如果我们要存越大的数据需要的内存越多.我们占用的内存是线性的

memory = array.size() * 4

优点:

  • 有多少内存就可以存多少数据 缺点:
  • 占用内存是线性的

方案2 , 直接使用4个字节的的位图​

bitmap

uint32 num = 0 ; 
num |= num << 1  ;
num |= num << 2   ;
num |= num << 3  ;
num |= num << 5 ;
num |= num << 7 ;

那么可以存多少个数字呢? 4*8 = 32 也就是可以存32个数字

优点:

  • 占用内存是O(1) , 存储数量不随着数据变大而变大

缺点

  • 用4个字节的位图最多可以描述一个32个Uint的数字

roaring bitmap​

roaring bitmap

更进一步,我们要存2^32个数​

  • 只使用bitmap 如果要用bitmap来存,我们要用 2^32 / 8 = 2^29 byte = 256m

  • 只使用array 需要的内存： 4*array.length byte

bitmap和array的区别： bitmap会固定占用的内存，array则是动态占用内存。 上面的例子（存储4字节长度的数字数组），bitmap会固定占用256m，而array则动态长度。在数组比较小的时候，使用array比较好，在数组长度比较大的时候，则使用bitmap比较好。

核心公式： number_length * n * 8 = 2^n 这里解释一下公式长度： number_length 描述的是一个数字的字节长度，比如要存储的是uint32 , 则number_length = 4 , 如果要存储uint64 ,则number_length = 8

4 *n*8 = 2^n 的解是16

所以用16个字节来描述一个联合体：{bitmap , array} , 当数组数量小于16的时候使用array 存储，当数量大于等于16的时候使用bitmap描述

roaring bitmap 容器的运算​

参考相关代码：

CRoaring/include/roaring/containers/containers.h

相关阅读: