MySQL之进阶：一篇文章搞懂MySQL索引之B+树

前言

在前面的系列文章中，介绍了关于MySQL索引的基础概念及相关知识，在这篇文章中，来讲解一些进阶的内容，也是我们在日常工作中经常用到的MySQL中InnoDB存储引擎的索引底层实现：B+树索引。

如果你还不了解MySQL索引的一些基础概念，可先阅读一下这篇文章《学习MySQL绕不开的两个基础概念：聚集索引与非聚集索引》，以及本系列中的其他文章。

提到B+树的索引实现，不得不先了解一下二叉查找树、平衡二叉树和B树这三种数据结构，因为B+树就是基于它们演化而来的。所以，在本篇文章中，除了B+树，你还将收获二叉查找树、平衡二叉树以及B树的相关知识。

二叉查找树

二叉查找树（Binary Search Tree，简称 BST）是一种树形数据结构，它具有以下特性：

• 节点的结构：每个节点包含三部分，一个值（称为键值）、指向左子树的指针/引用和指向右子树的指针/引用。
• 二叉搜索的性质：每个节点都满足，左子树中所有节点的值都小于当前节点的值，右子树中所有节点的值都大于当前节点的值，左子树和右子树本身也是二叉查找树。

下面来看一张二叉查找树的图结构：

二叉查找树

二叉查找树

上图展示了为 user 表创建的二叉查找树索引结构。图中的圆形代表二叉查找树的节点，其中最顶端的节点称为“根节点”，而没有子节点的节点称为“叶节点”。每个节点中存储了两个关键信息：键值（key）和数据（data）。键值对应 user 表中的 ID 字段，而数据则是 user 表中与该 ID 相关联的整行记录。

当需要查询 ID 为 8 的用户信息时，二叉查找树的查找过程如下：

• 初始阶段，将树的根节点设为当前节点，用查询的键值 8 与根节点的键值 10 进行比较。由于 8 小于 10，沿树的左子树移动，将其左子节点设置为当前节点。
• 接着，将查询键 8 与当前节点的键值 7 进行比较。因为 8 大于 7，继续沿树的右子树移动，将其右子节点设为当前节点。
• 最后，将 8 与当前节点的键值 8 进行比较，二者相等，查找成功。从当前节点中提取对应的实际数据（行数据）。

在二叉查找树中，插入和查找操作的时间复杂度取决于树的形态：

• 平均情况下（树较为平衡），操作的时间复杂度为 O(log⁡n)；
• 最坏情况下（树退化为链表），时间复杂度为 O(n)。

二叉查找树的结构还有效解决了插入新节点的问题。由于其“跳跃式”结构，节点无需按线性方式连续排列。在插入新节点时，只需根据键值找到合适的位置，避免了线性结构中插入一个元素导致其他元素依次移动的问题。这样，二叉查找树在动态数据管理中显得更为高效。

平衡二叉树

前面介绍了二叉查找树，但二叉查找树也存在自身的缺陷，比如在某些情况下可能退化为链表结构，具体如下面的图示所示：

二叉查找树退化为链表

二叉查找树退化为链表

当每次插入的元素总是当前二叉查找树中最大的元素时，树会逐渐演变为一条链表。这种情况下，插入和查找操作的时间复杂度会变为 O(n)。例如，查找 ID 为 17 的用户数据时，实际查找过程与全表扫描无异。出现这种现象的根本原因是二叉查找树的高度过高，导致结构不平衡，从而使查找效率显著下降且不稳定。

为了避免二叉查找树退化为链表，通常会引入平衡二叉查找树，例如红黑树和 AVL 树。这些平衡二叉树通过约束树的高度保证树形结构的近似平衡，从而提升查找效率。

平衡二叉树的核心思想是在二叉查找树的基础上增加以下条件：任意节点的左子树和右子树的高度差不能超过 1，并且每个子树始终保持平衡二叉树的性质。基于此，平衡二叉树可以始终将插入和查找操作的时间复杂度维持在 O(log⁡n)。

在一开始为 user 表创建的二叉查找树索引，其实就是一个平衡二叉树。而下图展示的则是一个不平衡的二叉树。

非平衡二叉树

非平衡二叉树

平衡二叉树之所以能维持高效的查找操作，是因为它在插入或删除节点后会自动“调整”树的结构以保持平衡。这种动态调整使得平衡二叉树相比普通二叉查找树查找效率更加稳定，整体访问速度也更快。

