面试题：MySQL 索引为什么用 B+ 树，不用哈希或二叉树

这题考察的是对存储介质的理解，而不只是背结论。要点在于：数据库的数据最终要落盘，而磁盘随机 IO 比内存慢 5 个数量级。

先看三个候选的问题

哈希索引：等值查询 O(1)，很快。但

• 不支持范围查询（WHERE age > 20 没法用哈希）
• 不支持排序和最左前缀匹配
• 大量哈希冲突时性能退化

InnoDB 确实有自适应哈希索引，但只是缓冲区的辅助结构，不能替代主索引。

二叉搜索树：逻辑上完美，但树高 = log₂n。一千万数据要 24 层，每层一次磁盘 IO，就是 24 次随机读。磁盘 IO 是瓶颈，不是 CPU。

平衡二叉树（AVL / 红黑树）：树高降到 log n，但一千万数据仍需 20+ 层，且每个节点只存一个键值，浪费磁盘块。

B+ 树怎么解决的

B+ 树是多路平衡树，一个节点存几百个键值，树高被压到 3~4 层：

• 千万级数据，3 次磁盘 IO 就能定位
• 非叶子节点只存键，不存数据，一个 16KB 的页能放上千个键
• 叶子节点用双向链表串联，范围查询只需找到起点然后顺序遍历

最后一条是关键。BETWEEN 或 ORDER BY 在 B+ 树上几乎是顺序读，而哈希和二叉树都要反复回溯。

具体到 InnoDB

InnoDB 的主键索引是聚簇索引：叶子节点存的是完整行数据。所以：

• 按主键查一行，一次 B+ 树遍历直接拿到全部字段
• 二级索引叶子存的是主键值，查到后还要回表拿其他列

这就是”覆盖索引”能优化的原因——如果把要查的列都建进联合索引，就不用回表：

-- 需要回表
SELECT name FROM users WHERE phone = '138xxxx';

-- 覆盖索引，不用回表
CREATE INDEX idx_phone_name ON users(phone, name);

一个反直觉的点

自增主键比 UUID 好，不是因为长度，而是因为顺序插入。自增 ID 总是追加到 B+ 树右侧，页利用率高；UUID 随机分布，导致频繁的页分裂和磁盘随机写，插入性能可能差一个数量级。

面试怎么答

按这个层次说：

1. 数据在磁盘，减少 IO 次数是首要目标
2. B+ 树多路平衡，把树高压到 3~4 层
3. 非叶子节点只存键，单页容纳更多键，进一步降低树高
4. 叶子链表支持高效范围查询和排序
5. 补充：聚簇索引 / 覆盖索引 / 自增主键的实践意义

只答”因为 B+ 树查询快”是拿不到分的，必须落到磁盘 IO 这个根因上。