面试官：为什么 MySQL 索引底层使用的是 B+ 树，而不是 B 树或红黑树？
面试回答
“MySQL 选择 B+ 树作为索引的底层数据结构，核心是为了减少磁盘 I/O 次数并高效支持范围查询。
首先，为什么不用红黑树或二叉查找树？因为红黑树是二叉树，每个节点最多只有两个子节点。当数据量达到千万级时，树的高度会非常高（几十层），这意味着一次查询可能需要几十次磁盘 I/O，性能极差。而 B+ 树是多叉树，一个节点（即一个磁盘页）可以容纳上千个键值，千万级的数据只需 3 到 4 层就能存下，查询时最多只需要 3-4 次磁盘 I/O。
其次，为什么不用普通的 B 树？B 树的非叶子节点不仅存键值，还存具体的数据。这会导致一个节点能存放的键值数量大大减少，树的高度变高，增加磁盘 I/O。而 B+ 树的非叶子节点只存键值（索引），所有数据都放在叶子节点，这样单个节点能容纳更多索引，树更矮更胖。
最后，B+ 树的叶子节点之间用双向链表连接了起来。在数据库中，范围查询（比如 WHERE age > 18 AND age < 30）非常频繁。B+ 树只需要找到起始节点，然后顺着链表遍历即可；而 B 树则需要进行复杂的中序遍历，跨越多个节点，产生大量的随机磁盘 I/O。因此，B+ 树是最适合关系型数据库磁盘存储的数据结构。”
系统讲解
在数据库系统中，磁盘 I/O 是最大的性能瓶颈。评价一个数据结构是否适合做数据库索引，核心标准就是：在海量数据下，能否用最少的磁盘 I/O 次数找到数据，并且是否支持高效的范围查询。
核心对比
| 数据结构 | 树的形态 | 数据存储位置 | 范围查询性能 | 磁盘 I/O 次数 | 适用场景 |
|---|---|---|---|---|---|
| 红黑树/二叉树 | 瘦高（二叉） | 所有节点 | 差（需中序遍历） | 极高（） | 内存数据结构（如 Java 的 TreeMap） |
| B 树 | 矮胖（多叉） | 所有节点 | 较差（需中序遍历） | 较低（） | 文件系统、部分非关系型数据库 |
| B+ 树 | 更矮胖（多叉） | 仅叶子节点 | 极好（叶子节点有链表） | 极低（通常 3-4 次） | 关系型数据库（如 MySQL InnoDB） |
1. 为什么不是红黑树？（树的高度问题）
红黑树是一种自平衡二叉查找树。它的特点是每个节点最多只有两个分支。
- 问题：在千万级数据量下，红黑树的高度会达到 20-30 层。由于数据库索引存储在磁盘上，树的每一层通常对应一次磁盘 I/O。几十次磁盘 I/O 需要几十毫秒，这在数据库查询中是不可接受的。
- B+ 树的优势：B+ 树是多路平衡查找树（多叉树）。InnoDB 存储引擎中，一个页（Page）的默认大小是 16KB。如果主键是
BIGINT（8字节），指针大小是 6字节，那么一个 16KB 的非叶子节点可以存放约 1170 个索引键（）。一棵高度为 3 的 B+ 树，就能支撑 （假设叶子节点单条记录 1KB，每页存 16 条） 万条数据。千万级数据只需 3 次磁盘 I/O。
2. 为什么不是 B 树？（节点容量与范围查询）
B 树（B-Tree）也是多叉树，但它与 B+ 树有两个致命区别：
- 节点容量与树高：B 树的非叶子节点不仅存储索引键，还存储该行的数据（Data）。如果一行数据有 1KB，那么一个 16KB 的节点只能放 16 条记录。这会导致节点的“扇出（Fanout）”极速下降，树的高度重新变高，从而增加磁盘 I/O 次数。而 B+ 树非叶子节点只存键值，极其紧凑。
- 范围查询效率：B 树的节点之间没有链接。如果要执行
SELECT * FROM table WHERE id BETWEEN 10 AND 100，B 树需要做繁琐的树的中序遍历，在不同的磁盘页之间来回跳转（随机 I/O）。而 B+ 树的所有叶子节点形成了一个双向有序链表，只需通过索引找到id=10的叶子节点，然后顺着链表顺序读取（顺序 I/O），直到id=100即可，效率极高。
亮点与深度
磁盘预读与局部性原理
B+ 树的设计完美契合了操作系统的磁盘局部性原理（空间局部性）。操作系统从磁盘读取数据时，并非按需读取，而是按页（通常是 4KB 或 8KB）进行预读。InnoDB 将 B+ 树的节点大小设置为 16KB，每次加载一个节点，正好利用了磁盘的顺序读特性，将相关联的索引键一次性加载到内存中。
常见追问
追问 1：为什么不用 Hash 索引？ Hash 索引的单次查询速度极快，时间复杂度为 。但它有两个致命缺点：
- 不支持范围查询：Hash 函数会将相邻的键散列到完全不同的位置，无法执行
id > 10这样的查询。 - 不支持排序：无法用于
ORDER BY。 - 哈希冲突：数据量大时冲突严重。 注：InnoDB 内部有“自适应哈希索引（Adaptive Hash Index）”机制，对于频繁访问的 B+ 树页，会自动在内存中构建 Hash 索引来加速等值查询，但这属于内存优化，底层持久化结构仍是 B+ 树。
追问 2：B+ 树能无限存数据吗？树高一般是多少？ 不能。通常建议单表数据量控制在 2000 万左右。因为当数据量超过 2000 万时，B+ 树的高度可能会从 3 层增加到 4 层，或者由于数据量过大导致内存 Buffer Pool 无法缓存足够多的非叶子节点，进而导致磁盘 I/O 显著增加。实际树高通常在 2-4 层之间。