存储算法 #06：Roaring Bitmap

Roaring Bitmap 是一种高效的压缩整数集合数据结构，根据数据密度自动选择最优的存储容器，在稀疏和密集场景下都能保持极低的内存占用与高效的集合运算。ClickHouse、Druid、Lucene/ES、Apache Spark 等大数据系统广泛使用。

相关文章：Bloom Filter · Copy-on-Write（COW）

目录

核心思想

问题：存储一个大整数集合（如 10 亿个文档 ID），需要高效支持：

• 插入 / 删除 / 查询
• 集合运算（交集 AND、并集 OR、差集）
• 低内存占用

方案对比（存储 10 亿整数中的 100 万个）：

HashSet<Integer>：
  每个 int 占 ~40 字节（对象头 + 哈希桶）
  100 万个 → 约 40 MB

普通位图（BitSet）：
  10 亿 bit = 约 120 MB（无论实际有多少元素）
  稀疏时极度浪费

Roaring Bitmap：
  根据密度自动选择容器
  100 万个稀疏整数 → 约 2 MB（20 倍压缩）
  集合运算比 HashSet 快 1000 倍

分块设计

将 32 位整数空间 [0, 2³²) 按高 16 位分为 65536 个桶（chunk）：

整数 x = 高16位（chunk ID）| 低16位（在该 chunk 内的位置）

例：x = 131073 = 0x00020001
  高16位 = 0x0002 = chunk 2
  低16位 = 0x0001 = 在 chunk 2 内的位置 1

Roaring Bitmap 结构：
  Map<uint16, Container>  // chunk ID → 容器
  
  只有包含元素的 chunk 才创建容器，空 chunk 不占内存
  → 天然稀疏友好

三种容器

每个 chunk 最多包含 65536 个元素（低 16 位的所有可能值），根据元素数量自动选择：

Array 容器（稀疏：< 4096 个元素）

存储：uint16[] 排序数组

示例：chunk 包含元素 {1, 5, 100, 999}
      存储：[1, 5, 100, 999]（uint16，2字节/个）

空间：2 × n 字节（n = 元素数量）
      最大：2 × 4096 = 8 KB

查找：二分查找，O(log n)
插入：找到位置后移动元素，O(n)
集合运算：双指针归并，O(n1 + n2)

适合：稀疏集合

Bitmap 容器（密集：≥ 4096 个元素）

存储：固定 8 KB 的位图（65536 bit = 8192 byte）

示例：chunk 包含 50000 个元素
      位图中对应位置置 1

空间：固定 8 KB（不随元素数量变化）
查找：O(1)（直接访问对应 bit）
插入：O(1)
集合运算：SIMD 位运算，极快

适合：密集集合（元素数 ≥ 4096，8KB 固定开销值得）

为什么以 4096 为分界：

Array 容器空间 = 2 × n 字节
Bitmap 容器空间 = 8 KB = 8192 字节

当 2n = 8192 → n = 4096
  n < 4096：Array 更省空间
  n ≥ 4096：Bitmap 更省空间（且速度更快）

→ 4096 是两种容器的空间等价点，用于自动切换

Run 容器（连续区间：RLE 压缩）

存储：连续区间的起始值 + 长度列表（uint16 对）

示例：chunk 包含 {1,2,3,4,5, 100,101,102, 200}
      区间：[1,5], [100,102], [200,200]
      存储：[(1,5), (100,3), (200,1)]  → 6 个 uint16 = 12 字节

空间：4 × r 字节（r = 区间数量）
      当 r < n/2（元素数/2）时比 Array 省空间
      当 r < 16384 时比 Bitmap 省空间

适合：大量连续 ID（如按时间序列的文档 ID）

触发时机：调用 runOptimize() 后，自动判断是否转为 Run 容器

集合运算

AND（交集）

Array ∩ Array：双指针，O(min(n1,n2))
Array ∩ Bitmap：遍历 Array，查 Bitmap 中是否置位，O(n_array)
Bitmap ∩ Bitmap：64 位 AND 运算，8192/8 = 1024 次操作（SIMD 可 256 次）

跨 chunk 处理：
  对两个 Roaring Bitmap 取 AND：
  只对两者都有的 chunk ID 做运算
  某方没有的 chunk → 结果为空，跳过

OR（并集）

Array ∪ Array：合并两个有序数组，O(n1+n2)
Bitmap ∪ Bitmap：64 位 OR 运算，极快
Array ∪ Bitmap：遍历 Array，在 Bitmap 中置位，O(n_array)

跨 chunk 处理：
  某方没有的 chunk → 直接复制另一方的容器

基数统计（Cardinality）

Array 容器：直接返回 array.size()
Bitmap 容器：统计置位数（popcount 指令，硬件加速）
Run 容器：累加所有区间的长度

与其他方案对比

实测（100万个随机 int32）：
  HashSet：约 40 MB
  BitSet：约 500 MB（4G 范围）
  Roaring Bitmap：约 2 MB

AND 运算（两个各含 1000 万元素的集合）：
  HashSet：约 1000ms
  Roaring Bitmap：约 5ms（200 倍）

异常场景

极端稀疏（10 亿中只有 1 个元素）

只有 1 个 chunk，1 个 Array 容器，存 1 个 uint16
占用：chunk ID（2B）+ Array 容器（2B）= 4 字节
非常高效 ✅

极端密集（全集，10 亿个元素全有）

65536 个 chunk，每个 chunk 都是满的 Bitmap 容器（8KB）
总占用：65536 × 8 KB = 512 MB

对比普通 BitSet（2³² bit = 512 MB）：相同大小
说明 Roaring Bitmap 密集场景不比普通 BitSet 差

频繁增删导致容器类型频繁切换

问题：元素数在 4096 附近反复增删，导致 Array↔Bitmap 频繁转换
     每次转换需要重新分配内存和复制数据

优化：
  增加迟滞区间（hysteresis）：
    超过 4096 转为 Bitmap，需降到 3500 以下才转回 Array
    避免边界处的频繁切换

工程应用

ES 中的使用示例：

// 查询 status=1 AND category=手机 的文档
// ES 内部：
//   status=1 的文档 ID 集合 → Roaring Bitmap A
//   category=手机 的文档 ID 集合 → Roaring Bitmap B
//   结果 = A AND B（Roaring Bitmap 交集）→ 文档 ID 列表
//   直接定位文档，无需全表扫描

参考资料

• Chambi, S. et al. (2016). Better bitmap performance with Roaring bitmaps
• Roaring Bitmap 官网：https://roaringbitmap.org/
• RoaringBitmap Java 库：https://github.com/RoaringBitmap/RoaringBitmap