MySQL为什么使用B+树？B+树和B树的区别

在数据库系统中，索引是提高数据检索效率的关键技术。MySQL 默认使用 B+树 作为索引的数据结构，而不是 B 树或其他数据结构。这是因为 B+树在范围查询、磁盘 I/O 效率以及数据存储方式等方面具有显著优势。

---

B+树和 B 树的区别

B+树和 B 树都是平衡多路搜索树，但它们在设计上有一些关键差异，这些差异直接影响了它们在数据库中的应用。

1. 数据存储位置

• B 树:
  • 每个节点（包括非叶子节点和叶子节点）都存储数据（索引 + 记录）。
  • 数据分布在整棵树的各个节点中。
• B+树:
  • 只有叶子节点存储实际数据（索引 + 记录），非叶子节点仅存储索引（键值）。
  • 数据集中在叶子节点，非叶子节点仅用于导航。

2. 叶子节点的结构

• B 树:
  • 叶子节点和非叶子节点的结构相同，都存储数据。
  • 叶子节点之间没有直接链接。
• B+树:
  • 叶子节点之间通过指针连接，形成一个有序链表。
  • 这种结构使得范围查询更加高效。

3. 索引的重复性

• B 树:
  • 非叶子节点的索引只出现一次，不会在子节点中重复出现。
• B+树:
  • 非叶子节点的索引会重复出现在子节点中，并且是子节点中所有索引的最大值（或最小值）。

4. 节点子节点与索引的关系

• B 树:
  • 非叶子节点的子节点数量比索引数量多 1。
• B+树:
  • 非叶子节点中有多少个子节点，就有多少个索引。

---

MySQL 为什么使用 B+树？

MySQL 选择 B+树作为索引结构的主要原因在于其高效的范围查询能力、磁盘 I/O 优化以及更适合数据库场景的设计。

1. 范围查询的高效性

• B+树:
  • 叶子节点之间通过指针连接，形成一个有序链表。
  • 当进行范围查询时（如 WHERE id BETWEEN 10 AND 100），只需要找到起始位置的叶子节点，然后沿着链表顺序遍历即可。
  • 这种设计使得范围查询的时间复杂度接近 O(log n + m)，其中 n 是索引数量，m 是范围查询的结果数量。
• B 树:
  • 由于数据分布在所有节点中，范围查询需要多次中序遍历整棵树，效率较低。

2. 磁盘 I/O 优化

• B+树:
  • 非叶子节点仅存储索引，不存储实际数据，因此每个节点可以存储更多的键值。
  • 这使得 B+树的层数更少，查询时需要访问的磁盘块更少，减少了磁盘 I/O 次数。
• B 树:
  • 每个节点都存储数据，导致节点能存储的键值较少，树的高度较高，查询时需要更多的磁盘 I/O。

3. 更适合数据库场景

• B+树:
  • 数据集中在叶子节点，非叶子节点仅用于导航，这种设计非常适合数据库的索引需求。
  • 叶子节点的有序链表结构非常适合范围查询和排序操作，而这些操作在数据库中非常频繁。
• B 树:
  • 数据分布在整个树中，适合随机查询，但在范围查询和排序操作上效率较低。

4. 更高的空间利用率

• B+树:
  • 非叶子节点不存储实际数据，可以存储更多的索引，空间利用率更高。
• B 树:
  • 每个节点都存储数据，空间利用率较低。

---

B+树和 B 树的对比总结

特性	B 树	B+树
数据存储位置	所有节点都存储数据	只有叶子节点存储数据
叶子节点结构	叶子节点之间没有链接	叶子节点通过指针连接，形成有序链表
范围查询效率	较低，需要中序遍历整棵树	较高，只需遍历叶子节点链表
磁盘 I/O 次数	较多，树的高度较高	较少，树的高度较低
空间利用率	较低，每个节点都存储数据	较高，非叶子节点仅存储索引
适用场景	适合随机查询	适合范围查询和排序操作

---

示例说明

假设有一个包含 100 万条记录的表，字段 id 是主键，使用 B+树索引。

1. 查询单个记录:

   • 通过 B+树的索引结构，可以快速定位到叶子节点，时间复杂度为 O(log n)。
   • 由于 B+树的层数较少，磁盘 I/O 次数也较少。

2. 范围查询:

   • 查询 WHERE id BETWEEN 1000 AND 2000：
     • 首先找到 id = 1000 的叶子节点。
     • 然后沿着叶子节点的链表顺序遍历，直到 id = 2000。
   • 这种操作非常高效，因为不需要回溯到非叶子节点。

---