然而，无论是平衡二叉树还是红黑树，当数据量不断增大时，树的高度也会随之增加。这意味着在执行查询操作时磁盘 I/O 的次数增多，逐渐影响整体查询性能。造成这一问题的根本原因在于这些数据结构的设计限制：它们是二叉树，每个节点只能有最多两个子节点。

那么，如果我们扩展二叉树为 M 叉树（M > 2），会发生什么呢？

对于具有相同节点数的树而言，三叉树（M=3）的高度会显著低于二叉树。当节点总数进一步增加且树的分叉数 M 越大时，M 叉树的高度会远小于二叉树的高度。这种设计显著降低了树的深度，从而减少查询时的磁盘 I/O 操作，提高数据访问效率。

B树

虽然平衡二叉树能够将查询操作的时间复杂度保持在 O(log⁡n)，但由于它的本质仍是一种二叉树结构，每个节点最多只有 2 个子节点。当数据量不断增长时，树的高度会随之增加，这会导致磁盘的 I/O 次数显著增多，从而降低数据查询的效率。

需要注意的是，与内存访问相比，磁盘操作的速度要慢几个数量级。因此，优化查询效率的关键在于尽可能减少磁盘读取次数。此外，磁盘的数据读取是按照磁盘块的单位进行的。如果一个磁盘块可以容纳更多的数据，那么查询时就能一次性加载更多信息，从而极大地提升数据访问效率。

然而，如果采用平衡二叉树作为索引的数据结构，每次查找节点都需要从磁盘读取对应的块信息，每个节点只存储一个键值和数据。这种设计在数据量较大时会导致严重的性能瓶颈，无论是数据存储还是查询效率都会受到限制。

为了解决平衡二叉树的缺陷，需要一种单个节点可以存储多个键值和数据的结构。这种树便是 B 树（Balance Tree），一种改进的多叉平衡树。

B树的结构

B 树突破了二叉树的限制，允许每个节点最多包含 M 个子节点（M > 2），从而显著降低树的高度。这个设计使得 B 树成为一种高效的多叉树。在 B 树结构中：

• 每个节点最多可以存储 M-1 个键值（Keys）和数据（Data）；
• 每个节点最多可以拥有 M 个子节点；
• B 树的阶数由 M 指定，M 称为 B 树的阶。

因此，相较于平衡二叉树，B 树的每个节点不仅存储了更多的键值和数据，还拥有更多的子节点，这进一步降低了树的高度。

假设有一棵 3 阶 B 树（M=3），其特点是：

• 每个节点最多存储 2 个键值（M-1）；
• 每个节点最多拥有 3 个子节点（M）；
• 当节点存储的键值超过其容量时（超过 M-1 个键值），节点会发生分裂。

通过这种设计，B 树能够平衡查询效率和磁盘 I/O 操作次数，在数据量较大的情况下表现出更高效的性能。

下图展示了一个典型的 B 树结构：

B树

B树

上图是一棵 3 阶 B 树，其中节点的指针 p 用于指向子节点。图中的每个节点在 MySQL 中被称为 "页"，这是因为页是 MySQL 中数据读取的基本单位，而页实际上对应磁盘块。在 MySQL 的索引底层数据结构中，使用 "页" 的概念更符合实际情况。

假设需要在上图的 B 树中查找 ID 为 75 的用户信息，可以按照以下步骤进行操作：

• 首先，访问根节点的页（页 1），将查询键值 75 与页 1 中的键值 35 比较。由于 75 大于 35，根据页 1 中的指针 p3 跳转至子节点页 4。
• 在页 4 中的键值进行比较，发现查询键值 75 介于键值 65 和键值 87 之间。根据页 4 中的指针 p2 跳转至子节点页 10。
• 在页 10 内查找，最终找到匹配的键值 75，并获取对应的用户信息 (75, pl)。

在这棵 3 阶 B 树中，查询 ID=75 的过程中，树的高度为 3，因此会发生 3 次磁盘 I/O 操作。然而，如果存储相同数量的数据使用平衡二叉树，其树的高度会更大，因此磁盘 I/O 操作次数也会显著增加。由此可见，B 树在数据查询场景下的效率明显优于平衡二叉树。

B树存在的不足

尽管 B 树的优势显著，但它也存在一些缺点：

