位图(Bitmap/Bitset)

定义

位图(Bitmap,又称 Bitset、位向量)用一段连续内存中的每一个比特表示一个编号对应的元素是否存在:第 i 位为 1 表示元素 i 在集合中。它是整数集合最紧凑的精确表示之一,1 亿个编号仅需约 12 MB。

原理

置位、清位、测试通过位运算完成;并集、交集、差集直接对底层机器字做按位或、与、异或,每条指令并行处理 64 个元素;统计基数可用 popcount 指令。对稀疏数据,压缩位图(如 RLE 系的 WAH、EWAH 以及分容器混合的 Roaring Bitmap)能大幅降低空间。

应用

数据库的位图索引适合低基数列的多条件过滤;Elasticsearch、Lucene、ClickHouse、Druid 等广泛使用 Roaring Bitmap 做倒排求交;Redis 提供 SETBIT/BITCOUNT 支撑签到、活跃标记等场景;操作系统用位图管理空闲页与 inode;布隆过滤器底层也是位数组。

优缺点

优点是空间紧凑、集合运算吞吐极高、缓存友好;缺点是只适合整数键、稀疏大值域需压缩变体,且不能直接存放附加数据。