RoaringBitmap：智能压缩版 Bitmap 的原理与取舍

[ Computer ]

如果你已经了解了 Bitmap（位图） 和 Bloom Filter（布隆过滤器），那么 RoaringBitmap 可以理解为：

一种“智能压缩版 Bitmap”，既保持了 Bitmap 查询快的优点，又解决了 Bitmap 太占内存的问题。

很多大数据系统（Spark、ClickHouse、Druid、Pinot、Lucene、Elasticsearch 等）都在使用它。(GitHub)

一、Bitmap 为什么不够好？

先回顾 Bitmap。

假设我们要表示下面这些数字：

{1,2,5,100}

Bitmap 会直接开到最大值：

0 1 2 3 4 5 6 ... 99 100

0 1 1 0 0 1 0 ...  0   1

优点：

  • 查询 O(1)
  • 并集、交集直接位运算
  • CPU 极快

例如

A:
00110100

B:
10100100

AND
00100100

OR
10110100

几乎就是 CPU 一条指令。

但是问题来了

假设：

只有三个数字

1
1000000
999999999

Bitmap 必须开到：

999999999 bit
≈125MB

实际上只保存了：

3 个数字

却浪费了：

999999996 个 bit

这就是 Bitmap 最大的问题：

数据越稀疏，越浪费内存。

二、RoaringBitmap 解决什么问题？

RoaringBitmap 的目标就是：

稀疏时像数组一样存，稠密时像 Bitmap 一样存。

一句话：

自动选择最省空间的数据结构。 (GitHub)

三、RoaringBitmap 的核心思想

RoaringBitmap 并没有维护一个超级大的 Bitmap。

它首先把整数按照 高 16 位 分组。

例如：

32 bit 整数

xxxxxxxx xxxxxxxx | yyyyyyyy yyyyyyyy
     高16位             低16位

例如数字：

100
1000
65535
70000
90000

分组后：

Container0（高16位=0）

100
1000
65535


Container1（高16位=1）

70000
90000

也就是说：

整个 32 位整数空间，被拆成很多：

65536 个小块

每块负责：

2^16 = 65536 个数字

论文称之为：

Container（容器）

整个 Bitmap 就变成：

Root

 ├── Container0
 ├── Container1
 ├── Container2
 ├── ...

而不是：

一个超级大的 Bitmap

这样可以避免为空白区域分配内存。(roaringbitmap.readthedocs.io)

四、Container 有三种存储方式

这也是 RoaringBitmap 最厉害的地方。

它不会固定采用 Bitmap。

而是：

根据当前 Container 的数据密度自动选择。

第一种：Array Container（稀疏）

假设这一块只有：

100
200
500

不用 Bitmap。

直接数组：

[
100,
200,
500
]

查询：

二分查找

空间非常小。

一般用于：

元素 <=4096

(roaringbitmap.readthedocs.io)

第二种：Bitmap Container（稠密）

如果：

这一块里面

30000 个数字

数组就太长了。

直接 Bitmap：

65536 bit

≈8KB

例如：

000101011001...

查询：

bitmap[offset]

O(1)

位运算：

AND

OR

XOR

CPU 极快。

一般：

元素 >4096

自动切换。(roaringbitmap.readthedocs.io)

第三种：Run Container（连续）

后来又加入了一种：

Run Container

例如：

100
101
102
103
104
105

Bitmap：

111111

数组：

100
101
102
103
104
105

其实最好的表示就是：

(start=100,length=6)

即可。

也就是：

100~105

存储：

[
(start,length)
]

连续数据压缩率极高。(阿里云)

五、什么时候切换？

例如：

开始：

Container0

100

300

500

只有三个元素。

使用：

Array Container

后来：

不断 add()

变成：

5000 个元素

RoaringBitmap 自动转换：

Bitmap Container

如果：

后来删除很多：

只剩几十个

又自动退回：

Array Container

所以：

用户完全不用关心底层结构。

六、为什么速度仍然很快？

例如：

A
B

都有：

Container0
Container1
Container5

做交集：

Container0

Bitmap AND Bitmap

↓

结果

不用扫描整个几十亿 Bitmap。

只处理：

存在数据的 Container

因此：

空 Container

直接跳过。

速度非常快。(arXiv)

