★ MySQL 为什么用 B+Tree 做索引？什么是回表与覆盖索引？

结论先行：B+Tree 只在叶子节点存数据且叶子间形成有序链表，内部节点只存键做路由：层高低（千万级数据通常 3~4 层）、单次查询的磁盘 IO 次数少且稳定、天然支持范围查询，因此成为 InnoDB 索引的默认结构。回表：走二级索引先定位到主键，再回聚簇索引取整行；覆盖索引：查询所需列全部包含在索引内，无需回表，是最常用的查询优化手段。

结构对比表

结构	范围查询	单点查询	磁盘 IO	备注
B+Tree	好（叶子链表顺序扫描）	好	层数低且稳定	InnoDB 聚簇/二级索引
B-Tree	一般	好	略多	每个节点都携带数据
Hash	不支持	O(1)	少	只适合等值查询

聚簇索引与二级索引

• 聚簇索引：按主键组织，叶子节点存整行数据，一张表只有一个；
• 二级索引：叶子节点存“索引列 + 主键”，查询列不全时需要回表补数据。

回表与覆盖索引示例

-- 假设二级索引 idx_name_age(name, age)
SELECT id, name, age FROM user WHERE name = '张三';
-- id/name/age 都在索引中 → Extra 显示 Using index，覆盖索引、不回表

SELECT name, age, phone FROM user WHERE name = '张三';
-- phone 不在索引里 → 需用 id 回聚簇索引取整行 → 回表

为什么不用哈希或红黑树

• 哈希索引无法支持范围查询与排序，而 B+Tree 靠叶子链表一次顺序扫描即可完成范围遍历；
• 红黑树在内存结构里很优秀，但磁盘随机 IO 昂贵：B+Tree 以“高扇出、低层高”把单次查询 IO 压到 3~4 次；
• B-Tree 非叶子节点也存数据，相同数据量下层数更深、IO 不稳定；B+Tree 把数据集中在叶子层，顺序读更友好。

二级索引查找过程

根节点二分定位 → 中间节点逐层下探 → 叶子节点命中记录
（覆盖索引：直接返回；否则用主键回聚簇索引取整行）

常见追问 / 记忆点

• 追问：主键为什么建议自增而不是随机 UUID？答：聚簇索引按主键物理有序，随机主键会造成页分裂、碎片与写放大。
• 追问：联合索引怎么建最省？答：遵循最左前缀原则，等值列放前面，并尽量让高频查询被覆盖索引“吞掉”。
• 记忆点：B+Tree 三好——“层低、IO 稳、链表支持范围”；优化先看执行计划 Extra 里的 Using index / Using filesort。