1. 引言：为什么 B+ 树与 B* 树值得深入研究

在计算机科学与数据库工程的交汇处，树结构始终扮演着核心角色。无论是操作系统的文件系统、关系型数据库的存储引擎，还是现代分布式系统里的元数据管理，几乎都能看到同一种数据结构的身影——B+树。与此同时，B*树作为 B 树家族中一个相对小众却设计精巧的变体，也因其非根节点分裂策略和更高的空间利用率而备受关注。

很多开发者在日常工作中频繁使用数据库索引，却对底层实现缺乏系统认知。当面试官问起「为什么 MySQL 要使用 B+ 树而不是红黑树」「为什么索引会失效」「最左前缀原则的底层依据是什么」时，往往只能给出零散甚至错误的答案。这些问题的答案，都深埋在 B 树家族的设计哲学之中。

本文的目标，是从数据结构的最基本问题出发，逐步推导出 B 树、B+ 树、B* 树产生的必然性，再深入到数据库索引的实现细节，最后落到实战层面的索引设计与优化。文章覆盖以下几个部分：

• 演进脉络：从二叉搜索树到平衡二叉树，再到 B 树家族，理解每一次结构升级解决的核心问题。
• B 树详解：定义、性质、查找、插入、删除与高度分析。
• B+ 树详解：结构特征、与 B 树的本质差异、各项操作的完整过程。
• B* 树详解：分裂策略、设计动机、优缺点与适用场景。
• 数据库索引原理：B+ 树如何落地为存储引擎中的索引结构，聚簇索引、二级索引、联合索引与覆盖索引的机制。
• MySQL InnoDB 深入：页结构、索引组织表、回表机制与索引维护成本。
• 结构对比：B 树、B+ 树、B* 树与其他常见树结构的横向比较。
• 实战优化：索引失效的典型场景、优化原则与案例分析。

阅读本文需要读者具备基本的二叉树和算法复杂度概念。如果你对「树的高度」「磁盘 I/O」「页」这些词感到陌生，也无需担心，文章会从直觉层面逐步建立这些概念。建议通读一遍以建立整体框架，再针对自己关心的部分精读和复盘。

2. 演进脉络：从二叉搜索树到 B 树家族

2.1 二叉搜索树的理想与现实

二叉搜索树是最朴素的搜索结构之一：每个节点最多有两个子节点，左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。这个性质保证了在理想情况下，查找操作可以在 O(log n) 时间内完成。

然而「理想情况」成立的前提是树保持大致平衡。如果插入序列本身有序，比如依次插入 1、2、3、4、5、6，二叉搜索树会退化成一棵单侧延展的链表，此时查找复杂度退化为 O(n)。这在真实系统中是不可接受的，因为数据的写入顺序几乎不可能被保证是随机的。

2.2 平衡二叉树的补救

为了解决退化问题，人们设计了自平衡二叉树，代表结构包括 AVL 树和红黑树。AVL 树通过维护每个节点的平衡因子，在失衡时进行单旋或双旋操作，强制左右子树高度差不超过 1，从而保证查找、插入、删除均为 O(log n)。红黑树则放宽了平衡条件，通过对节点染色和一系列旋转、变色规则，保证最长路径不超过最短路径的两倍，以换取更少的旋转次数和更稳定的插入性能。

平衡二叉树在内存场景下表现优秀，Java 的 TreeMap、C++ STL 的 map 等数据结构底层都采用红黑树。但当数据规模大到必须落盘时，它们的局限性就暴露了出来。

2.3 磁盘 I/O：树结构的真正瓶颈

在数据库和文件系统中，数据存储在磁盘上。磁盘访问的延迟远高于内存：一次随机磁盘寻道的时间通常是内存访问的十万倍以上。因此，衡量磁盘数据结构性能的核心指标，不是 CPU 比较次数，而是磁盘 I/O 次数。

对于一棵存储在磁盘上的二叉树，即使它完美平衡，高度也可能非常大。假设数据量为 100 万条，二叉树最优高度大约为 log₂(1000000) ≈ 20 层。这意味着一次查找最坏需要访问 20 个节点，而如果这些节点分散存储在不同磁盘块中，就对应 20 次磁盘 I/O。这在数据库场景下几乎不可接受。

问题的关键在于：二叉树的每个节点只存一个键和两个指针，导致节点非常「瘦小」，远小于操作系统和磁盘交换数据的最小单位——页。一个典型磁盘页为 4KB 或 16KB，而一个二叉树节点可能只有几十字节，这造成了巨大的空间浪费和 I/O 放大。

