引言

"你说你熟悉 MySQL 索引，那我问你：索引为什么用 B+ 树？" 这是后端面试的经典开场。很多候选人的回答是"B+ 树查询快"——这个答案等于没说，哈希表查询 O(1) 岂不是更快？也有人答"B+ 树是平衡树"——红黑树也是平衡树，为什么不用？当面试官追问"那 B 树呢，B+ 树到底比 B 树强在哪"，大部分人就卡住了。

这个问题答不好，不是因为 B+ 树有多难，而是思考顺序错了：一上来就背 B+ 树的特点，却没有先回答"数据库索引的约束条件是什么"。答案的第一性原理其实只有一句话：磁盘随机 IO 极贵，索引结构的唯一设计目标，就是用最少的磁盘读取次数找到数据。理解了这一句，哈希、红黑树、B 树为什么落选，B+ 树为什么胜出，全部可以自己推导出来，根本不用背。这篇文章就从磁盘 IO 的成本讲起，把四种结构放在同一个标尺下一较高低，最后给出 InnoDB 里的真实数字和面试回答话术。

一、先立标尺：一次磁盘随机 IO 到底有多贵

1.1 数字说话

把机械盘的 10ms 等比放大成体感时间：如果 CPU 读一次内存（100ns）是你低头看一眼手表（1 秒），那么一次磁盘随机 IO（10ms）就是 约 28 小时——出差一趟的时间。这就是《Systems Performance》里著名的"延迟数字"给人的冲击：CPU 和磁盘之间差了约 10 万倍。

SSD 时代随机读快了几十倍（0.1ms 级），但结论没变：即使是 NVMe SSD，随机读仍比内存访问慢约 1000 倍；而且数据库读磁盘的最小单位不是一条记录，是一个页（InnoDB 默认 16KB）——一次随机 IO 的成本是固定的，读一页和读一条记录花的时间几乎一样。

1.2 由此推出索引结构的三条硬约束

约束 1：树的高度决定 IO 次数 → 树必须"矮胖"，不能"高瘦"
        每下一层大概率触发一次磁盘 IO（根页在内存时少一次）
        树高 3 和树高 30，差距就是 3 次 IO（~30ms）vs 30 次 IO（~300ms）

约束 2：每读一个页要尽量"值回票价" → 一个 16KB 页里容纳的导航信息越多，
        一次 IO 能排除的数据范围就越大（扇出 fan-out 要大）

约束 3：业务查询不只有等值，还有范围（WHERE id BETWEEN 100 AND 200）、
        排序（ORDER BY）、前缀（LIKE 'abc%'） → 数据在叶子层必须物理有序

接下来四个候选结构，全部用这三条标尺衡量。

二、哈希索引：等值查询的王者，范围查询的废柴

2.1 优势：O(1) 的等值查询

哈希索引对索引列算哈希值，映射到桶数组的某个槽位，等值查询一次哈希定位：

WHERE id = 10086
  → hash(10086) = 73
  → 直接定位桶 73 → 找到记录
  → 理想情况 1 次 IO，比任何树都快

2.2 致命伤：哈希之后，顺序没了

哈希函数的本质是"均匀打乱"，id=10086 和 id=10087 的哈希值天差地别、在磁盘上的位置毫无关系。于是数据库最常见的另外半边天全塌了：

2.3 另外两个工程问题

• 哈希冲突：不同键映射到同桶要挂链表/开放寻址，冲突严重时退化成链表扫描，O(1) 变 O(n)，性能不稳定。
• 无法利用索引排序完成 ORDER BY：数据库无法靠哈希索引避免排序。

2.4 那 MySQL 里完全没有哈希索引吗？有，但只是配角

① Memory 引擎支持显式 HASH 索引（只适合临时表/字典表）
② InnoDB 的自适应哈希索引（AHI）：
   监控发现某些 B+ 树索引页被等值访问得特别频繁，
   自动在内存里为这些热点建哈希表——注意关键词：
   "自动""等值热点""内存里"，它是 B+ 树之上的加速器，不替代 B+ 树
