面试官:索引为什么用 B+ 树而不是 B 树/哈希/红黑树?——从磁盘 IO 讲起
引言 "你说你熟悉 MySQL 索引,那我问你:索引为什么用 B+ 树?" 这是后端面试的经典开场。很多候选人的回答是"B+ 树查询快"——这个答案等于没说,哈希表查询 O(1) 岂不是更快?也有人答"B+ 树是平衡树"——红黑树也是平衡树,为什么不用?当面试官追问"那 B 树呢,B+ 树到底比 B 树强在哪",大部分人就卡住了。 这个问题答不好,不是因为 B+ 树有多难,而是思考顺序错了:一上来就背 B+ 树的特点,却没有先回答"数据库索引的约束条件是什么"。答案的第一性原理其实只有一句话:磁盘随机 IO 极贵,索引结构的唯一设计目标,就是用最少的磁盘读取次数找到数据。理解了这一句,哈希、红黑树、B 树为什么落选,B+ 树为什么胜出,全部可以自己推导出来,根本不用背。这篇文章就从磁盘 IO 的成本讲起,把四种结构放在同一个标尺下一较高低,最后给出 InnoDB 里的真实数字和面试回答话术。 一、先立标尺:一次磁盘随机 IO 到底有多贵 1.1 数字说话 操作大致耗时(数量级) CPU 访问 L1 缓存~1 ns CPU 访问主存~100 ns SSD 随机读(4KB)~50....