2.4 直觉：让每个节点装下更多内容

既然磁盘按页读取，那么最自然的优化思路就是：让树中每个节点的大小尽量接近一个页的大小，并且在一次 I/O 中把一个节点完整读入内存，再充分利用这个节点里存储的多个键进行二分查找。这样一来，树的高度会显著降低，I/O 次数也随之大幅减少。

这种「每个节点可以拥有多个子节点」的树，就是多路搜索树。B 树正是多路平衡搜索树中最经典、最成熟的实现。B 树、B+ 树、B* 树都共享这一底层思想：用更宽、更矮的树来适配磁盘块访问模式。

3. B 树详解

3.1 B 树的定义与性质

B 树，全称 B-tree，由 Rudolf Bayer 和 Edward M. McCreight 于 1970 年前后提出，是一种自平衡的多路搜索树。关于字母 B 的含义，常见的说法有 Balanced、Bayer 或 Boeing，作者本人并未给出官方解释，但不妨碍它成为数据库和文件系统中最重要的数据结构之一。

一棵 m 阶 B 树满足以下性质：

• 每个节点至多有 m 个子节点，至多存储 m-1 个关键字。
• 除根节点和叶子节点外，每个节点至少有 ⌈m/2⌉ 个子节点，即至少存储 ⌈m/2⌉-1 个关键字。这个下限保证了节点不会过度稀疏。
• 根节点若不是叶子节点，至少要有 2 个子节点。
• 所有叶子节点都在同一层，这保证了整棵树的绝对平衡。
• 每个非叶子节点中，关键字按照升序排列，且关键字 kᵢ 左侧子树的所有关键字都小于 kᵢ，右侧子树的所有关键字都大于 kᵢ。

这里需要特别强调「所有叶子节点都在同一层」这一性质。它意味着无论从哪个节点开始查找，到达任意叶子节点的路径长度都完全相同，B 树不会出现局部退化。这是 B 树与普通多路搜索树的本质区别之一，也是它能够保证稳定查找性能的根基。

3.2 B 树节点结构

在典型的 B 树实现中，一个内部节点由多组「关键字-子树指针」构成。例如一个存储了关键字 10、30、60 的节点，会拥有 4 个子节点指针，分别指向：小于 10 的子树、位于 10 和 30 之间的子树、位于 30 和 60 之间的子树、大于 60 的子树。

有些 B 树实现还会在每个内部节点中额外存储指向数据的指针，使查找命中内部节点时可以直接返回数据，这也是传统 B 树与 B+ 树的重要区别之一。我们将在第 4 章详细对比这一点。

阶数 m 的选择并非随意。在数据库场景中，m 通常不是先验确定的，而是由「节点容量等于磁盘页大小」这一约束反推出来。例如页大小为 16KB、每个键加子指针占 40 字节时，m 约为 400 阶，这意味着每个内部节点可以容纳大约 400 个子节点，树的高度自然被压得很低。

3.3 B 树的查找

B 树的查找从根节点开始，采用以下流程：

1. 从根节点出发，在当前节点的关键字序列中执行二分查找，找到第一个大于等于目标值的位置。
2. 若当前位置的关键字等于目标值，且内部节点存储了数据指针，则直接返回结果。
3. 否则，沿着该位置对应的子节点指针进入下一层。
4. 重复上述过程，直到到达叶子节点；若在叶子节点中也未命中，则判定查找失败。

值得强调的是，B 树的查找不仅在树的高度方向上进行，还在每个节点内部进行二分查找。总比较次数约为 O(log m × log_m n)，但从磁盘视角看，每一次下降一层只对应一次磁盘 I/O，因此磁盘 I/O 次数约为树的高度 h。这也是 B 树性能评估中最关键的量。

3.4 B 树的插入

B 树的插入遵循「先插入、后分裂」的原则。具体步骤如下：

1. 从根节点开始，按照查找路径定位到目标叶子节点。
2. 若目标叶子节点未满，即关键字数量小于 m-1，则将新关键字按顺序插入该叶子节点，操作结束。
3. 若目标叶子节点已满，即关键字数量等于 m-1，插入后关键字数量将达到 m，违反了节点容量上限，此时需要执行分裂操作。

分裂过程如下：