③ 应用层自己用 Redis 哈希：那是 KV 缓存场景，不承担数据库的范围/排序职责

结论：哈希是"点查特化武器"，数据库需要的是"点查+范围+排序+前缀"全都要的通用结构，哈希第一张票出局。

三、红黑树（二叉平衡树）：单条查找很快，但树太"高"

3.1 红黑树本身很优秀

红黑树是自平衡二叉搜索树，Java 的 TreeMap、HashMap 链表转红黑树用的都是它。内存世界里它近乎完美：查找 O(log₂n)，增删通过旋转/染色保持平衡。

3.2 问题：二叉意味着扇出只有 2，高度压不下来

注意约束 1——磁盘场景里 O(log n) 是不够的，关键看 log 的底数：

红黑树/AVL：每个节点最多 2 个孩子，扇出 = 2
  存 1000 万条数据，树高 = log₂(10⁷) ≈ 24 层
  → 最坏情况约 24 次磁盘随机 IO
  → 机械盘：24 × 10ms = 240ms（一条 SQL！）
  → 100 并发就是灾难

红黑树是为内存比较设计的：每个节点存一个键+两个指针，一次节点访问在内存里是纳秒级，24 层无所谓。但把节点搬到磁盘页上，24 层就是 24 次页读取。而且二叉节点每个只存一个键，16KB 的页装一个节点——约束 2 也违反了：一次 IO 读 16KB，只用了其中几十字节的导航信息，极度浪费。

那能不能让每个磁盘页放很多二叉节点？可以（类似缓存优化的 BST 布局），但这本质上已经在向多路平衡树演化——干脆直接用多路树。

3.3 结论

二叉平衡树输在"扇出太小、层数太多"。要压低树高，思路很直接：让每个节点有更多孩子——这就是 B 树家族的出发点。

四、B 树：多路平衡解决了树高，但数据散在各层

4.1 B 树的进步：多路 + 矮胖

B 树（B-tree）是多路平衡查找树，一个节点（对应一个磁盘页）里放多个键、多个孩子指针：

[30 | 60]
           /    |    \
      [10,20] [40,50] [70,80]     ← 键和孩子都在节点内有序

假设一个页能放 100 个键：扇出 = 101，存 1000 万行树高 ≈ log₁₀₁(10⁷) ≈ 3.5 层——对比红黑树的 24 层，IO 次数从 24 次砍到 3~4 次。这就是多路树对磁盘的意义。

4.2 B 树的关键特征（也是和 B+ 树的分歧点）

B 树的所有节点都存完整数据行（或行指针），包括非叶子节点。查找路径可能在任何一层结束（命中根节点的键就直接返回，不用下到叶子）。

这带来两个问题：

问题 1：非叶子节点存数据 → 单页能放的键变少 → 扇出变小、树变高

一个 InnoDB 页 = 16KB
非叶子节点里一条记录 = 键 + 孩子指针(约6B) + 【数据行】
  如果数据行平均 500B：
    一个页大约只能放 16KB / 500B ≈ 32 条 → 扇出约 33
  B+ 树非叶子节点只存 键(8B) + 指针(6B) ≈ 14B：
    一个页能放 16KB / 14B ≈ 1170 条 → 扇出约 1170

同样存 2000 万行：
  B  树（扇出 33）：高度 ≈ log₃₃(2×10⁷) ≈ 4.8 → 5 层
  B+ 树（扇出1170）：高度 ≈ log₁₁₇₀(2×10⁷) ≈ 2.5 → 3 层

B 树不是不矮，但把宝贵的非叶子页空间花在存数据上，导航能力被稀释——违反约束 2。

问题 2：数据分散在所有层，叶子节点之间没有链表 → 范围查询要中序遍历整棵树

