⭐ 题目日期：

小米 - 2024/12/26

📝 题解：

InnoDB 存储引擎使用的是 B+树（B+ Tree） 作为索引结构，而非传统的 B树（B-Tree）。尽管 B树 和 B+树 在名称和基础结构上相似，但 B+树 针对数据库场景做了优化，具体原因如下：

---

1. B+树与B树的核心区别

• B树：
  • 每个节点（包括内部节点和叶子节点）既存储键（Key）也存储数据（Data）。
  • 查找可能在任意层级的节点命中数据，无需遍历到叶子节点。
• B+树：
  • 只有叶子节点存储数据，内部节点仅存储键（作为导航）。
  • 叶子节点通过指针串联成有序链表，支持高效的范围查询。
  • 所有数据查询必须走到叶子节点。

---

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

(1) 更少的磁盘I/O（关键优势）

• B+树的内部节点不存储数据，可以容纳更多键值，从而降低树的高度（减少层级）。
• 例如，一个 3 层的 B+树 可以存储千万级数据，而同样数据量的 B树 可能需要更多层级。
• 树的高度越低，查询时的磁盘I/O次数越少（数据库性能瓶颈主要在于磁盘I/O）。

(2) 范围查询的高效性

• B+树的叶子节点通过链表连接，范围查询（如 WHERE id BETWEEN 10 AND 20）只需遍历链表，无需回溯上层节点。
• 而 B树 的范围查询需要多次中序遍历，效率较低。

(3) 全表扫描更高效

• B+树的所有数据都存储在叶子节点，且叶子节点有序，全表扫描只需遍历叶子节点链表。
• B树 的数据分散在各层节点，全表扫描需要遍历整棵树。

(4) 更适合事务和锁机制

• InnoDB 支持行级锁和 MVCC（多版本并发控制），B+树的叶子节点存储完整数据（聚簇索引），锁定单行时可直接在叶子节点加锁。
• B树 的数据分散在各层，锁管理复杂度更高。

(5) 更适合覆盖索引

• B+树的非聚簇索引（二级索引）的叶子节点直接存储主键值，回表查询更高效。
• 例如，若查询的列都在索引中（覆盖索引），可直接从叶子节点获取数据，无需二次查找。

---

3. B树的潜在劣势

• 空间利用率低：B树 的每个节点需要存储键和数据，相同磁盘页能容纳的键更少，树的高度可能更高。
• 范围查询成本高：B树 的范围查询需要多次访问不同层级的节点，而 B+树 只需线性遍历叶子链表。
• 锁竞争更激烈：B树 的数据分散在各层，高并发时锁粒度难以细化。

---

4. 总结：B+树是数据库索引的最优解

特性	B树	B+树
数据存储位置	所有节点存储数据	仅叶子节点存储数据
范围查询效率	低（需中序遍历）	高（线性遍历叶子链表）
树的高度	较高（相同数据量）	较低
全表扫描效率	低	高
适合场景	内存型数据库、单一查询	磁盘型数据库、范围查询

对于 InnoDB 这类面向磁盘存储、高并发事务处理的引擎，B+树 在 减少I/O次数、优化范围查询、支持事务和锁机制 等方面的优势更加突出，因此成为默认选择。

---

附加：InnoDB索引的其他特性

1. 聚簇索引（Clustered Index）：
   • 主键索引的叶子节点直接存储行数据，表数据按主键顺序物理存储。
   • 若未定义主键，InnoDB 会自动生成隐藏的聚簇索引。
2. 二级索引（Secondary Index）：
   • 叶子节点存储主键值，查询时需要回表到聚簇索引获取完整数据。

---

结论：B+树 通过牺牲部分单次查询的理论性能（必须走到叶子节点），换取了整体系统的稳定性和高效性，完美契合数据库的磁盘I/O优化和复杂查询需求。