[每周一更]-(第99期)：MySQL的索引为什么用B+树？
文章目录
- B树与B+树的基本概念
- B树（Balanced Tree）
- B+树（B-Plus Tree）
- 对比
- 为什么MySQL选择B+树
- 1. **磁盘I/O效率**
- 2. **更稳定的查询性能**
- 3. **更高的空间利用率**
- 4. **并发控制**
- 其他树结构的比较
- 参考
索引是一种 数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。MySQL索引有三类：B+树索引、Hash索引、全文索引
在数据库系统中，索引是提高数据检索效率的关键工具。而在MySQL中，B+树索引是最常用的一种索引结构。理解为什么MySQL选择使用B+树而不是B树或其他树结构，首先需要深入了解B+树和B树的特性及其在数据库检索中的表现。
B树与B+树的基本概念
B树（Balanced Tree）
B树是一种自平衡的多叉树数据结构，其中每个节点可以包含多个子节点和键。B树的每个节点都包含键和子节点指针，叶子节点不需要保持在同一层。
B树的特性包括：
- 每个节点包含多个键：每个节点至少包含 ⌈m/2⌉−1个键，至多包含 m−1 个键，m 为B树的阶数。
- 所有叶子节点在相同深度：树的所有叶子节点处于同一深度。
- 平衡性：插入和删除操作保持树的平衡。
B+树（B-Plus Tree）
B+树是B树的一种变体，具有以下特点：
- 叶子节点链表：所有叶子节点通过链表相连，形成一个有序链表。
- 非叶子节点只存储键：非叶子节点不存储数据，只存储键和子节点指针，数据仅存储在叶子节点中。
- 更高的节点分支因子：因为非叶子节点只存储键，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+树详解