B 树范围查 id BETWEEN 100 AND 300：
  找到 100（可能在某叶子）→ 要"中序遍历"找后继
  → 后继可能在旁边的叶子，也可能要回到上层再下来
  → 树的多个层之间来回跳跃，产生大量随机 IO

B+ 树范围查：
  找到 100 所在叶子 → 沿叶子页内部的 next 指针顺序往后扫
  → 叶子在物理/逻辑上有序串联，几乎是顺序 IO

B 树的单条等值查找偶尔更快（命中上层即返回），但数据库是 OLTP 混合负载，范围扫描、全表/索引扫描非常普遍，B 树的这个优势换不来整体收益。

4.3 顺带破除一个常见误解

很多人以为"B 树是二叉树"——不是。B 树的 B 普遍认为代表 Bayer（发明者）或 Balanced，它从出生起就是多路平衡树。红黑树是二叉，B 树是多路，B+ 树是 B 树的变种，三者不是一回事。

五、B+ 树：为磁盘量身定做的最终答案

B+ 树在 B 树基础上做了三处针对性改造，每一刀都砍在前面四种结构的痛点上。

5.1 改造一：非叶子节点只存键，不存数据 → 扇出极大、树极矮

根页（只存导航键，约1170个）
        ┌──────────────┼──────────────┐
        ▼              ▼              ▼
   中间页（只存键） 中间页（只存键） 中间页（只存键）     ← 每层扇出 ~1170
   ┌──┼──┐        ┌──┼──┐        ┌──┼──┐
   ▼  ▼  ▼        ▼  ▼  ▼        ▼  ▼  ▼
 ┌─────────────────────────────────────────┐
 │ 叶子页：存全部索引键 + 完整数据行(聚簇)   │
 │ [键|行][键|行][键|行]... ⇄ ⇄ ⇄ ⇄ ...    │ ← 叶子之间双向链表
 └─────────────────────────────────────────┘

InnoDB 真实容量账（经典估算，bigint 主键 8B + 页内指针 6B ≈ 14B）：

非叶子页：16KB / 14B ≈ 1170 个导航条目
叶子页：  假设一行数据 1KB，一页放约 16 行

树高 2（根+叶子）：1170 × 16 ≈ 1.9 万行
树高 3（根+中间+叶子）：1170 × 1170 × 16 ≈ 2190 万行
树高 4：≈ 256 亿行

千万级大表，B+ 树高度稳定在 3 层，意味着任何单行查询最多 3 次页 IO——而根页和中间页因为被反复访问，几乎常驻 Buffer Pool，实际常常只有 1 次真实磁盘 IO。 这就是 InnoDB 敢说"主键点查毫秒内"的结构基础。

5.2 改造二：所有数据都在叶子层，且叶子按键有序连成双向链表 → 范围查询是顺序 IO

-- 找到 id=100 的叶子页后，200、201... 顺着叶子链表往后读即可
SELECT * FROM t WHERE id BETWEEN 100 AND 200 ORDER BY id;

• 找到起点（3 次 IO）→ 叶子页内二分定位 → 沿 next page 指针顺序扫描；
• 顺序 IO 在机械盘上比随机 IO 快几十上百倍（预读 read-ahead 还能提前把相邻页加载进内存）；
• ORDER BY 直接利用叶子有序性，避免 filesort；覆盖索引扫描同理。

5.3 改造三：查询路径长度稳定（永远走到叶子）

B 树命中不同层路径长短不一，B+ 树所有查询都从根走到叶子，路径长度完全一致——查询性能稳定可预测，这对数据库的延迟 SLA 很重要。

5.4 四结构总决战

六、结合 InnoDB 再深一层：这些面试追问要接住

6.1 聚簇索引：叶子节点存的就是整行数据

InnoDB 的表本身就是按主键组织的 B+ 树（索引组织表 Index-Organized Table）：

