RoaringBitmap原理分析

Bitmap是一种非常重要的数据结构,其有着优秀的压缩能力,并且对于常见的去重,过滤,差集并集等有着良好的性能表现。本文介绍一种特殊的Bitmap–RoaringBitmap。

前言

Bitmap是基于位存储数据结构,相对数组可以节省很大内存空间,举例来说,假如要存放1000000以内的数字,如果用int数组,那么需要用4*1000000字节,用Bitmap,只需要用1000000/8字节。性能可以提高32倍。
但是,如果数字再大,Bitmap也会占用很大空间,因此很多基于压缩思路的Bitmap出现。而RoaringBitmap是一种兼顾了压缩和性能的Bitmap。

RoaringBitmap

RoaringBitmap将int数字的高16位作为索引,正好short是16位长度。因此索引采用short数组存储,每次需要二分查找索引。而低16位则是作为数据,存储到其他容器,RoaringBitmap根据存储的大小,分为3个容器,ArrayContainer,BitmapContainer,RunContainer

ArrayContainer

当数据量低于4096时,采用ArrayContainer存储,这个容器也比较简单,核心是一个short数组,我们知道short是2字节,因此存储的数字大小不能超过65536。将65536范围内的数字散布在4096个槽位里,因此这个数组里数组的分布是稀疏的。每次寻找数据也只需二分查找即可。
为什么要用4096作为边界呢,这就要结合下面的BitmapContainer容器一起看了。

BitmapContainer

当存储的数据4096个数字后,RoaringBitmap采用Bitmap来存储所有的数字,包括之前那4096个数字。这一次的数量限制是2^16,也就是65536。这个数字很容易计算出,由于存储在container的数据只有32位中的低16位,因此作为Bitmap,只需要提供2^16个bit即可。
在这个容器中,核心是一个long数组,为了2^16个bit,这个数组分配了1024个空间,也是正好满足了2^16个bit。
这里可以看出,BitmapContainer占用空间的上限也同样是8*1024=8KB,因此ArrayContainer的长度超过4096转换成BitmapContainer可以节省更多的空间,这也解释了为什么ArrayContainer的上限是4096了。

RunContainer

RunContainer是基于一种Run Length Encoding压缩算法的容器,其压缩原理是对于连续的数字只记录初始数字以及连续的长度,比如有一串数字 2,3,4,5,6 那么经过压缩后便只剩下2,5。从压缩原理我们也可以看出,这种算法对于数据的紧凑程度非常敏感,连续程度越高压缩率也越高。
在这个容器中,核心是一个short数组,数组存储了压缩后的初始数字以及连续的长度。这意味着压缩后占用最小的空间就是两个short,4个字节。而最大空间则为永远不连续的场景65536/222也就是128KB。存储空间分配可以直接参考代码中的注释

1
2
3
4
5
if you have the values 11,12,13,14,15, you store that as 11,4 where 4 means that beyond 11
// itself, there are
// 4 contiguous values that follows.
// Other example: e.g., 1, 10, 20,0, 31,2 would be a concise representation of 1, 2, ..., 11, 20,
// 31, 32, 33

那么这个容器在什么情况下使用呢,RoaringBitmap提供了一个优化的接口,对比存储到BitmapContainer和RunContainer占用的空间大小,选小的那个。

总结

从上面的分析可以看出,RoaringBitmap将int类型的数据分为两个部分存储,高16位单独存储在short数组,低16位根据数据量存储在不同的容器。当然所有操作的意义在于使用更少的空间获取更好的性能,这里的性能包括了常见的去重,过滤,差集并集等操作。在官方论文里性能倒是比其他压缩类型的Bitmap好很多,参考论文

ulysses wechat
订阅+