位图bitmap的改进版：Roaring Bitmap

原创

cuiyi

发布于 2023-01-09 13:59:58

2.2K0

发布于 2023-01-09 13:59:58

文章被收录于专栏：未知之路-技术杂记未知之路-技术杂记

定义

咆哮位图，是一种压缩位图，是对bitmap的改进，除了使用bitmap存储数据，还使用了array等数据结构，以达到压缩的目的。

和bitmap的区别

比bitmap更节省内存空间：

把32位分为2^16个容器，只为用到的容器分配空间，解决了稀疏数据浪费空间的问题。
每个容器根据数据的稠密情况使用array或bitmap数据结构，节省了每个容器占用的内存空间。

比bitmap性能更高：

因为不会开辟大量不用的内存，参与计算的内存块比较少，提升计算速度。
使用有序数组保存容器，在进行逻辑运算时（与或非）基本只需要计算相同索引的容器。

作用

解决bitmap统计大数据尤其是稀疏数据浪费内存空间的问题；
解决bitmap内存空间无法收缩的问题：存储容器的array和ArrayContainer都是数组，支持清空和移除元素，但其空间释按照语言自身的GC机制处理。

实现原理

使用拆分模式，把2^32位拆分为2^16个容器，每个容器最多保存2^16个元素。

把要统计的数字拆分位高16位和低16位，高16位用作容器的索引、用于定位数字在哪个容器；低16位用作容器内元素的索引、用作定位数字在容器内的位置。

容器保存在一个有序数组中，在需要时被创建，不需要时不会创建。该数组名为highLowContainer。

容器有3种类型：ArrayContainer、BitmapContainer和RunContainer，根据要统计的数字的数量和数字的连续性自动选择合适的容器。

RunContainer：使用Run-Length Encoding方式压缩存储的元素，对连续数据的压缩效果特别好，但如果数据比较散列，反而会更占用空间，长度没有限制；

ArrayContainer：元素为short类型的有序数组，存储散列数据时，效果比较好；

BitmapContainer：使用bitmap存储数据，存储大量数据时，效果比较好；

容器的使用及容器之间的转换

元素数量不超过4096时，使用ArrayContainer，超过4096后使用BitmapContainer。同时，根据元素的连续性，把ArrayContainer或BitmapContaner转换为RunContainer。

ArrayContainer和BitmapContainer的选择：

元素数量不超过4096时，使用ArrayContainer；超过4096后使用BitmapContainer。

ArrayContainer使用2字节的short类型来存储每个元素，4096*2byte=8kb；BitmapContainer是定长2^16个bit，即bitmap固定大小8k。

所以当元素数量小于4096时，ArrayContainer占用的空间小于BitmapContainer；元素数量大于4096时，ArrayContainer占用的空间大于BitmapContainer；元素数量等于4096时，两者占用的空间相同，都是8kb。

ArrayContainer保证元素的有序性，使用二分查找进行读写，时间复杂度是O(logn)；BitmapContainer读写时间复杂度是O(1)或O(n)。

创建：

如果是单个元素，直接使用ArrayContainer；

如果是多个连续元素，比较ArrayContainer和RunContainer占用空间的大小，选择占用空间小的；

转换：

如果当前是ArrayContainer：

元素数量大于4096时，直接在添加元素时转换为BitmapContainer；

运行runOptimize()时，比较ArrayContainer和RunContainer占用的空间，选择占用空间小的；

如果当前是BitmapContainer：

元素被删除，元素数量小于等于4096时，直接转换为ArrayContainer；

运行runOptimize()时，比较bitmapContainer和RunContainer占用的空间，选择占用空间小的；

如果当前是RunContainer：

只有运行runOptimize()时，根据当前的元素数量，同时比较三种容器占用的空间，选择占用空间小的；

ArrayContainer是同步转换，即在每个写操作中检测阈值，如果达到阈值则直接做对应的转换，先移动旧元素再添加新元素。
Roaring Bitmap不是一种常驻进程的服务，不存在后台调用的情况；在各种容器的读写操作中也没有调用runOptimize()函数。所以runOptimize()就是一个常规函数，是手动调用执行的。一旦要调用这个函数，必须有一个基本的调用策略，而不是随机的或做一次性的调用，否则可能不但达不到优化效果，还会使性能更低下。