1. 将溢出的节点以中间关键字为界分为左右两个节点，左节点保留较小的关键字，右节点保留较大的关键字，中间关键字则上移到父节点。
2. 若父节点也因上移而溢出，则对父节点继续执行同样的分裂操作。
3. 若分裂一直传播到根节点，根节点溢出后会被分裂为左右两个节点，同时产生一个新的根节点，新根节点仅包含原中间关键字和指向左右子节点的指针。此时整棵树的高度增加 1。

这种自底向上的分裂传播，保证了 B 树始终维持「所有叶子节点在同一层」的平衡性质。分裂是 B 树在写入场景下的主要成本之一，但它的发生频率随节点容量增大而降低：节点容量越大，触发分裂的概率越低，这也是大节点设计的另一个优势。

3.5 B 树的删除

B 树的删除比插入更复杂，因为删除后必须维护「节点关键字数量不低于下限」这一约束。删除流程大致如下：

1. 定位到包含待删除关键字的目标节点。
2. 若目标节点是叶子节点，直接删除该关键字。
3. 若目标节点是内部节点，通常不能直接删除关键字，因为关键字承担着分割子树的路由职责。常见的做法是：用其左子树的最大关键字或右子树的最小关键字替换待删除关键字，然后到对应叶子节点中删除这个替换用的关键字。
4. 删除后若节点关键字数量低于下限，需要执行「借位」或「合并」操作恢复平衡。

借位：若被删节点的一个相邻兄弟节点关键字数量大于下限，则从父节点「借」一个关键字下来，同时将兄弟节点的一个关键字上移到父节点。这种方式保持了节点数量的同时，不需要改变树的高度。

合并：若相邻兄弟节点也都处于下限状态，则将被删节点与一个兄弟节点以及父节点中的分割关键字合并为一个节点。合并操作会导致父节点关键字数量减少，若父节点也因此低于下限，则继续向上传播合并，最坏情况下会传导到根节点，导致树的高度降低 1。

删除操作的复杂度与插入相当，但其传播机制更丰富，编码实现时需要格外小心边界条件，尤其是根节点特殊情况的处理。

3.6 B 树的高度与性能分析

假设一棵 m 阶 B 树存储了 N 个关键字，最小子节点数为 ⌈m/2⌉，记为 t，则高度 h 满足以下关系：

在关键字数量方面，高度为 h 的 B 树最少关键字数约为 2 × t^(h-1) - 1，最多关键字数约为 m^h - 1。因此，对于给定关键字数 N，树高 h 满足：

log_m(N+1) ≤ h ≤ log_t((N+1)/2) + 1

以实际数字为例：若页大小为 16KB，m 取 400 阶，存储 1 亿条记录时，B 树高度大约仅为 3 到 4 层。这意味着一次查找最多只需 3 到 4 次磁盘 I/O 就能定位到目标数据，与二叉树的 20 多层相比是数量级的提升。

这种优越性正是 B 树家族统治磁盘数据结构领域的根本原因。但传统 B 树也有不足：内部节点同时存储数据和路由信息，导致单个页能容纳的关键字数量受限，且范围查询效率不高。这些不足直接催生了 B+ 树。

4. B+ 树详解

4.1 B+ 树的定义与结构

B+ 树是 B 树最重要的变体，也是 MySQL InnoDB、Oracle、SQL Server 等主流数据库默认采用的索引结构。它在 B 树的基础上做了几项关键改造：

• 数据只存储在叶子节点：内部节点只保存关键字和子节点指针，不保存数据本身。内部节点的全部关键字只是「路标」，用于路由查找。
• 叶子节点之间用链表串联：所有叶子节点通过指针按关键字顺序连接，形成一个有序的单向或双向链表。
• 内部节点关键字可以是「冗余」的：某个关键字即使出现在内部节点中，也一定会在叶子节点中再次出现，保证叶子节点包含完整的数据全集。

这一设计带来两个巨大收益：一是内部节点因为不携带数据而变得非常「轻」，同一页可以容纳更多关键字，树高进一步降低；二是叶子节点链表使范围查询变得极其高效，找到下界后可以顺序遍历链表，而不需要在树中反复回退。

4.2 B+ 树与 B 树的本质差异

很多初学者把 B+ 树简单理解为「B 树把数据挪到了叶子节点」。这固然是结构上的核心差异，但更重要的是理解这种结构变化引出的行为差异：

对比维度	B 树	B+ 树
数据存储位置	内部节点和叶子节点均可存储数据	仅叶子节点存储数据
内部节点内容	关键字 + 数据 + 子指针	仅关键字 + 子指针
单节点可容纳关键字数	较少（被数据占用空间）	较多（节点更轻）
树高	相对较高	相对较矮
点查询	命中内部节点可提前返回	必须一直查找到叶子节点
范围查询	需要对树进行中序遍历，复杂且 I/O 次数多	叶子链表顺序遍历，高效稳定
稳定性	不同位置的数据查找路径长度不同	所有数据查找路径等长，性能稳定

