数据库位图索引与B树索引在不同数据分布下的效率

数据库位图索引在低基数（重复值多）的数据分布下效率远超B树索引，而B树索引在高基数（重复值少）且需要范围查询的场景下更具优势。这不是一句空话，而是由两种索引的底层数据结构和算法逻辑决定的。位图索引用0和1的位向量表示某个值是否存在，天然适合"性别""状态码"这类只有几个取值的列；B树索引通过平衡树结构维护有序键值，适合"身份证号""时间戳"这类几乎每个值都不同的列。选错索引类型，查询性能可能差几十倍甚至上百倍。

要真正理解两者在不同数据分布下的效率差异，必须从底层原理入手，而不是停留在"位图快还是B树快"这种笼统的说法上。下面我会从数据结构、适用场景、性能瓶颈、实际测试四个维度，把这个问题彻底讲透。

位图索引的核心是一个位向量（Bitmap）。假设一张表有100万行，某列"性别"只有"男"和"女"两个值，那么位图索引会为"男"维护一个100万位的向量，第i位为1表示第i行是"男"，为0则不是。同样为"女"也维护一个。当你查询"性别=男"时，数据库直接扫描这个位图，找到所有为1的位置，返回对应行。如果还要加条件"年龄>30"，就对两个位图做AND运算，硬件层面的位运算极快。

B树索引的核心是一棵平衡的多路搜索树。每个节点存储多个键值和指向子节点的指针，叶子节点按顺序链接。查询时从根节点开始二分查找，逐步定位到叶子节点。对于等值查询，时间复杂度是O(log n)；对于范围查询，找到起点后沿叶子节点链表顺序扫描即可。B树的优势在于它天然支持排序和范围操作，而且对高基数列的存储效率很高。

两者的根本区别在于：位图索引把"值的存在性"压缩成了位，适合值少行多的情况；B树索引把"值本身"组织成树，适合值多且需要有序访问的情况。这个结构差异直接决定了它们在不同数据分布下的表现天差地别。

低基数（Low Cardinality）指的是一列中不同值的数量远小于总行数。比如"订单状态"列只有"待支付、已支付、已发货、已完成、已取消"5个值，而表有500万行数据。这种情况下，位图索引的优势非常明显。

首先是存储效率。5个值各对应一个500万位的位图，总共约3MB（500万位÷8÷1024÷1024≈0.6MB每个，5个约3MB）。而B树索引需要为每一行存储键值+行指针，500万行至少几十MB。存储小意味着I/O少，缓存命中率高。

其次是查询速度。查询"状态=已支付"时，位图索引直接返回一个位向量，数据库根据位向量中为1的位置批量取行。如果还要加"地区=北京"，只需对"已支付"和"北京"两个位图做AND运算，CPU的位运算指令一条指令处理64位，500万位只需约7.8万次运算，微秒级完成。而B树索引需要先在"状态"索引上找到"已支付"对应的行ID集合，再到"地区"索引上找到"北京"对应的行ID集合，最后做集合交集，过程复杂得多。

用一段伪代码来说明位图索引的查询逻辑：

// 位图索引查询示例
Bitmap status_paid = getBitmap("status", "已支付");   // 500万位向量
Bitmap region_beijing = getBitmap("region", "北京");   // 500万位向量
Bitmap result = bitwise_and(status_paid, region_beijing); // 位与运算
List<RowID> rows = getRowsByBitmap(result);            // 根据位图取行

这个过程的关键在于位运算的并行性和极低的CPU开销。在低基数场景下，位图索引几乎是碾压级的存在。

高基数（High Cardinality）指的是一列中不同值的数量接近甚至等于总行数。比如"用户ID""邮箱地址""身份证号"这类列，几乎每行都不同。这种情况下，位图索引会彻底崩盘。

原因很简单：如果有100万行，每行的"用户ID"都不同，位图索引就需要为每个值维护一个100万位的位图。100万个值×100万位=10^12位≈125GB，这还只是一个列的索引！不仅存储爆炸，而且每个位图里只有一个1，其余全是0，做位运算毫无意义——你相当于在一个几乎全是0的向量里找那唯一的1。

B树索引在高基数场景下表现优异。100万个不同的键值，B树的高度通常只有3到4层（假设每个节点存100个键），查询任何一个值只需3到4次磁盘I/O（如果根节点在内存中则更少）。而且B树天然支持范围查询，比如"用户ID在10000到20000之间"，从起点开始顺序扫描叶子节点即可，效率极高。位图索引做这种范围查询几乎不可能，因为你需要把范围内每个值的位图全部OR起来，值越多运算量越大。

所以结论很明确：高基数列，老老实实用B树索引，不要碰位图。

现实中很多列既不是极低基数也不是极高基数，比如"城市"列可能有几百个值，"产品类别"可能有几十个值。这种中等基数（Medium Cardinality）的情况，两种索引都可以用，但各有优劣。

