为什么 InnoDB 选择 B+树作为索引结构？

知识点图片

InnoDB 存储引擎选择 B+树 作为其底层的索引数据结构，是经过对磁盘I/O特性、数据库查询模式（等值查询、范围查询）以及存储效率进行深度权衡后的必然结果。

要理解为什么选 B+树，最清晰的方法是看看为什么不选其他数据结构，以及 B+树到底解决了什么核心痛点。

数据库的数据是存在磁盘上的。相比于内存，磁盘读取非常慢。操作系统和数据库引擎在读取磁盘时，为了提高效率，通常按“块”或“页（Page）”来读取（InnoDB 默认一页为 16KB）。
索引设计的终极目标就是：在查找数据时，尽量减少磁盘的 I/O 次数。

哈希表（Hash Table）
- 优点：等值查询（=，IN）极快，时间复杂度 $O(1)$ 。
- 致命缺点：不支持范围查询（>，<，BETWEEN）和排序。因为哈希计算后数据是无序散列的，而数据库中有大量的范围查询。
二叉查找树（BST） / 红黑树（Red-Black Tree）
- 优点：支持等值查询和范围查询。
- 致命缺点：树太高了，导致磁盘 I/O 次数过多。这两种树每个节点最多只有 2 个子节点（扇出极低）。如果表里有 1000 万条数据，红黑树的高度可能达到 20 多层。这意味着查找一条数据可能需要 20 多次磁盘 I/O，这对于数据库是灾难性的。

为了解决“树太高”的问题，引入了多路平衡查找树（B树）。B树的一个节点可以容纳多个子节点，树变矮了。但 InnoDB 依然没有选择 B树，而是选择了它的升级版 B+树。

B树和 B+树的核心区别在于：

InnoDB 选择 B+树而非 B树的原因如下：

InnoDB 的一个节点（一页）大小固定为 16KB。
在 B树中，因为非叶子节点也要存 Data，导致一个 16KB 的页能存放的 Key 的数量很少。
在 B+树中，非叶子节点只存 Key（如 BigInt 占 8 字节）和指针（6 字节），一个 16KB 的页可以存放大约 1000 多个指针。
数学威力：如果一棵 B+树高度为 3，第一层 1 个节点，第二层 1000 个节点，第三层（叶子节点）1000 × 1000 = 100 万个节点。每个叶子节点若存 16 条记录，只需 3 次磁盘 I/O，就能在 1600 万条数据中找到目标数据。B树要达到同样的容量，树的高度会远大于 3。

在 B树中：如果要查询 10 到 20 之间的数据，由于数据分散在各个节点，需要在树的各个层级之间进行中序遍历，跨节点跳跃，会导致极其频繁的随机磁盘 I/O。
在 B+树中：所有叶子节点形成了一个有序链表（InnoDB 实现为双向链表）。如果要查询 10 到 20 的数据，只需要从根节点快速定位到 10 所在的叶子节点，然后顺着链表指针向后遍历即可，非常适合范围查询、排序和分页，且大多是顺序 I/O。

InnoDB 存储引擎的设计与 B+树完美契合，具体体现在它的聚簇索引（Clustered Index）机制上：

数据即索引，索引即数据：InnoDB 的主键索引就是一棵完整的 B+树，它的叶子节点里直接存放了整行数据（Row Data）。
辅助索引（二级索引）：辅助索引也是 B+树，但它的叶子节点存放的是主键的值。查询时先在辅助索引找到主键，再去主键 B+树中查数据（这个过程叫回表）。
页和链表：InnoDB 将 B+树的同层节点用双向链表连接，页内记录用单向链表连接，极大地优化了磁盘的顺序读取。

一句话概括：
InnoDB 选择 B+树，是因为它能用最矮的树高（最少的磁盘 I/O）容纳海量数据，同时通过叶子节点链表完美解决了关系型数据库中刚需的范围查询问题。

播面