Roaring Bitmap

定义

Roaring Bitmap 是 Daniel Lemire 等人于 2014 年提出的压缩位图格式:把 32 位整数按高 16 位分成至多 65536 个块(chunk),每块根据元素密度自适应选择容器——稀疏时用有序 short 数组(array container),稠密时用 8 KB 位图(bitmap container),连续区间多时用游程编码(run container)。

原理

查询先按高 16 位二分定位容器,再在容器内查找;两个 Roaring Bitmap 的并交差运算逐容器配对处理,不同容器组合有专门优化的算法,并大量使用 SIMD 指令。相比 WAH/EWAH 等游程压缩位图,Roaring 支持随机访问而无需解压整个序列。

应用

Roaring Bitmap 已成为事实标准:Lucene/Elasticsearch 用它缓存过滤器结果,ClickHouse、Druid、Kylin、Pilosa、Spark、InfluxDB 等系统用它做倒排索引求交、用户画像圈选(标签与人群包运算)与去重统计,多语言均有官方实现。

优缺点

优点是空间与速度兼得、运算可并行、格式跨语言互通;缺点是仅适用于整数集合,极度随机稀疏的数据压缩收益有限。