★ FEATURED ARTICLE 先给结论因为磁盘。索引结构的所有设计权衡最后都归结到一件事怎么把一次查询需要的磁盘 IO 次数压到最低。理解了这条B 树的每个设计点都能自己推出来。如果把数据全放进内存B 树未必是最优解。Redis 的有序集合用的是跳表没用 B 树是因为它压根不走磁盘。反过来看这个对照恰恰证明了 B 树是为磁盘量身定做的。一次真实的慢查询说起这个我想起一个 case。一张订单表3000 万行主键查询正常走的是 secondary index 的时候偶发 1.2 秒。第一反应当然是索引没生效。但看执行计划type 是 refrows 只有 40 多行索引用上了。真正的原因在别处走了二级索引之后要拿着主键值回表去聚簇索引里捞整行数据而那 40 行散落在 40 个不同的页里。40 次随机 IO而机械盘一次约 10ms加起来就接近 400ms 了。后来改成覆盖索引不需要回表直接降到了 8ms。这个 case 说明的就是本文的主题理解的单位是页是 IO 次数不是比较了几次字符串。有了这个视角下面所有的取舍都会变得很自然。逐个排除为什么不是这几种Hash 为什么不行Hash 做等值查找是 O(1)比 B 树的 O(log n) 快得多理论上更优。MySQL 也确实支持 Hash 索引——Memory 引擎就是用 HashInnoDB 还有个自适应哈希索引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。假设主键是 bigint8 字节指针按 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 未必还是最优解。你在生产中调过页大小吗或者遇到过因为页大小导致的问题评论区聊聊。
阅读完成 · 觉得有帮助？
