[面试题] 从 InnoDB 的索引结构分析，为什么索引的 key 使用 B+ 树？

📖 版块 A：知识讲解版 (温故知新)

• B+ 树的核心特征：

  1. 非叶子节点只存键值和指针：不存储实际的行数据（Data）。这使得单个节点（页）能容纳更多的键值，从而产生更大的“扇出”（Fan-out）。
  2. 叶子节点存储所有数据：所有数据都在同一层，查询路径长度固定。
  3. 叶子节点之间有双向链表：在叶子节点层级形成了逻辑上的有序序列。

• 对比其他数据结构的劣势：

  1. Hash 索引：虽然等值查询快（O(1)），但不支持范围查询、排序和模糊匹配（like ‘abc%’）。
  2. 二叉搜索树 / 红黑树：由于每个节点最多只有两个子节点，当数据量大时，树的高度会非常高。由于索引存储在磁盘上，树的高度直接决定了磁盘 I/O 的次数。
  3. B 树（B-Tree）：其非叶子节点也会存储 Data。这意味着在相同的 16KB 页面大小下，B 树每个节点能存储的 Key 数量远少于 B+ 树。为了存储相同量级的数据，B 树的高度会比 B+ 树更高，且 B 树在进行范围查询时需要频繁地进行中序遍历。

🎤 版块 B：面试实战版 (高手逐字稿)

Q：从 InnoDB 的索引结构分析，为什么索引的 key 使用 B+ 树？

💬 高手逐字稿：

关于 InnoDB 选择 B+ 树作为索引结构，我认为最核心的原因在于：它是磁盘 I/O 效率与多维度查询需求（等值、范围、排序）权衡后的最优解。

我们可以从以下三个维度来拆解：

首先是查询效率的稳定性与磁盘 I/O 的优化。在数据库中，索引是存在磁盘上的，而磁盘 I/O 是最大的性能瓶颈。B+ 树相比于 B 树，最大的区别在于非叶子节点只存储 Key 和指针，不存储 Data。这带来的直接好处是：一个 16KB 的物理页可以存放更多的索引键。这就大幅提升了“扇出”率，降低了树的高度。在实际生产中，一个 3 到 4 层的 B+ 树就能支撑千万级甚至亿级的数据量，这意味着定位一行数据通常只需要 3 到 4 次磁盘 I/O。

其次是对范围查询和排序的天然支持。在业务开发中，我们经常会用到 BETWEEN、> 或者 ORDER BY。B+ 树的所有叶子节点通过双向链表连接，并且是逻辑有序的。当我们需要范围查询时，只需要先定位到起始位置的叶子节点，然后顺着链表向后遍历即可，不需要像 B 树那样去反复进行中序遍历和跨层访问，这极大地减少了随机 I/O。

最后是相比于 Hash 索引的普适性。虽然 Hash 索引在等值查询上更快，但它无法处理范围扫描、模糊查询以及多列联合索引的最左匹配。B+ 树作为一个有序结构，能够完美支持这些场景。

这里可以深挖一个细节： 很多人会忽略一个点，就是 B+ 树的查询效率其实比 B 树更稳定。因为在 B 树中，如果运气好，可能在根节点就找到了数据；如果运气不好，要去叶子节点。这种波动在高并发系统下会导致响应时间的抖动。而 B+ 树的所有查询最终都会下沉到叶子节点，这种“固定”的路径长度保证了每个 SQL 执行耗时的稳定性。

如果我们粗略估算一下：InnoDB 的非叶子节点中，一个指针加一个长整型 Key 大约占用 14 字节，那么一个 16KB 的页可以容纳超过 1000 个键值。即便树只有 3 层，它的承载能力也是 1000 的 3 次方，也就是 10 亿级别。这种极高的空间利用率是 B+ 树成为关系型数据库首选结构的根本原因。