Roaring Bitmap：如何把大量整数集合压缩起来，还能快速求交集？

如果要表示一个整数集合，例如“哪些用户参加过活动”“哪些文档包含某个词”，位图是一种简单高效的办法：用第 n 位表示整数 n 是否存在。可当整数范围特别大、实际成员却很稀疏时，直接分配一整张位图会浪费空间。Roaring Bitmap（Roaring 位图）通过把整数按高位分块，并为每块选择合适的容器，兼顾压缩与快速集合运算。

一个常见设计会把 32 位整数拆成高 16 位和低 16 位。高位用来定位块，低位值则存放在该块的容器里。若某个块只有少数成员，就用紧凑的有序数组；成员密度升高时，可切换到固定大小的位图容器。这样稀疏区域不必承担密集位图的空间成本，而密集区域还能利用机器字并行执行按位运算。

这类结构的优势不只是压缩。对两个 Roaring 集合做交集、并集、差集时，可以按块匹配容器，依据容器类型选用合适算法。例如数组与数组可以合并比较，位图与位图可以做机器字级 AND，混合类型也可使用专门路径。许多分析查询因此能直接在压缩后的结构上运行，避免先展开成完整大位图。

容器之间可以采用不同表示，是 Roaring 与单一编码方案的重要区别。它仍是精确集合：如果某整数在集合里，查询就返回存在；若不在，就返回不存在。Bloom Filter 则是概率型成员测试，空间更省，但可能出现“误报存在”。两者解决的问题不同：Roaring 适合需要精确成员关系与集合运算，Bloom Filter 适合用很小空间先排除大多数不存在的元素。

不过，“压缩”不意味着任何数据上都更小。若集合分布不理想，元数据、容器切换和序列化格式都会影响实际占用；频繁随机更新也可能带来维护开销。评估时要看整数范围、密度分布、读写比例以及需要执行的运算，而不是只比较理论上的每个元素几位。

可以把 Roaring 想成一座按街区管理的档案馆：先按邮区找到一个小柜，再根据柜子里材料多寡，使用薄薄的名册或完整索引卡墙。查询和合并都能在柜子内部处理，不必把整座城市的空地址全部列出来。它的核心价值是为整数集合提供一种自适应、可精确计算的表示方式，常见于搜索引擎、数据库、分析系统和日志处理。

来源：Chambi 等：Better bitmap performance with Roaring bitmaps