Roaring Bitmap

Roaring Bitmap是一种专门为大规模整数集合设计的高性能压缩位图数据结构。它的核心目标是同时解决传统位图和压缩位图的两个致命痛点传统位图Fixed Bitset查询快O(1)但空间浪费严重。例如要存储文档 ID{1, 1000000}仍需分配 100万位的内存。简单压缩位图如 RLE / Elias-Fano空间省但随机访问慢。查找第 N 个元素或判断某个 ID 是否存在往往需要 O(N) 的线性扫描解压。Roaring Bitmap 通过分块 自适应编码完美兼顾了两者既支持 O(1) 级别的随机访问又能根据数据密度自动选择最优压缩策略。这正是 LuceneIndexedDISI直接借鉴它的原因。 核心原理65536 分块 三种容器容器类型触发条件存储方式特点Array Container基数 4096排序的short[]数组稀疏时比位图更省空间二分查找 O(log n)Bitmap Container基数 ≥ 4096固定 8KB 位图 (65536 bits)稠密时 O(1) 随机访问交集/并集可用 SIMD 加速Run Container存在长连续区间(start, length)对的数组对连续段极其高效适合有序递增数据️ 全局索引结构除了桶内容器Roaring Bitmap 还维护一个顶层目录一个排序的高 16 位键数组short[] keys对应的容器指针/偏移数组这使得定位任意整数的过程为在keys中二分查找高 16 位 → 找到对应容器在容器内用低 16 位做 O(1) 或 O(log n) 查找整体查找复杂度为O(log n container_op)远优于线性扫描。 为什么 Lucene IndexedDISI 要借鉴它回到你引用的那段注释IndexedDISI的需求是在磁盘上存储稀疏文档 ID 列表支持advance(target)快速跳转支持index()返回当前文档的 ordinal即这是第几个匹配文档空间开销可控这与 Roaring Bitmap 的设计目标高度吻合Roaring Bitmap 特性IndexedDISI 对应实现65536 分块相同的 block sizeArray / Bitmap / Run 三态SPARSE / DENSE / ALL 三态去掉了 Run因为 DocID 通常不够连续顶层 keys 目录块查找表int-pair 数组存累计 index 字节 offsetBitmap Container 内的 rank/selectDENSE 块的 Rank 结构byte-pair 子块计数容器按需加载MMap 只读取目标 block避免全量加载IndexedDISI本质上是Roaring Bitmap 的磁盘化、只读化、ordinal-aware 特化版本。它去掉了写入和修改能力换来了更极致的磁盘布局优化比如把 Rank 结构放在 DENSE 块头部保证局部性把查找表放在文件尾部便于一次性读入内存。 超越 Lucene 的影响Roaring Bitmap 已成为现代数据基础设施的事实标准数据库Apache Druid、ClickHouse、StarRocks 用它做倒排索引和物化视图OLAPApache Spark、Flink 用它做 Shuffle 阶段的 ID 传递搜索引擎Elasticsearch、Solr、Vespa 底层都依赖它Java 生态官方库org.roaringbitmap:RoaringBitmap被广泛使用理解 Roaring Bitmap就理解了现代系统中如何在有限内存/磁盘中高效表达和操作大规模离散集合这一通用范式。而IndexedDISI正是这一范式在搜索场景下最精致的工程实现之一。