七、举一个查询例子

例如：

用户标签：

喜欢篮球：

1
2
5
8
10

用户标签：

喜欢足球：

2
5
6
9

Bitmap：

篮球

010011010

足球

001011001

交集：

AND

↓

2
5

RoaringBitmap：

底层也是：

Container

↓

Bitmap

↓

AND

速度几乎一样。

但是：

如果用户 ID：

1
100000
99999999

Bitmap：

需要几千万 bit

RoaringBitmap：

只有三个数字

几个数组即可

八、为什么比 Bitmap 更省内存？

假设：

最大 ID：

10 亿

但是：

实际只有：

1000 个 ID

Bitmap：

10亿 bit

≈125MB

RoaringBitmap：

Root

↓

几个 Container

↓

Array

↓

1000 个 uint16

可能：

几 KB

甚至：

几十 KB

即可。

九、实际应用场景

RoaringBitmap 非常适合表示整数集合，尤其是需要频繁做集合运算的场景：

场景 用法
搜索引擎 文档 ID 集合，快速求交集（多个关键词同时命中）
推荐系统 用户标签、兴趣集合
广告系统 人群圈选（年龄 + 地区 + 兴趣）
数据仓库 Bitmap Index
ClickHouse 去重、Bitmap 聚合
Apache Druid 用户分析
Apache Spark 高效集合操作
Redis 模块 大规模用户 ID 管理

这些系统使用 RoaringBitmap 的主要原因是：内存占用低，同时交集、并集等集合运算仍然非常快。(GitHub)

十、RoaringBitmap 与其他数据结构对比

数据结构 查询 内存 去重 交集/并集 适用场景
HashSet O(1) 较高 ✅ 较慢 通用集合
Bitmap O(1) 很高（稀疏数据） ✅ 极快 ID 连续、数据密集
Bloom Filter O(k) 极低 ❌（可能误判） 不擅长 判断“可能存在”
RoaringBitmap 接近 O(1) 低 ✅ 极快 稀疏 + 稠密混合的大规模整数集合

十一、可以把它理解成什么？

如果只记住一句话，我建议记住下面这张思维图：

                     Bitmap
                (一个巨大位图)
                      │
      ┌───────────────┴───────────────┐
      │                               │
   数据稠密                        数据稀疏
      │                               │
   查询很快                     内存浪费严重
      └───────────────┬───────────────┘
                      │
                RoaringBitmap
                      │
        把数据切成很多 2^16 的小块(Container)
                      │
      ┌───────────────┼───────────────┐
      │               │               │
 Array Container  Bitmap Container  Run Container
  (稀疏数组)        (稠密位图)        (连续区间)
      │               │               │
      └───────────────┴───────────────┘
                      │
       自动选择最优存储 + 保持高速集合运算

因此，RoaringBitmap 可以理解为 Bitmap 的“自适应升级版”：它将整数空间划分为多个容器，每个容器根据数据分布自动选择数组、位图或区间编码等表示方式，从而在保持 Bitmap 高速查询和集合运算能力的同时，大幅降低稀疏数据场景下的内存消耗。这一设计也是它成为现代搜索引擎、分析数据库和大数据系统中广泛采用的压缩位图格式的核心原因。(arXiv)

补充：RoaringBitmap 的局限与取舍

有，而且 RoaringBitmap 并不是 Bitmap 的全方位升级版，它是在空间、查询、集合运算之间做的平衡。

很多人看到它以后会觉得：

“既然比 Bitmap 省内存，又一样快，那是不是全面替代 Bitmap 了？”

实际上不是。

1. 删除和插入并非真正 O(1)

先看 Bitmap。

假设：

bitmap[100] = 1

插入：

bitmap[100] = 1

删除：

bitmap[100] = 0

仅修改一个 bit。

时间：

O(1)

RoaringBitmap 不一样。

例如：

Container0

[100,200,300]

属于：

ArrayContainer

删除：

remove(200)

变成：

[100,300]

数组需要移动元素。

时间：

O(n)

更麻烦的是：

4097 个元素

删除后：

4096 个元素

可能触发：

BitmapContainer
↓
ArrayContainer

容器转换。

这时候需要：

重新构建容器

会有额外开销。

2. 随机写入不如 Bitmap

Bitmap：

