MySQL 为什么用 B+ 树做索引？

B+ 树的优势有两个：一是树矮胖，每个节点是一个页，一次 IO 读一整页关键字，千万级数据高度才三四层，磁盘 IO 次数少；二是叶子节点串成有序链表，范围查询顺着链表扫即可，而哈希索引不支持范围。对比二叉树：数据倾斜时退化成链表；对比 B 树：非叶子节点也存数据，单页放的键少树更高。

我会顺着 B+ 树讲聚簇索引：InnoDB 主键索引的叶子直接存整行，二级索引叶子存主键值，所以二级索引查询可能回表，覆盖索引直接在二级索引里拿齐字段避免回表。实践上我用这个原理解释过为什么 select * 慢、为什么联合索引要把高区分度列放前面、为什么用自增主键避免页分裂。

我从存储引擎的页结构讲：16KB 页、页内有序数组加页目录二分、层间指针；插入引发页分裂与合并，自增主键顺序写入最友好，随机 UUID 导致写放大。查询成本模型：一次 B+ 树查找等于树高次 IO，buffer pool 命中则免 IO，所以热点页常驻时千万级表也能毫秒返回。索引设计是 IO 次数与写入维护成本的平衡。

追问『为什么不用红黑树』：二叉结构树高 log2n 太深，一千万数据二十多层 IO；『为什么不用哈希』：等值快但范围与排序无能为力，Memory 引擎支持可见一斑；『联合索引 (a,b,c) 查 b 能用吗』：不能，不满足最左前缀，但 (a,b) 查 a 走最左。