有一个常见误解需要澄清：B 树在内部节点命中时可以提前返回，理论上点查询可能比 B+ 树更快。但从工程角度看，数据库索引的绝大多数负载包含范围扫描，且磁盘 I/O 次数的稳定性比偶尔少访问一层更有价值。更重要的是，B+ 树将数据全部下沉到叶子层后，内部节点变得紧凑，整体树高更矮，实际上在多数数据规模下点查询的 I/O 次数也不劣于 B 树。

4.3 B+ 树的查找

B+ 树的查找路径与 B 树类似：从根节点开始，在每个内部节点做二分查找确定要进入的子节点，直到到达叶子节点。区别在于，无论目标关键字是否在内部节点中出现，都必须一直走到叶子节点。在叶子节点中通过二分或顺序扫描找到目标关键字后，再取得其对应的数据指针。

这种「所有点查询路径等长」的特性，使 B+ 树在性能可预测性上明显优于 B 树，这对数据库的查询优化器估算成本也更有帮助。

4.4 B+ 树的插入

B+ 树的插入同样遵循「先插入、后分裂」原则，但分裂策略与 B 树有细微差异：

1. 沿着查找路径定位到目标叶子节点。
2. 将新关键字插入叶子节点。若叶子节点未满，插入即结束。
3. 若叶子节点已满，将其分裂为两个节点，并将合适的中间关键字复制或上移到父节点，作为路由信息。
4. 与 B 树不同的是，分裂后上移到父节点的关键字，通常仍然保留在叶子节点中。也就是说，内部节点中的关键字只是叶子节点关键字的副本。
5. 父节点若溢出则继续分裂，传播到根节点时树高增加 1。

由于内部节点不存储数据，B+ 树的内部节点可以容纳更多关键字，分裂触发频率进一步降低。在大容量节点的场景下，绝大多数插入只涉及一个叶子节点的局部修改，写入性能非常平稳。

4.5 B+ 树的删除

B+ 树的删除与 B 树类似，但有一个关键简化：当删除的关键字是某个内部节点中的路由关键字时，通常不需要在内部节点中立即删除它。因为内部节点关键字只负责路由，并不直接持有数据，即便它略微「过时」，只要仍能正确划分左右子树的范围，查找就不受影响。

删除的核心步骤仍然是：

1. 在叶子节点中找到并删除目标关键字。
2. 若叶子节点关键字数低于下限，尝试向相邻兄弟借位；借位时可能需要同时更新父节点中的分割关键字。
3. 若无法借位，则与兄弟节点合并，并相应更新父节点；合并传播到根节点时树高降低 1。

这种「内部节点路由关键字可延迟清理」的特性，让 B+ 树的删除实现比 B 树更灵活，也是许多存储引擎在选择索引结构时青睐 B+ 树的工程原因之一。

4.6 B+ 树的核心优势总结

• 更低的树高：内部节点瘦身，单层扇出更大，磁盘 I/O 次数更少。
• 高效的范围查询：叶子链表支持顺序扫描，天然适配 SQL 中的范围条件和排序需求。
• 稳定的查询性能：所有数据都在叶子层，点查询路径等长。
• 便于支撑二级索引与聚簇索引的配合：叶子节点可以只存主键值，形成紧凑的二级索引结构。

正是这些特性，使 B+ 树成为绝大多数关系型数据库存储引擎索引结构的事实标准。

5. B* 树详解

5.1 B* 树的定义

B* 树是 B+ 树的一个变体，二者的主体结构几乎相同：数据只存储在叶子节点，内部节点仅作索引，叶子节点之间以链表相连。B* 树与 B+ 树的唯一实质性差异，在于非根节点的分裂策略。

在标准 B+ 树中，当一个节点溢出时，它被分裂为两个各约 50% 满的节点。B* 树则要求：非根节点在分裂前，必须先尝试向相邻兄弟节点「匀出」部分关键字。只有当相邻兄弟节点也都满了、无法再接纳新关键字时，才真正执行分裂，且分裂后两个新节点各占原始数据的三分之二左右，也就是保持约 66.7% 的填充率。根节点仍然可以按 B+ 树的规则分裂。

5.2 B* 树的分裂机制详解

