为什么数据库索引偏爱 B+ 树

刚入行时，我对索引的理解只有一句话："给查询慢的字段加个索引就好了。"后来接手一个老项目，发现一张千万级的订单表上建了十几个索引，写入慢得离谱，而真正常用的几个查询却一个都没用上索引。那次之后我才意识到，索引不是贴上就灵的膏药，想用好它，得先弄清楚它到底长什么样。

这篇文章就从一个问题出发：为什么主流关系型数据库的索引几乎都选择了 B+ 树？

先想清楚：索引要解决什么问题

索引的目标很朴素，就是让查找变快。如果只看内存里的查找，候选结构有很多：

• 哈希表：等值查找平均 O(1)，快得惊人；
• 二叉搜索树：查找 O(log n)，还天然有序；
• 跳表：同样 O(log n)，实现比平衡树简单。

但数据库面对的环境和内存算法题完全不同。数据主要存放在磁盘上，而磁盘有一个决定性的特点：一次读取的开销，和读多少数据关系不大，和读多少次关系很大。

以机械硬盘为例，一次随机读取需要寻道和旋转等待，耗时通常在毫秒级；而一旦磁头就位，连续读取几十 KB 数据的额外开销几乎可以忽略。固态硬盘虽然没有机械寻道，但它同样以"页"为单位读写，随机读的次数依然是性能的关键。

所以，对磁盘上的索引来说，真正要优化的不是比较次数，而是磁盘 I/O 的次数。这个视角一换，很多结构的优劣就完全不一样了。

逐个排除候选者

哈希表的问题在于它只擅长等值查询。像 WHERE age BETWEEN 20 AND 30、ORDER BY create_time、WHERE name LIKE '张%' 这类范围查询、排序和前缀匹配，在哈希表里都无从下手，只能全表扫描。而这些恰恰是业务中最常见的查询形式。因此哈希索引只在少数特定场景下使用，不适合当通用索引。

二叉搜索树的问题在于"太高了"。一个节点只存一个键、只有两个分叉，一千万条数据组成的平衡二叉树，高度大约是 24 层。如果每个节点都存储在不同的磁盘页上，最坏情况下一次查找需要 24 次磁盘 I/O。按每次 10 毫秒计算，单次查询就要 240 毫秒，这是完全不可接受的。

问题的症结很明显：每次 I/O 读进来一整页数据（通常是 4KB 或 16KB），却只用了其中一个键，大量空间被浪费了。

那么，能不能让一个节点装下更多的键，让树变得又矮又胖？ 这正是 B 树家族的核心思想。

B 树：把树压扁

B 树是一种多路平衡查找树。它的每个节点可以存放多个键和多个子节点指针，节点的大小通常被设计成恰好等于一个磁盘页。

假设一个节点能容纳 1000 个分叉，那么：

• 1 层能索引约 1000 条数据；
• 2 层约 100 万条；
• 3 层约 10 亿条。

也就是说，存储十亿级数据，树高也只有 3 到 4 层，一次查找最多几次磁盘 I/O。再考虑到根节点和上层节点通常常驻内存，实际需要访问磁盘的次数往往只有一两次。

这已经是质的飞跃了。那为什么数据库最终用的是 B+ 树，而不是 B 树本身？

B+ 树：在 B 树基础上的两个关键改进

B+ 树和 B 树结构很像，但有两点重要区别。

第一，只有叶子节点存储数据，非叶子节点只存键。

在 B 树中，每个节点既存键又存对应的数据记录。数据记录往往比键大得多，这会挤占节点空间，导致每个节点能放下的键变少，分叉数下降，树也就变高了。

B+ 树把所有数据都下沉到叶子节点，内部节点只保留用于导航的键和指针。这样同样大小的节点能容纳更多的键，分叉数更大，树更矮，I/O 更少。

第二，叶子节点之间用链表串联起来。

所有叶子节点按键的顺序排列，并通过指针相互连接。这个设计对范围查询是决定性的。