位图索引在中等基数下仍然有不错的表现，尤其是多条件组合查询。比如"城市=上海 AND 产品类别=电子产品 AND 价格>100"，三个位图AND运算后再与价格范围的结果交集，整体效率通常优于B树索引的多次回表。但要注意，位图索引有一个致命弱点：不适合高并发写入。因为每次插入或更新一行，都需要修改多个位图的对应位，如果是锁粒度粗的实现，会产生严重的锁竞争。

B树索引在中等基数下的写入性能更好，因为只需要在树中插入或更新一个键值。但多条件查询时，B树需要多次索引查找+回表+集合运算，步骤多、开销大。

我的建议是：如果这张表以查询为主、写入少，且经常有多条件组合查询，优先考虑位图索引；如果写入频繁，或者经常需要范围查询和排序，B树索引更稳妥。很多现代数据库（如Oracle、PostgreSQL的扩展）支持两种索引共存，可以根据实际查询模式混合使用。

下面用一个具体场景来说明。假设有一张1000万行的订单表，包含"支付方式"（5个值）、"订单金额"（高基数）、"创建时间"（高基数但常做范围查询）三列。

场景一：查询"支付方式=微信支付 AND 金额>500"。位图索引对"支付方式"建索引，快速定位微信支付的行，再过滤金额>500的行。B树索引对"支付方式"建索引，找到微信支付的行ID后回表取金额再过滤。位图索引在这个场景下通常快3到10倍，因为避免了大量随机回表。

场景二：查询"创建时间在2024-01-01到2024-06-30之间"。这是典型的范围查询，位图索引几乎无法高效处理（除非把时间离散化成几十个桶，但精度损失大）。B树索引直接从起点扫描到终点，效率极高。这个场景B树完胜。

场景三：查询"支付方式=支付宝"。单条件等值查询，低基数列。位图索引直接返回位向量，B树索引走树查找。两者差距不大，但位图索引在数据量大时略优，因为不需要回表就能知道哪些行匹配（如果配合位图索引的压缩存储和批量取行机制）。

选型的核心原则总结如下：

第一，先看基数。基数低于总行数的1%甚至更低，位图索引优先考虑；基数高于10%，B树索引更安全；中间地带看查询模式。

第二，看查询类型。多条件AND查询，位图索引有天然优势；范围查询、排序、前缀匹配，B树索引是唯一选择。

第三，看写入频率。高频写入的表慎用位图索引，锁竞争和维护成本高；读多写少的表位图索引可以大胆用。

第四，看数据库支持。不是所有数据库都原生支持位图索引。Oracle、PostgreSQL（通过扩展或GIN索引的变体）、SQL Server（列存储索引中有类似机制）支持较好；MySQL的InnoDB引擎原生不支持位图索引，需要用其他方式模拟或借助第三方工具。

很多人以为位图索引就是"快"，但忽略了一个关键问题：位图索引的压缩。原始位图如果不压缩，存储量虽然比B树小，但也不是无限小。现代数据库会对位图做WAH（Word-Aligned Hybrid）压缩或RLE（Run-Length Encoding）压缩，把连续的0或1压缩成更短的表示。压缩后的位图做位运算需要先解压，这会增加CPU开销。所以在某些极端情况下，压缩位图的查询速度可能不如预期。

另一个容易忽略的点是位图索引的更新代价。假设你有一个位图索引覆盖"性别"列，当你把某行的性别从"男"改成"女"时，需要同时修改"男"和"女"两个位图的对应位。如果这行被频繁更新，位图的维护成本会累积。而B树索引只需更新一个节点（或少数几个节点），代价小得多。

还有一个进阶思路：对于中等基数列，可以考虑"分区位图索引"。把数据按某个维度分区，每个分区内基数降低，再对每个分区建位图索引。这样既利用了位图的查询优势，又控制了单个位图的大小。Oracle的Bitmap Join Index就是这种思路的产物，它把多个表的连接结果预计算成位图，加速复杂查询。

最后要强调的是，索引选择不是一次性的决定。随着数据量增长和查询模式变化，今天合适的索引明天可能不合适。建议定期用数据库的执行计划分析工具（如EXPLAIN、EXPLAIN ANALYZE）检查索引使用情况，根据实际运行数据做调整。不要迷信任何一种索引类型，数据分布和业务场景才是最终的裁判。

总的来说，位图索引和B树索引不是谁替代谁的关系，而是各有各的战场。低基数+多条件查询，位图索引是利器；高基数+范围查询+高并发写入，B树索引是基石。理解数据分布的特征，匹配正确的索引类型，才能让数据库查询效率最大化。这不是理论问题，是每个DBA和后端开发者都必须掌握的实战技能。