聚簇索引（主键）B+ 树：
  叶子页 = 完整数据行（所有列）
  → 主键查询在叶子直接拿到全部数据，不需要二次查找

二级索引（普通索引）B+ 树：
  叶子页 = 索引列值 + 主键值（不是行指针！）
  → 先在二级索引树查到主键，再拿主键去聚簇索引树查一遍 = 回表（两次 B+ 树查找）

为什么二级索引叶子存主键而不是物理地址？因为 B+ 树页分裂/数据移动时行的物理位置会变，存地址就要到处更新二级索引；存主键值，行怎么搬都不受影响，代价就是回表。这也解释了为什么主键要尽量短（自增 bigint 最好）：每个二级索引的叶子都要冗余一份主键，主键越长，二级索引越胖，扇出越小，树越高——又回到了 5.1 的容量账。

6.2 为什么推荐自增主键而不是 UUID？

注意 MySQL 8.0 有 UUID_TO_BIN(uuid, 1)（swap flag）可以把时间相关位前置，缓解随机插入，但长度问题仍在。

6.3 最左前缀原则的结构解释

联合索引 (a, b, c) 在 B+ 树叶子里的排序键是先按 a、a 相同按 b、b 相同按 c——这就是为什么 WHERE b=? 用不上索引（b 在全局无序），而 WHERE a=? AND b=? 能用。范围查询后面的列失效也是同理：a=? AND b>? AND c=? 中 b 一旦是范围，c 在该区间内不再有序。

6.4 页都在 Buffer Pool 里时，B+ 树还有优势吗？

有，但讨论变成"内存数据结构"了：内存中红黑树/哈希也不慢。但 Buffer Pool 不可能装下全库，且 B+ 树页同时服务于"缓存命中"和"缓存未命中"两种路径，用一种结构统一覆盖；加上范围/排序红利，B+ 树仍是最优解。纯内存 KV 场景（如 Redis）确实用哈希表等结构，因为约束变了——这正说明结构选型永远由约束决定。

七、面试怎么答：30 秒版 + 3 分钟版

30 秒版（电梯陈述）

"核心原因是磁盘随机 IO 比内存访问慢约十万倍，而且数据库按页读取，所以索引结构的目标是用最少的 IO 完成查询。哈希等值是 O(1) 但不支持范围和排序；红黑树是二叉结构扇出只有 2，千万数据有 20 多层、20 多次 IO；B 树虽然是多路树，但数据存在所有节点导致单页扇出小、且范围查询要跨层中序遍历。B+ 树把数据全部放到叶子、非叶子只存导航键，InnoDB 16KB 的页扇出约 1170，千万级表树高只有 3 层，最多 3 次 IO；叶子节点又按键有序串成链表，范围查询和排序变成顺序扫描。所以 B+ 树是矮、宽、叶子有序三者兼得，最匹配磁盘。"

3 分钟版的展开顺序（按这个节奏答，不会乱）

1. 先讲约束：磁盘随机 IO ~10ms、按 16KB 页读取、树高=IO 次数
   → 索引必须矮胖、扇出大、叶子有序
2. 哈希：等值 O(1)，但哈希打散顺序，范围/排序/前缀/最左前缀全废
   → 补充：InnoDB 有自适应哈希，但只是 B+ 树热点之上的内存加速器
3. 红黑树：二叉扇出 2，log₂(千万)≈24 层 24 次 IO，为内存设计
4. B 树：多路解决了树高（~5 层），但非叶子存数据稀释扇出，
   数据散落各层且叶子不相连，范围查询跨层随机 IO
5. B+ 树三改造：非叶子只存键（扇出1170，三层两千万）、
   全数据在叶子+叶子双向链表（范围=顺序IO）、查询路径等长（性能稳定）
6. 加分项：InnoDB 聚簇索引叶子存整行、二级索引存主键要回表，
   所以主键要短且自增（避免 UUID 随机插入造成页分裂）