设 B* 树的非根节点最少填充率为 66.7%，即每个非根节点的关键字数量至少占其容量的 2/3。当向一个已满的叶子节点 P 插入新关键字时：

1. 先检查 P 的左兄弟或右兄弟，若某个相邻兄弟节点尚未满，则将 P 中的一部分关键字搬迁到兄弟节点中，使 P 重新留出空间，随后把新关键字插入 P。父节点中的分割关键字需要同步更新，以反映新的边界。
2. 若 P 的两个相邻兄弟节点（或存在的那个兄弟节点）都已满，则将 P 与兄弟节点中的关键字合并在一起，再重新均匀分配到三个节点中。若兄弟节点只有一个，则重新分配到两个节点中，并创建或复用第三个节点以承接额外的数据，随后更新父节点中的对应路由信息。

这种机制最直观的效果是：节点在不必要的情况下不会被立即分裂，从而提升了节点的平均空间利用率。标准 B+ 树经历大量插入后，节点的平均填充率通常约在 69% 左右，而 B* 树可以将这一数字提升到约 81% 以上，写密集、插入量大的场景下尤其明显。

5.3 B* 树的设计动机

B* 树的设计初衷是减少节点分裂导致的存储空间浪费。在磁盘数据库中，页面利用率直接决定数据文件的大小和缓存命中率。填充率越高，同样数量的数据占用的页越少，树高越低，内存中能缓存的热点页比例也越高。

此外，节点分裂是 B 树家族中成本最高的写操作之一，因为分裂往往需要新分配页面并修改父节点，甚至会向上传播。B* 树通过延迟分裂，减少了分裂次数，在插入密集的负载下降低了整体写入放大。

5.4 B* 树的优缺点

优点包括：

• 空间利用率更高，数据文件更紧凑。
• 分裂频率降低，插入密集型场景下写放大更小。
• 保留了 B+ 树高效范围查询的全部优点。

缺点同样明显：

• 插入、删除时的「匀数据」和「再分配」操作更复杂，涉及兄弟节点间的数据搬运，编码难度高。
• 增删过程中需要更频繁地更新父节点路由关键字和兄弟指针，锁竞争更复杂。
• 并发控制更困难，因为一次插入可能同时修改两个甚至三个节点，加锁范围更大。
• 实际工程实现相对稀少，数据库领域仍以 B+ 树为主流，B* 树的优化收益在多数场景下不足以弥补其实现复杂度。

总体而言，B* 树是数据结构理论中一个精巧的优化方向，理解它有助于深化对「节点填充率与写放大之间权衡」的认知。虽然在主流数据库中没有大规模落地，但它对理解存储结构设计中的工程取舍非常有价值。

6. 数据库索引原理：B+ 树的工程落地

6.1 索引是什么

数据库索引可以类比为书的目录：没有目录时，要查找某个主题只能逐页翻找；有了目录，先根据目录定位到页码，再翻到对应页面读取内容。数据库索引的本质，是一种独立于数据存储、用于加速数据定位的辅助结构。

从文件视角看，一张表的索引就是一个由索引键到数据位置的映射。当用户执行带条件的查询时，查询优化器评估各索引的代价，选择最优索引，通过索引结构定位到满足条件的数据位置，再读取实际数据。

6.2 为什么索引结构选择 B+ 树

数据库索引结构需要同时满足以下需求：

• 支持点查询：根据等值条件快速定位单条或多条记录。
• 支持范围查询：高效处理大于、小于、区间以及 ORDER BY 等操作。
• 支持动态增删改：数据持续写入和删除，索引必须能在线维护而不使性能退化。
• 适配磁盘特性：节点大小与磁盘页对齐，最小化 I/O 次数。

我们来逐一排除其他候选结构：

哈希表：等值查询极快，但完全不支持范围查询和排序，且哈希冲突处理在数据量变化时需要重建，不适合作为数据库的通用索引。

红黑树与 AVL 树：在内存中表现出色，但二叉树过高，磁盘场景下 I/O 次数多，不适合。

跳表：内存中支持高效范围查询，但整体仍是「扁平多指针链表」结构，节点利用率低，磁盘局部性差。

LSM 树：写入性能极强，适合日志型负载，但读放大和空间放大问题需要额外的压缩与合并策略，复杂度高。

B 树：支持范围查询，但数据分散在内部节点，范围扫描需要回退遍历，且单节点扇出较小。

B+ 树：兼顾点查询、范围查询、稳定树高、良好的磁盘适配性，配合叶子链表可以高效地完成范围扫描，因此成为关系型数据库索引的默认选择。

