在数据库系统中，索引是提升查询性能的关键技术之一。MySQL作为最流行的关系型数据库之一，选择了B+树作为其默认的索引结构。那么，为什么MySQL会选择B+树？本文将从B+树的设计原理、实际应用场景以及与其他索引结构的性能对比等方面，深入解析B+树的优势与性能。

1. B+树的基本结构

B+树是一种平衡多路搜索树，具有以下特点：

• 平衡性：所有叶子节点位于同一层，保证了查询的稳定性。
• 多路分支：每个节点可以包含多个子节点，减少了树的高度。
• 叶子节点链表：所有叶子节点通过指针连接，支持高效的范围查询和顺序访问。

B+树的节点分为内部节点和叶子节点：

• 内部节点：存储键值和指向子节点的指针。
• 叶子节点：存储键值和实际的数据指针（或数据本身）。

2. 为什么MySQL选择B+树？

2.1 高效的查询性能

B+树的查询时间复杂度为O(log n)，其中n是索引键的数量。由于B+树是多路平衡树，其高度通常较低，即使在数据量非常大的情况下，查询性能依然稳定。

实际场景：
假设一个表中有1亿条记录，如果使用二叉搜索树（BST），树的高度可能达到27层（log10 ≈ 26.57），而B+树的分支因子通常为几百，树的高度可能只有3-4层。这意味着B+树只需要3-4次磁盘I/O即可完成查询，而BST可能需要27次。

2.2 适合磁盘I/O优化

数据库系统通常需要将数据存储在磁盘上，而磁盘I/O是性能的主要瓶颈。B+树的节点大小通常与磁盘块大小（如4KB）匹配，能够最大限度地利用每次磁盘I/O读取的数据量。

实际场景：
假设一个B+树的节点大小为4KB，每个键值占8字节，指针占8字节，那么一个节点可以存储大约250个键值和指针。相比之下，二叉搜索树每个节点只能存储一个键值和两个指针，导致更多的磁盘I/O。

2.3 支持范围查询

B+树的叶子节点通过指针连接成一个有序链表，非常适合范围查询（如BETWEEN、>、<等操作）。

实际场景：
假设需要查询一个订单表中2023年1月1日到2023年12月31日的所有订单：

SELECT * FROM orders WHERE order_date BETWEEN '2023-01-01' AND '2023-12-31';

B+树可以快速定位到起始键值，然后通过叶子节点的链表顺序访问所有符合条件的记录。而哈希索引等结构无法高效支持范围查询。

2.4 更适合大数据量

B+树的层数较低，能够有效减少树的深度，适合处理大规模数据。

实际场景：
在一个包含10亿条记录的表中，B+树的高度可能只有4层，而红黑树等平衡二叉搜索树的高度可能达到30层。这意味着B+树的查询性能更加稳定。

3. B+树与其他索引结构的性能对比

3.1 B+树 vs 二叉搜索树（BST）

案例：
在一个包含1亿条记录的表中，B+树的查询可能需要3-4次磁盘I/O，而BST可能需要27次。

3.2 B+树 vs 哈希索引

案例：
哈希索引在等值查询（如WHERE id = 123）时性能优于B+树，但在范围查询时无法使用。例如：

SELECT * FROM users WHERE age BETWEEN 20 AND 30;

B+树可以高效完成，而哈希索引无法支持。

3.3 B+树 vs B树

案例：
在范围查询场景中，B+树通过叶子节点的链表可以快速遍历，而B树需要回溯到父节点，效率较低。

4. 实际应用中的性能表现

以下是一个实际测试案例，对比B+树和哈希索引在查询性能上的差异：

测试环境：

• 数据量：1亿条记录
• 查询类型：
• 等值查询：SELECT * FROM table WHERE id = 12345678;
• 范围查询：SELECT * FROM table WHERE value BETWEEN 1000 AND 2000;

测试结果：

从结果可以看出，哈希索引在等值查询上略优于B+树，但在范围查询上完全无法使用。而B+树在两种查询场景下均表现良好。

5. 总结

MySQL选择B+树作为索引结构的原因可以归结为以下几点：

1. 高效的查询性能：B+树的多路分支和平衡性保证了稳定的查询效率。
2. 适合磁盘I/O优化：节点大小与磁盘块匹配，减少了磁盘I/O次数。
3. 支持范围查询：叶子节点的链表结构非常适合范围查询。
4. 适合大数据量：较低的树高度使其能够高效处理大规模数据。

通过实际场景和性能对比可以看出，B+树在通用性和性能上均优于其他索引结构，这也是MySQL选择B+树作为默认索引结构的主要原因。