常见追问速答

八、总结

速查卡

唯一标尺：磁盘随机 IO 极贵（机械盘~10ms，SSD~0.1ms），按 16KB 页读
         → 树高 = IO 次数，必须矮胖、大扇出、叶子有序

哈希    ：点查 O(1)，范围/排序/前缀全废（AHI 只做热点加速器）
红黑树  ：扇出 2，千万数据 24 层 24 次 IO（内存结构）
B 树    ：多路~5 层，但数据存全节点→扇出小，叶子不相连→范围随机 IO
B+ 树   ：非叶子只存键（扇出~1170）→ 3 层存 2000 万行
         叶子存全部数据+双向链表 → 范围/排序顺序 IO
         查询路径等长 → 性能稳定
InnoDB  ：聚簇索引叶子=整行；二级索引叶子=主键→回表
         主键短(8B)且自增：扇出大、无页分裂

一句话

索引选型不是"谁查询快"的功能比拼，而是磁盘 IO 约束下的必然推导：一次机械盘随机 IO 约 10ms、比内存访问慢约十万倍，数据库还只能按 16KB 的页为单位读取，于是索引结构被三条铁律锁死——树高决定 IO 次数必须矮胖、每页导航信息要尽量多即扇出要大、叶子数据必须物理有序以支撑范围和排序。哈希表点查 O(1) 天下第一，但哈希函数把顺序彻底打散，BETWEEN、ORDER BY、LIKE 前缀、联合索引最左前缀全部失效，只能做 InnoDB 里自适应哈希那样的点查加速器；红黑树为内存而生，二叉扇出只有 2，一千万数据要长到约 24 层、一次查询 24 次随机 IO 就是 240ms；B 树靠多路平衡把层数压到约 5 层是巨大进步，但它在所有节点都塞数据行，一个 16KB 页只能放约 33 个条目，稀释了扇出，而且数据散落在树的各层、叶子之间互不相连，范围查询只能跨层中序遍历打出大量随机 IO。B+ 树做了三刀切中全部痛点：非叶子节点只存键不存行，14 字节约一个导航条目使单页扇出达到约 1170，于是两层装两万、三层装两千万、四层两百亿，千万级表的任何点查最多 3 次页 IO，而根页和中间页几乎常驻 Buffer Pool，常态下只有一次真实磁盘读；全部数据行下沉到叶子层，叶子按键有序并用双向链表串联，范围查询和 ORDER BY 从树顶定位一次起点后就退化为顺序扫描，机械盘预读友好、比随机 IO 快几十倍；所有查询都走到叶子、路径等长，性能稳定可预测。再往 InnoDB 里走一步：聚簇索引的叶子就是完整数据行，二级索引的叶子存的是主键值所以要回表——这反过来解释了主键为什么必须短（bigint 8 字节，每个二级索引都冗余一份）且必须自增（UUID 随机插入导致页分裂、填充率下降、顺序写变随机写）。所以标准答案的底色从来不是"B+ 树快"，而是：B+ 树是唯一同时满足"矮、宽、叶子有序"的磁盘友好结构——矮让 IO 次数恒定在个位数，宽让每次 IO 值回票价，叶子有序把范围查询变成顺序读，这三件事恰好一一对应磁盘的三个物理事实。

给学习者的建议

互动话题：被问到"为什么用 B+ 树"时你是怎么答的？有没有被追问到 B 树和 B+ 树区别时卡壳过？评论区聊聊你的面试经历。

参考资料

• MySQL 8.0 官方文档：InnoDB 索引结构（Clustered and Secondary Indexes）
• MySQL 8.0 官方文档：B+ Tree 索引页结构与 Buffer Pool
• Database System Concepts（Silberschatz）：B+ Tree Indexing 章节
• Gregg, Systems Performance：延迟数量级参考表
• SQLite 官方文档：The SQLite Query Optimizer Overview（B-Tree 组织）