需要说明的是，不同数据库有不同取舍。例如 MongoDB 默认采用 B 树，因为文档模型更偏向单文档读写；而 MySQL、PostgreSQL、Oracle 等关系型数据库普遍采用 B+ 树，以支撑 SQL 中大量的范围查询和排序操作。

6.3 聚簇索引与非聚簇索引

根据数据与索引的物理组织方式，数据库索引可分为聚簇索引和非聚簇索引两大类。

聚簇索引：索引的叶子节点直接存储整行数据。也就是说，数据本身就是索引的一部分，表数据的物理顺序与索引键顺序一致。每张表只能有一个聚簇索引，因为数据只能以一种物理顺序存储。在 MySQL InnoDB 中，主键索引就是聚簇索引。

非聚簇索引（二级索引）：索引的叶子节点存储的是索引键和指向实际数据的位置信息，而非整行数据。一张表可以有多个二级索引。在 InnoDB 中，二级索引叶子节点存储的是「索引键 + 主键值」，查询到主键值后再回到聚簇索引中查找整行数据，这个过程称为回表。

理解聚簇索引与二级索引的关系，是理解数据库索引优化的一把钥匙。二级索引越紧凑、回表代价越低，整体的查询性能就越好。

6.4 联合索引与最左前缀原则

联合索引是指由多个列共同组成的索引，例如在 (city, age) 两列上建立联合索引 idx_city_age。联合索引在 B+ 树中的组织方式为：先按第一列排序，第一列相同再按第二列排序。也就是说，联合索引的键是多个列值的组合。

在这种结构下，联合索引只有在查询条件从最左侧列开始连续匹配时才能被有效利用，这就是「最左前缀原则」。例如联合索引 (a, b, c)：

• WHERE a = 1：可以命中索引前缀。
• WHERE a = 1 AND b = 2：可以命中索引前缀。
• WHERE a = 1 AND b = 2 AND c = 3：可以完整命中索引。
• WHERE b = 2：不能命中，因为 b 不是最左列。
• WHERE a = 1 AND c = 3：只能利用 a 列进行过滤，c 列无法通过索引进一步缩小范围，因为中间跳过了 b。

这背后的原理正是 B+ 树的排序结构：联合索引中，只有保证前缀列值固定或有序，后续列才具有全局有序性。一旦前缀缺失，后续列在索引中的排列就不再有序，索引自然失效。

6.5 覆盖索引

覆盖索引是指一个查询所需的全部列都包含在某个索引中，查询只需遍历该索引，无需回表即可获得全部结果。例如联合索引 (a, b, c) 对于查询 SELECT a, b, c FROM t WHERE a = 1 就是覆盖索引。

覆盖索引的价值在于避免了回表，使查询只访问索引页而不必访问数据页，大幅减少 I/O。在数据库优化中，当发现某个高频查询的字段有限且固定时，将这些字段组合进一个联合索引、使查询实现覆盖，是性价比极高的优化手段。

覆盖索引同时解释了为什么索引里存储的值越少越好：二级索引越窄，同样的「高度」对应的数据定位效率越高，占用空间越小，越容易完整放入内存缓存。

7. MySQL InnoDB 的 B+ 树索引深入

7.1 InnoDB 存储引擎与磁盘页

InnoDB 是 MySQL 默认的事务型存储引擎，支持 ACID 事务、行级锁、多版本并发控制和聚簇索引。InnoDB 将磁盘上的数据组织为固定大小的「页」，默认页大小为 16KB。所有索引和数据最终都以页为单位存储和读写，这与 B+ 树「节点对齐磁盘页」的设计哲学完全一致。

7.2 InnoDB 页的基本结构

InnoDB 的页包含页头、页尾、记录区、目录槽等多个部分。其中与索引直接相关的核心机制包括：

• 记录按主键顺序排列：页内的行记录按照主键值的升序组织，形成一个小的有序结构。
• 页目录（Page Directory）：页内为记录建立稀疏目录，通过二分定位目录槽快速找到目标记录区间，再在区间内顺序扫描。
• 前后页指针：同层相邻页之间通过指针连接，叶子层形成有序链表，上层节点则保存指向子页的指针和每个子页的边界键。

这个「页内记录有序 + 页间链表连接 + 上层索引页路由」的结构，本质上就是一棵 B+ 树。InnoDB 并没有单独为索引维护一套复杂抽象，而是直接以页为节点实现对 B+ 树的落地。

