MySQL 为什么常用 B+ 树索引

数据库课讲索引时提到 InnoDB 用 B+ 树。课堂上讲了结论，但我当时没完全理解为什么非得是 B+ 树。

课后查了一圈，整理成这篇笔记。

核心约束：磁盘 IO 是瓶颈

索引结构不能只看时间复杂度，还要看它适不适合磁盘。

内存随机访问很快，磁盘随机 IO 慢得多。所以数据库索引很重要的目标是：尽量少读磁盘页。

逐个排除

哈希表

哈希表做等值查询很快，但范围查询不行。比如：

WHERE age > 20

哈希后的值是乱序的，没法顺着扫。

红黑树

红黑树是二叉树，树会比较高。数据量一大，查一次可能要走很多层。如果每层都对应一次磁盘页读取，代价就高了。

B 树

B 树已经比二叉树适合磁盘，但它的非叶子节点也存数据。一个页里能放的索引项就少一些，树的高度不如 B+ 树好控制。

B+ 树赢在哪

1. 非叶子节点只存键：一页能放更多索引项，树更矮
2. 数据全在叶子层：查询路径长度稳定
3. 叶子节点串成链表：范围查询可以顺着链表扫

SELECT * FROM users WHERE age BETWEEN 20 AND 30;

一个实用推论

联合索引 (a, b, c) 本质上是先按 a 排，再按 b 排，最后按 c 排。

所以最左前缀原则不是数据库随便定的规则，而是排序方式决定的：如果跳过 a 直接查 b，整棵树对 b 来说并不是有序的。

课程项目里给学生表加了 (class_id, score) 联合索引，按班级查成绩排名的接口从 1.2s 降到 40ms。数据结构没白学。