位图索引

定义

位图索引(Bitmap Index)为被索引列的每个不同取值维护一个位图(bitmap),位图的第 n 位表示第 n 行是否等于该值。例如"性别"列会生成两个位图,每个位图的长度等于表的行数。

原理

多条件查询可转化为位图间的按位 AND、OR、NOT 运算,CPU 处理位运算极快,组合任意多个条件的代价都很低,最终位图直接给出满足条件的行号集合。位图通常配合压缩编码(如 WAH、Roaring Bitmap)存储,低基数时体积远小于 B 树。

适用场景

位图索引适合取值种类少(低基数)的列,如性别、状态、地区,以及以复杂多维过滤为主的分析型(OLAP)负载,Oracle 的 bitmap index 是经典实现,ClickHouse、Druid 等也大量使用位图技术。

局限

高基数列会产生海量位图;更新一行需要修改多个位图并引发锁竞争,因此位图索引不适合高并发写入的 OLTP 系统。