[每周一更]-(第99期)：MySQL的索引为什么用B+树？

索引是一种 数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。MySQL索引有三类：B+树索引、Hash索引、全文索引

在数据库系统中，索引是提高数据检索效率的关键工具。而在MySQL中，B+树索引是最常用的一种索引结构。理解为什么MySQL选择使用B+树而不是B树或其他树结构，首先需要深入了解B+树和B树的特性及其在数据库检索中的表现。

B树与B+树的基本概念

B树（Balanced Tree）

B树是一种自平衡的多叉树数据结构，其中每个节点可以包含多个子节点和键。B树的每个节点都包含键和子节点指针，叶子节点不需要保持在同一层。

B树的特性包括：

1. 每个节点包含多个键：每个节点至少包含 ⌈m/2⌉−1个键，至多包含 m−1 个键，m 为B树的阶数。
2. 所有叶子节点在相同深度：树的所有叶子节点处于同一深度。
3. 平衡性：插入和删除操作保持树的平衡。

B+树（B-Plus Tree）

B+树是B树的一种变体，具有以下特点：

1. 叶子节点链表：所有叶子节点通过链表相连，形成一个有序链表。
2. 非叶子节点只存储键：非叶子节点不存储数据，只存储键和子节点指针，数据仅存储在叶子节点中。
3. 更高的节点分支因子：因为非叶子节点只存储键，B+树相对于同阶的B树可以存储更多的键，从而减少树的高度。

对比

特性	B树	B+树
节点存储	键和数据	内部节点存储键，叶子节点存储数据
键的数量	⌈m/2⌉−1到 m−1	⌈m/2⌉−1到 m−1
子节点指针数量	⌈m/2⌉ 到 m	⌈m/2⌉ 到 m
数据存储位置	内部节点和叶子节点	仅在叶子节点
叶子节点链表	不存在	存在（叶子节点通过链表连接）
查询效率	O(logmN)，从根节点到叶子节点	O(logmN)，从根节点到叶子节点
插入/删除操作	相对复杂，需要调整节点	相对复杂，需要调整叶子节点链表和节点
范围查询效率	较差，需要遍历多个节点	优秀，叶子节点通过链表有序连接
顺序访问	较差，需要中序遍历树	优秀，通过链表遍历叶子节点
空间利用率	较高	较高，叶子节点存储更多数据
适用场景	频繁插入、删除操作	高效范围查询、顺序访问、数据库索引

B树：

• 适用于需要频繁插入和删除操作的场景。
• 数据既存储在内部节点也存储在叶子节点。
• 查询和更新操作效率较高，但范围查询和顺序访问效率较低。

B+树：

• 适用于需要高效范围查询和顺序访问的场景。
• 数据仅存储在叶子节点，内部节点只存储键。
• 叶子节点通过链表连接，提高了范围查询和顺序访问的效率。

为什么MySQL选择B+树

1. 磁盘I/O效率

数据库检索的效率很大程度上取决于磁盘I/O操作的效率。B+树的结构有利于减少磁盘I/O操作：

• 叶子节点链表：B+树的所有叶子节点通过链表相连，支持顺序访问。当进行范围查询时，只需在链表中遍历叶子节点即可，大大提高了范围查询的效率。
• 更高的节点分支因子：由于非叶子节点只存储键，B+树可以在同样大小的节点中存储更多的键和子节点指针，从而减少树的高度。更少的高度意味着在检索时需要更少的磁盘I/O操作。

2. 更稳定的查询性能

B+树的查询性能更加稳定，尤其是在范围查询和排序操作中表现突出：

• 范围查询：B+树的叶子节点通过链表相连，进行范围查询时只需遍历链表，性能较为稳定。
• 排序：B+树的叶子节点本身是有序的，支持高效的排序操作。

3. 更高的空间利用率

B+树的空间利用率更高，因为它将数据仅存储在叶子节点中，而非叶子节点只存储键和指针。相比之下，B树的每个节点都存储数据和指针，导致空间利用率较低。

4. 并发控制

B+树的结构有助于提高并发控制能力：

• 分裂和合并操作：在插入和删除操作时，B+树的分裂和合并操作相对简单且对树的结构影响较小，这有助于提高并发操作的性能和稳定性。

与 B 树相比，B+树具有以下优点：

• 更矮胖的树: B+树的非叶子结点不存储数据，因此可以存储更多的索引，从而使树更加矮胖。这使得查询数据时需要访问的树的层数更少，从而提高查询效率。
• 更快的范围查询: B+树的叶子结点按关键字顺序存储，并且相邻的叶子结点之间有指针相连，因此可以很有效地支持范围查询。

B树与B+树比较

• B+树层级更少，查找更快
• B+树查询速度稳定：由于B+树所有数据都存储在叶子节点，所以查询任意数据的次数都是树的高度h
• B+树有利于范围查找
• B+树全节点遍历更快：所有叶子节点构成链表，全节点扫描，只需遍历这个链表即可
• B树优点：如果在B树中查找的数据离根节点近，由于B树节点中保存有数据，那么这时查询速度比B+树快。

其他树结构的比较

虽然B+树在数据库索引中表现优异，但了解其他树结构的优缺点也有助于全面理解数据库索引的选择：

• AVL树：AVL树是一种高度平衡的二叉搜索树，每次插入和删除操作都会导致旋转，以保持平衡。虽然AVL树的查找效率高，但由于频繁的旋转操作，其插入和删除效率较低，不适合频繁更新的数据库环境。
• 红黑树：红黑树是一种自平衡的二叉搜索树，通过颜色标记节点并进行旋转操作来保持平衡。红黑树的插入和删除效率高于AVL树，但由于其二叉结构，相对于多叉树的B+树，磁盘I/O效率较低。

各种树解决的问题以及面临的新问题

• 二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；

• 平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低；

• 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；

• B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题；

• B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。

MySQL选择B+树作为索引结构是基于其在磁盘I/O效率、查询性能、空间利用率和并发控制等方面的优势。B+树通过将数据存储在叶子节点并使用链表连接叶子节点，实现了高效的范围查询和排序操作，同时减少了磁盘I/O操作的次数，提供了稳定的查询性能。这些特点使得B+树成为MySQL数据库索引的首选结构。

参考

• 知乎 - MySQL 为什么使用 B+ 树来作索引？
• Github - B树和B+树详解