咆哮位图（Roaring Bitmap）

咆哮位图（Roaring Bitmap）是一种高效的压缩位图数据结构,用于紧凑地存储整数集合并快速执行交集、并集等集合运算。它由 Daniel Lemire 等人推动发展,广泛应用于数据库与搜索引擎的位图索引。

概述

传统位图用每一位表示一个整数是否存在,对连续密集的数据非常紧凑,但当数据稀疏地分布在很大取值范围时,会浪费大量空间;而用有序数组存储稀疏集合虽省空间,却在密集时又不划算。咆哮位图的思路是分而治之:把整数的高位作为分块索引,每一块内部再根据实际密度自适应地选择最合适的存储容器。

核心特点

• 高低位分块:将整数按高位切分成多个块,每块负责一段固定范围的取值。
• 多种容器:块内数据稀疏时用有序数组存储成员,密集时用位图存储,极其连续时用区间游程压缩,按需切换。
• 快速集合运算:交并差等运算按块对齐后逐块进行,并针对不同容器组合采用专门优化,速度快于逐位处理。
• 压缩与性能兼顾:它不像某些压缩位图那样必须解压才能随机访问,能在压缩态下高效查询和运算。

应用场景

咆哮位图被大量数据系统采用,如搜索引擎用它存储倒排索引中的文档编号集合并做布尔检索,分析型数据库用它加速过滤与聚合,大数据框架用它做去重与集合运算。许多知名的检索与 OLAP 系统都内置了这一结构。

常见问题

问:它相比普通位图好在哪?答:普通位图在数据稀疏且取值范围大时会浪费空间,咆哮位图通过分块和自适应容器,在稀疏与密集分布下都能保持较好的空间与运算效率。

问:它适合存储什么样的数据?答:最适合整数标识符的集合,例如文档编号、用户编号,尤其是需要频繁做集合交并运算的场景。