set(999999999)

直接定位：

offset

修改 bit 即可。

RoaringBitmap：

需要先：

找到 Container

高16位
↓
定位Container
↓
低16位
↓
更新

过程变成：

Root查找
+
Container查找
+
更新

虽然仍然很快，

但已经不是 Bitmap 那种：

一个数组下标

的极致性能。

3. 容器切换存在额外成本

RoaringBitmap 最厉害的地方：

Array
↔
Bitmap
↔
Run

自动切换。

但切换本身是有代价的。

例如：

ArrayContainer

里面：

4096个元素

继续插入：

4097个元素

会发生：

Array
↓
Bitmap

需要：

遍历4096个元素
重新生成Bitmap

一次性成本较高。

例如：

4095
4096
4095
4096
...

来回震荡。

会导致：

频繁转换容器

性能下降。

因此很多实现会做：

hysteresis（滞后阈值）

避免反复切换。

4. 不适合大量连续写入

例如日志系统：

1
2
3
4
5
...
100000000

不断追加。

这种场景：

HashSet

或者：

普通 Bitmap

反而可能更简单。

因为：

RoaringBitmap

需要维护：

Container
索引
转换
压缩

额外元数据。

5. 极度稠密时反而不占优势

假设：

0 ~ 10亿

几乎全部存在。

例如：

95%

都存在。

普通 Bitmap：

10亿 bit

≈125MB

固定。

RoaringBitmap：

除了 BitmapContainer 之外还有：

Root
Container索引
Cardinality统计

等元数据。

因此：

极度稠密

场景下：

RoaringBitmap

未必更省。

甚至可能稍大。

6. 只适用于整数集合

RoaringBitmap 本质上存的是：

uint32

或者：

uint64

集合。

例如：

用户ID
文档ID
商品ID
订单ID

非常适合。

但是：

用户名
邮箱
URL

不能直接存。

需要：

字符串
↓
映射
↓
整数ID
↓
RoaringBitmap

多一层转换。

7. TopN、排序能力弱

例如：

100
5
8
1000
7

RoaringBitmap 关心的是：

是否存在

而不是：

插入顺序

或者：

权重

因此：

Top100
最大值
最小值
排行榜

这类操作，

远不如：

B+Tree
SkipList
Heap

合适。

8. 序列化比 Bitmap 更复杂

Bitmap：

直接 dump 内存

即可。

RoaringBitmap：

需要保存：

Root
Container类型
Array数据
Bitmap数据
Run数据

结构类似：

{
  containerType,
  cardinality,
  payload
}

序列化和反序列化逻辑更复杂。

9. CPU Cache 命中率不如 Bitmap

这是很多人忽略的。

Bitmap：

连续内存

111001010...

CPU 非常喜欢。

Cache 命中率极高。

RoaringBitmap：

Root
 ↓
Container
 ↓
Array

存在：

指针跳转

或者：

多段内存

访问模式没那么连续。

因此：

纯查询性能

理论上永远打不过：

连续Bitmap

只是差距通常不大。

10. 最重要的一条：它优化的是“稀疏+稠密混合场景”

RoaringBitmap 最适合：

最大ID非常大

实际数据不多

例如：

用户ID：
1~100亿

实际在线用户：
500万

这种情况：

Bitmap

会爆内存。

HashSet

集合运算慢。

RoaringBitmap：

内存接近 HashSet

交集速度接近 Bitmap

这就是它成功的原因。

级总结

可以记住下面这个表：

数据结构 插入 删除 查询 交集/并集 内存
HashSet O(1) O(1) O(1) 较慢 高
Bitmap O(1) O(1) O(1) 极快 最大
RoaringBitmap 近 O(1) 近 O(1) 近 O(1) 极快 很低

RoaringBitmap 的核心取舍可以概括为：

牺牲一点点：
    插入性能
    删除性能
    实现复杂度

换来：
    数十倍~数百倍内存节省
    接近 Bitmap 的集合运算速度

所以在搜索引擎、广告人群圈选、OLAP 分析、推荐系统中，它几乎成为了 Bitmap 的事实标准；但在需要高频随机更新、极度稠密数据、或者需要排序/范围索引的场景中，普通 Bitmap、HashSet、B+Tree 等结构仍然更合适。