7.3 索引组织表与聚簇索引

InnoDB 的表数据采用索引组织表形式，即数据表本身就是以主键为聚簇索引的 B+ 树，叶子节点存放完整的行记录。因此 InnoDB 表必须有主键。若建表时未显式指定主键，InnoDB 会按以下规则自动选择合适的列作为聚簇索引键：

1. 选择第一个声明为 NOT NULL 的唯一索引。
2. 若没有这样的唯一索引，则自动生成一个隐藏的 6 字节自增 row ID 作为聚簇索引键。

这条规则带来了一个重要的实践建议：尽量为表显式设计一个有序、短小、稳定的主键。因为二级索引的叶子节点要存储主键值，主键越短，二级索引越小；主键若大量随机插入（如 UUID），还会导致 B+ 树频繁页分裂和页内数据移动，写入性能显著下降。

7.4 二级索引与回表

InnoDB 的二级索引也是一棵 B+ 树，但其叶子节点存储的是「二级索引键 + 主键值」。当查询通过二级索引执行时：

1. 先在二级索引 B+ 树中查找到匹配的索引键，得到对应的主键值。
2. 再携带该主键值到聚簇索引 B+ 树中查找，读取完整行记录。

这个「先查二级索引、再查聚簇索引」的过程就是回表。回表意味着多一次 B+ 树查找，多若干次磁盘 I/O。因此，访问大量随机行时，回表代价可能非常高，优化器甚至会放弃二级索引而选择全表扫描。

7.5 索引维护与页分裂

在 InnoDB 中，插入数据时若无序插入，会导致目标页已满而触发页分裂。页分裂后数据重新分布，并修改父页中的路由信息，成本较高。更不利的是，无序主键还会造成页空间碎片化，降低页填充率。

因此，为高写入频率的表选择单调递增的主键（如自增 ID），可以使新数据总是追加到 B+ 树的右端，分裂只发生在最右侧路径上，大大减轻页分裂和碎片问题。这也是许多业务表使用自增主键的底层原因。

7.6 关于 B+ 树 vs B* 树的工程补充

InnoDB 为了缓解标准 B+ 树页分裂导致的页利用率下降问题，设计了诸如插入缓冲、页合并等机制，并在局部通过页的再分配来做近似「兄弟节点匀数据」的优化。这些工程手段在思路上与 B* 树有相通之处，但 InnoDB 并未在全局层面采用标准 B* 树的分裂策略，主要原因是其操作的复杂性和并发控制成本过高。理解这一点，有助于把「B* 树的理论优点」与「生产系统的工程取舍」区分开。

8. B 树、B+ 树、B* 树与其他结构全面对比

结构	数据存储	范围查询	树高	空间利用率	实现复杂度	典型用途
红黑树	内存节点	中序遍历，效率一般	较高	较高	中等	内存有序容器，如 TreeMap
B 树	内部和叶子均可	需树遍历，较复杂	低	约 69%	中等	文件系统、MongoDB
B+ 树	仅叶子节点	叶子链表，极高效	更低	约 69%	中等	MySQL、PostgreSQL、Oracle 等
B* 树	仅叶子节点	叶子链表，极高效	更低	约 81% 以上	高	理论研究及部分存储系统优化
LSM 树	多层结构	需合并多源结果	不适用	取决于压缩策略	高	RocksDB、LevelDB、Cassandra

从表中可以清晰地看出，B+ 树并非在所有维度上都绝对最优，它之所以成为数据库索引的主流选择，是因为它在点查询、范围查询、写维护成本与实现复杂度之间取得了高度平衡。B* 树在空间利用率上更进一步，但实现复杂性显著上升，因此在强调稳定、易扩展的生产数据库中并未取代 B+ 树。选择结构时，需要结合数据规模、读写比例、查询模式和并发要求综合判断。

9. 实战：数据库索引设计与优化

9.1 索引不是越多越好

索引能加速查询，但也会拖慢写入并占用空间。每次 INSERT、UPDATE、DELETE 都会同步维护相关索引。索引越多，写入成本越高；同时，过多的小索引占用内存和磁盘，还会降低缓存命中率。优化索引的第一步，往往是删掉冗余和无用索引。

9.2 索引失效的典型场景

了解索引失效场景，是避免「建了索引却不生效」的关键。以下场景会阻碍 B+ 树索引的有效利用：

