★ MySQL 为什么选用 B+Tree 作为索引结构？
结论先行：InnoDB 索引底层是 B+Tree。选它而非哈希、红黑树或 B 树，是因为 B+Tree 层数矮、叶子节点有序串联，能用最少的磁盘 I/O 完成定位与范围查询。
一、先排除其它结构
| 结构 | 等值查询 | 范围查询 | 磁盘友好度 | 为什么不适合做主索引 |
|---|---|---|---|---|
| 哈希表 | O(1) | 不支持 | 一般 | 只能等值命中，无法排序与范围扫描 |
| 二叉搜索树 | O(logN) | 支持 | 差 | 数据量大时树高陡增，I/O 次数多 |
| 红黑树 | O(logN) | 支持 | 差 | 千万级数据树高约 20+，读盘太多 |
| B 树 | O(logN) | 一般 | 较好 | 非叶子也存数据，单页能容纳的 key 少 |
| B+Tree | O(logN) | 优秀 | 最好 | —— 最终选择 |
二、B+Tree 胜出的四个点
- 矮：非叶子节点只存索引 key 与指针，一个 16KB 页可存上千 key，三层即可支撑千万级数据。
- 有序：叶子节点按 key 升序排列并用双向链表相连，范围查询、排序、分组都走顺序扫描。
- 稳定：所有查询都要走到叶子层，路径等长，单条 SQL 耗时波动小，便于预估。
- 冗余：key 全部冗余在叶子，非叶子只是路标，配合聚簇索引还能减少回表。
- 预读友好：页内 key 连续存放，磁盘按页预读，顺序扫描吞吐更高。
三、InnoDB 中两类 B+Tree
聚簇索引(主键) 叶子节点 = 完整行记录，一张表只有一个
二级索引(普通) 叶子节点 = 索引列 + 主键值，可建多个
四、与磁盘 I/O 的关系
一次页读取 ≈ 一次磁盘 I/O
层数 = 定位一条记录必须的磁盘 I/O 次数
3 层 B+Tree ≈ 3 次 I/O 即可找到叶子页
常见追问与记忆点
- 追问：为什么不用跳表？跳表更适合内存场景（如 Redis），磁盘场景更看重页预读与顺序 I/O。
- 追问：页大小能改吗？能（innodb_page_size），改小树会变高，生产环境默认 16KB。
- 记忆点：B+Tree = 矮 + 胖 + 叶子有序链表，用少量冗余换更少磁盘 I/O 与更好的范围扫描。