想象一下查询 id BETWEEN 1000 AND 2000。在 B 树中，数据散落在各层节点里，要找出所有结果，需要在树中反复上下遍历。而在 B+ 树中，只需要先定位到 1000 所在的叶子节点，然后沿着链表顺序往后读，直到超过 2000 为止。顺序读取恰好是磁盘最擅长的访问方式。

此外，B+ 树还有一个不太起眼的好处：查询性能稳定。因为所有数据都在叶子层，任何一次查找都必须走到叶子，路径长度完全相同。而 B 树中，有的数据在根节点附近就能找到，有的要走到最底层，耗时波动更大。

把理论落到实处：聚簇索引与二级索引

以 MySQL 的 InnoDB 存储引擎为例，B+ 树的使用方式有一些值得了解的细节。

聚簇索引。 InnoDB 的表数据本身就是按主键组织的一棵 B+ 树，叶子节点里存放的是完整的行记录。换句话说，"表"和"主键索引"是同一个东西。这也是为什么推荐使用自增整数作为主键：新数据总是追加在树的最右侧，不会引起频繁的页分裂；而如果用随机的 UUID 作主键，每次插入都可能落在树的中间，导致大量的页分裂和碎片。

二级索引。 在其他字段上建立的索引也是 B+ 树，但叶子节点里存的不是完整行，而是该字段的值加上对应的主键值。通过二级索引查询时，先在二级索引树中找到主键，再拿着主键回到聚簇索引中查找完整的行，这个过程叫做回表。

回表意味着额外的查找开销。如果查询需要的字段恰好全部包含在二级索引中，就不必回表，这种情况称为覆盖索引。设计索引时有意识地利用覆盖索引，常常能带来明显的性能提升。

联合索引与最左前缀。 在多个字段上建立的联合索引，会按照字段定义的顺序依次排序。比如索引 (a, b, c)，数据先按 a 排序，a 相同再按 b 排序，以此类推。这就决定了查询条件必须从最左边的字段开始匹配才能用上索引。只有 WHERE b = 1 的查询无法利用这个索引，因为在整棵树中 b 并不是有序的。

回到开头那张表

理解了这些，再回看那张挂了十几个索引的订单表，问题就清楚了：

• 每个索引都是一棵独立的 B+ 树，每次插入、更新、删除都要同步维护所有这些树，写入自然越来越慢；
• 很多索引是单字段索引，而实际查询往往是多条件组合，单字段索引的过滤效果有限；
• 有几个联合索引的字段顺序和查询条件不匹配，违反了最左前缀原则，形同虚设；
• 状态字段、性别字段这种区分度很低的列也建了索引，优化器评估后通常宁可全表扫描。

最后的优化方案并不复杂：删掉七个几乎不被使用的索引，把几个单字段索引合并成两三个顺序合理的联合索引，再针对最高频的查询设计了一个覆盖索引。写入性能恢复正常，核心查询的耗时从数秒降到了几十毫秒。

几条实用的经验

索引不是越多越好。 每个索引都有写入成本和存储成本，只为真正高频、真正慢的查询建索引。

优先考虑联合索引。 把区分度高、最常用于等值匹配的字段放在前面，范围查询的字段放在后面。

学会看执行计划。 数据库提供的执行计划分析工具会告诉你查询是否用上了索引、用的是哪个、扫描了多少行。凭感觉加索引，远不如看一眼执行计划来得可靠。

警惕索引失效的写法。 对索引列使用函数、进行隐式类型转换、在左侧使用模糊匹配通配符，这些都会导致索引无法使用。

结语

B+ 树能成为数据库索引的事实标准，并不是因为它在算法复杂度上有多么惊艳，而是因为它恰好贴合了磁盘这种存储介质的物理特性：用更大的节点换更少的 I/O，用有序的叶子链表换高效的范围扫描。

这其实是系统设计中反复出现的一个道理：最好的数据结构，往往不是理论上最优的那个，而是最契合底层硬件的那个。 理解了这一点，再去看 LSM 树为什么适合写多读少的场景、列式存储为什么适合分析型查询，思路都会清晰很多。