bitmap 在某个长度之后会占用内存比array小,利用这个特性,可以将数据的存储压缩成bitmap存储.
背景
当我们有多个数字的数组,我们可以用多种方式描述一个数字.
array = [1 , 2 , 3 ,5,7] (1)方案1 , 直接使用数组
假设每个数字是一个Uint32 ,也就是4字节的数字.
那么上面例子(1) 中占用的字节数:5*4 = 20 字节 , 如果我们要存越大的数据需要的内存越多.我们占用的内存是线性的
memory = array.size() * 4优点:
- 有多少内存就可以存多少数据 缺点:
- 占用内存是线性的
方案2 , 直接使用4个字节的的位图
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
更进一步,我们要存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相关阅读: