MySQL 索引为什么用 B+ 树？从 B 树、Hash、红黑树讲起
先给结论
因为磁盘。
索引结构的所有设计权衡最后都归结到一件事：怎么把一次查询需要的磁盘 IO 次数压到最低。理解了这条，B+ 树的每个设计点都能自己推出来。
如果把数据全放进内存，B+ 树未必是最优解。Redis 的有序集合用的是跳表，没用 B+ 树是因为它压根不走磁盘。反过来看，这个对照恰恰证明了 B+ 树是为磁盘量身定做的。
一次真实的慢查询
说起这个我想起一个 case。一张订单表3000 万行，主键查询正常，走的是 secondary index 的时候偶发 1.2 秒。
第一反应当然是"索引没生效"。但看执行计划，`type` 是 `ref`，`rows` 只有 40 多行，索引用上了。
真正的原因在别处：走了二级索引之后，要拿着主键值回表去聚簇索引里捞整行数据，而那 40 行散落在 40 个不同的页里。40 次随机 IO，而机械盘一次约 10ms，加起来就接近 400ms 了。
后来改成覆盖索引，不需要回表，直接降到了 8ms。
这个 case 说明的就是本文的主题：理解的单位是"页"，是 IO 次数，不是"比较了几次字符串"。有了这个视角，下面所有的取舍都会变得很自然。
逐个排除：为什么不是这几种
Hash 为什么不行
Hash 做等值查找是 O(1)，比 B+ 树的 O(log n) 快得多，理论上更优。MySQL 也确实支持 Hash 索引——Memory 引擎就是用 Hash，InnoDB 还有个自适应哈希索引（AHI），不过那个是 InnoDB 自己偷偷建的，你没法手动指定。
它不能当主力，卡在四点：
- 不定范围查询。Hash 之后的值是无序的，`where id > 100 and id < 200` 这种只能全表扫。而范围查询在线上业务里占比不低。
- 搞不定排序。`order by` 用不上索引，只能额外排序。
- 最左前缀原则失效。联合索引里 Hash 是把整个 key 拼起来算的，只用左边部分字段就查不了。
- 冲突代价不可控。冲突会退化成链表遍历，而数据量增大会让冲突变频繁，性能没有下限保证。
所以：Hash 只擅长"按这个值找这一条"，而数据库要应付的场景远不止这一种。
二叉树和红黑树
排除它们的理由更简单：树太高了。
红黑树是二叉树，每个节点最多两个孩子。100 万行数据，红黑树高度大约是 20。如果这个索引长在磁盘上，一次比较就可能是一次 IO，最坏要 20 次磁盘 IO 才能找到一个值。
更麻烦的是平衡操作。红黑树插入要旋转、变色，在磁盘结构上做这种调整，代价远高于内存。
有人说 AVL 树更平衡、高度更低。问题是它为了维持严格平衡，插入时的旋转次数比红黑树还多。在读多写少的理想场景里 AVL 更优，但数据库不能假设写入很少。
那 B 树呢？它已经很接近了
到这一步才进入正题。B 树是"多路平衡查找树"，一个节点可以有几十上百个孩子，高度一下就降下来了。
但 InnoDB 还是没选它，用的是 B+ 树。差别在两点：
差别一：数据搁哪儿
B 树的每个节点都存数据（整行），非叶子节点也存。B+ 树只有叶子节点存数据，非叶子节点只存索引键和指针，不存数据。
这个差别带来的连锁反应很关键。InnoDB 一页默认 16KB。如果非叶子节点要塞整行数据，能放的节点数就少，扇出（fan-out）就低，树就高。而 B+ 树的非叶子节点只放键和指针，一页能塞进去上千个，树的高度自然就被压扁了。
差别二：叶子之间连不连
B+ 树的叶子节点之间有一条双向链表串起来的。B 树没有，叶子彼此独立。
这条链表是范围查询的胜负手。B+ 树做范围查询，找到起点之后顺着链表往后扫就行了，不用再回到父节点。B 树要做中序遍历，得在树的不同层之间来回跳，中途还要回溯，会产生大量随机 IO。
顺带说一句，这也是为什么 MySQL 的叶子节点是"双向"链表而不是单向——`order by desc` 倒着扫的时候数据也能用到。
算个数：三层树能存多少行
这一段建议直接记下来，面试官很喜欢问。
InnoDB 页默认 16KB。假设主键是 bigint，8 字节，指针按 6 字节算：
一个非叶子页能放： 16 * 1024 / (8 + 6) ≈ 1170 个指针 一个叶子页装的完整行：假设一行 1KB → 16 行那三层树能索引多少行？
1170 × 1170 × 16 = 21,902,400**约 2100 万行**。
两千万左右的数据量，三次磁盘 IO 就能定位到某一行。而且因为根节点几乎肯定被缓存在内存里，实际往往只有 2 次 IO。
这就是"索引为什么快"的数字答案。它不神秘，就是算术加上两个设计选择：让非叶子节点只存索引、让叶子节点串成链表。
面试官在等的那句
到这里，普通候选人讲完了"多路、矮、链表"。如果停在这，面试官会客套地点点头，然后换下一题。
真正拉开差距的是这一句：
B 树的查询复杂度是不稳定的——运气好，要找的数据就在根节点，一次命中；运气不好，得一路走到最深的叶子。最坏情况下两者差距很大。B+ 树强制每次查询都落到叶子节点，查询路径长度固定，复杂度稳定是 O(log n)。
线上系统要的不是"平均更快"，而是延迟可预测。
这句话的价值在于：它说明你不是从书上抄答案，而是真正想过生产环境要什么。稳定比快更重要，这是运维和 DBA 视角才有的判断。
四个常见的错误答案
错误一：只说"B+ 树是多路平衡查找树"
这是教科书定义，不是对这个问题的回答。面试官问的是"为什么是它"，你要回答的是取舍，不是名词解释。
错误二：说"B+ 树一定比 B 树快"
不准确。单条等值查询，B 树可能更快，因为数据可能在高层就命中了，不用走到叶子。B+ 树赢在**范围查询**和**整体稳定**，不是赢在每一次单点查询上。
错误三：以为 InnoDB 的索引只有一种
InnoDB 除了 B+ 树，还有自适应哈希索引（AHI，全自动、不可干预）、全文索引（倒排）。面试时提一句 AHI，能证明你知道体系边界在哪。
错误四：把 B+ 树和 Hash 当成互斥关系
它们不是替代关系。InnoDB 在一定条件下会给热点页自动加 AHI，是两套机制并存。
标准答法（可以直接背）
MySQL 选 B+ 树，核心是为了减少磁盘 IO。
相比二叉树和红黑树，它是多路的，树高被压到很低，千万级数据只需 2~3 次 IO；相比 Hash，它支持范围查询、排序和最左前缀；相比 B 树，它的非叶子节点只存索引键不存数据，扇出更高，且叶子节点之间用双向链表相连，范围查询不用回溯。
另外 B+ 树的查询路径长度固定，每次都落到叶子，复杂度稳定。生产环境要的是延迟可预测，这一点比平均性能更重要。
说完这段，如果面试官还想继续聊，大概率会顺着往下问联合索引、回表、覆盖索引那几个坑。
一个还没聊完的问题
有个细节我一直没找到特别好的解释：InnoDB 为什么死守 16KB 的页大小，而不是像某些数据库那样做成可配置的？
官方文档给的理由是和历史兼容性有关。但如果从 SSD 随机读特性出发重新设计，16KB 未必还是最优解。
你在生产中调过页大小吗？或者遇到过因为页大小导致的问题？评论区聊聊。