节点存储索引和记录数据：B 树的每个节点不仅包含索引数据（键值），还存储记录数据（行信息）。然而，用户记录数据的大小通常远远超过索引数据的大小。在查找过程中，为了访问索引数据，会加载整个节点的数据块，这会增加磁盘 I/O 操作次数。

加载无用记录数据：在查询位于底层某个节点的过程中，例如查找记录 A，会将一些无关的记录数据（非 A 记录数据）从磁盘加载到内存。这些记录数据对查询没有帮助，因为我们仅使用索引数据进行比较。这不仅增加了磁盘 I/O 操作次数，还额外消耗了内存资源。

范围查询效率低：使用 B 树进行范围查询（如查找某个范围内的键值）往往需要通过中序遍历访问多个节点，涉及频繁的磁盘 I/O。这样一来，在处理范围查询时，B 树的整体查询效率可能会下降。

上述问题暴露了 B 树的局限性，因此在实际应用中进一步演化出了 B+树。B+树针对 B 树的不足进行了优化，专注于索引效率提升，尤其是范围查询和磁盘 I/O 的优化。

B + 树

最后，主角终于登场，那就是 B+ 树。B+ 树是 B 树的一种升级版优化结构，而在 MySQL 中，索引的数据结构正是基于 B+ 树实现的。

img

img

B+ 树与 B 树的主要区别

数据的存储位置：

• 在 B 树中，所有节点（包括叶子节点和非叶子节点）都会存储键值和实际数据（即索引和记录）。
• 而在 B+ 树中，仅叶子节点存储实际数据（索引+记录），非叶子节点只存储键值（索引）。

这种设计的好处是，非叶子节点只存储键值，因此固定大小的数据库页（如 InnoDB 中的页默认大小为 16KB）能够容纳更多的键值。这样，B+ 树的阶数（每个节点子节点的最大数量）会更高，使得树的形态“更矮更胖”。树的高度变得更低，可以显著减少查询时磁盘 I/O 操作的次数，从而提高查询效率。

B+ 树的阶数等于节点中能够存储的键值数量。例如，如果 B+ 树的一个节点可以存储 1000 个键值，那么一棵 3 层的 B+ 树就能够存储多达 1000×1000×1000=10 亿条数据。通常情况下，根节点会常驻内存，对于这棵 B+ 树，查询任意键值只需要 2 次磁盘 I/O，效率非常高。

叶子节点的排列和结构：

• B+ 树的所有索引都会出现在叶子节点中，叶子节点之间通过有序链表连接构成一个可遍历的结构。
• 这种设计使得范围查找、排序查找、分组查找以及去重查找变得非常简单高效。

而在 B 树中，由于实际数据分散在各个节点上，这些操作的实现变得复杂且不高效。

B+ 树在 MySQL 中的实现

InnoDB 中的 B+ 树索引：上图展示了 InnoDB 中基于 B+ 树的索引实现方式（严格来说，是 聚集索引 的实现方式）。在 InnoDB 中，数据页之间通过双向链表连接，叶子节点中的数据记录通过单向链表连接。通过这些链表结构，可以快速访问表中的所有数据，同时支持高效的范围查找。

MyISAM 中的 B+ 树索引：MyISAM 的 B+ 树索引实现与 InnoDB 略有不同。对于 MyISAM，B+ 树的叶子节点并不存储实际数据，而是存储指向数据文件的地址。在执行查询时，定位到叶子节点后需要进一步通过文件地址读取对应的数据。因此，相较于 InnoDB，MyISAM 的索引查询效率在某些场景下会略低。

通过以上对比，我们可以看到 B+ 树的改进之处，不仅提升了查询效率，还为范围查找等复杂查询场景带来显著优势。这样的结构设计使得 B+ 树成为 MySQL 索引实现的核心数据结构，同时有针对性地解决了 B 树的一些关键性问题。

小结

这篇文章，我们通过二叉查找树、平衡二叉树、B 树逐步引入了 MySQL 索引底层的核心数据结构——B+ 树，并详细介绍了B+树高效查询及范围查找的优化设计。在 InnoDB 和 MyISAM 存储引擎中，B+ 树展现出了更高效的索引查询能力，尤其是在减少磁盘 I/O 和支持复杂查询场景方面具有优势。理解 B+ 树不仅有助于优化数据库查询性能，还能帮助我们深入掌握 MySQL 索引的工作原理，为日常开发与调优提供重要参考。

全文完，感谢阅读，如果喜欢请三连。