• 对索引列使用函数或运算：如 WHERE YEAR(create_time) = 2025，会破坏索引列本身的顺序，导致索引无法走全范围匹配。
• 隐式类型转换：字符串列与数字直接比较时，若发生隐式转换，索引可能失效。
• 前导模糊查询：LIKE '%keyword' 这种以通配符开头的条件，无法利用 B+ 树的有序性。
• 联合索引违反最左前缀：跳过最左列直接使用后续列。
• OR 条件未合理使用索引：OR 连接的两个条件中只要有一个无法走索引，整体查询可能退化为全表扫描。
• 范围条件之后的列失效：联合索引 (a, b, c) 中，若 a 使用范围查询，则 b、c 一般无法继续通过索引精确定位，因为 a 一旦是范围，b 在该范围内的排序不再具备全局有序性。

9.3 优化设计的一般原则

1. 为高频查询的过滤列建立索引：先观察慢查询日志，针对出现频率高、过滤效果好的列建索引。
2. 联合索引列顺序要合理：把等值查询、区分度更高的列放在前面；把范围查询列放在后面。
3. 尽量使用覆盖索引：让查询列全部落在索引中，避免回表。
4. 主键尽量短且有序：优先自增整型，减少页分裂和二级索引体积。
5. 避免大字段建索引：长文本列可考虑前缀索引，但需注意前缀选择性和回表代价。
6. 关注回表代价：当二级索引命中的行过多、回表随机 I/O 太大时，优化器倾向于全表扫描，此时应调整索引或查询写法。

9.4 一个联合索引设计案例

假设用户表 user 上经常执行如下查询：

SELECT user_id, nickname
FROM user
WHERE city = '上海'
  AND age BETWEEN 25 AND 35
ORDER BY user_id
LIMIT 20;

分析该查询：city 是等值条件，age 是范围条件，user_id 既参与排序又参与覆盖。可以设计联合索引 (city, age, user_id) 或 (city, user_id, age)。比较两种方案：

• (city, age, user_id)：city 等值定位，age 范围过滤，user_id 落在索引中可实现部分覆盖，但 ORDER BY user_id 因 age 是范围列而不一定能完全利用索引排序。
• (city, user_id, age)：city 等值定位后，user_id 有序，可同时满足 ORDER BY 和覆盖，但 age 作为第三列只能作为过滤条件而非缩小范围的结构化条件。

实际选择需要结合数据分布和查询频率，通过 EXPLAIN 观察执行计划中是否出现 Using index、Using filesort 等关键信息来迭代优化。这个例子也再次说明：索引优化不是套模板，而是理解 B+ 树排序结构与具体 SQL 访问模式之间的匹配关系。

10. 总结与延伸学习

本文从二叉搜索树在磁盘场景下的性能瓶颈出发，推导出多路平衡搜索树的设计必然性，系统梳理了 B 树、B+ 树、B* 树的定义、结构、操作与性能特征，并深入分析了 B+ 树在数据库索引中的工程落地，特别是 MySQL InnoDB 中的聚簇索引、二级索引、回表和页分裂机制，最后落到索引设计与优化的实战原则上。

核心结论可以归纳为三点：

1. 磁盘 I/O 是树结构设计的第一约束。B 树家族通过「宽节点降低树高」来解决磁盘访问放大问题。
2. B+ 树是数据库索引的事实标准。它将数据集中于叶子节点、以链表相连，把范围查询效率和稳定性推到了关系型数据库最需要的位置。
3. B* 树是空间利用率上的进一步优化，但其复杂的分裂与数据再分配机制带来了更高的实现和并发控制成本，因此更多停留在理论研究与局部优化思路中。

对于希望进一步深入的学习者，建议沿着以下几个方向延伸：

• 阅读 MySQL 官方文档中关于 InnoDB 页结构、聚集索引和二级索引的说明，结合源码了解 B+ 树的实际实现细节。
• 动手实现一个简化版 B+ 树，重点练习插入、删除的分裂与合并传播逻辑，这是理解其平衡机制的最佳方式。
• 研究 LSM 树与 B+ 树的对比，理解写入放大与读放大之间的权衡，及其在 NewSQL 与 KV 存储中的选择逻辑。
• 使用 EXPLAIN 分析真实业务 SQL 的执行计划，观察索引选择、回表、文件排序等现象，建立「SQL 语句到 B+ 树访问路径」的映射直觉。

数据库索引优化本质上是对 B+ 树结构与查询模式的理解运用。当你能在看到一条 SQL 时，脑中自动浮现它在 B+ 树上的查找路径、过滤能力和回表代价，便真正掌握了从数据结构到数据库性能的完整链路。