第 9 章 · 索引与查询优化

快不快看索引：B+ 树与哈希、聚簇与覆盖、最左前缀，以及用 EXPLAIN 看清查询。

9.1 为什么是索引

无索引只能全表扫描（O(n)）。索引是辅助数据结构，用额外空间换查询时间，即「为数据建目录」。

9.2 B+ 树索引 vs 哈希索引

维度	B+ 树索引	哈希索引
结构	多路平衡树，叶子层全链成有序链表	哈希表（桶 + 冲突链）
等值查找 `=`	O(log n)，快	O(1)，更快
范围查找 `BETWEEN`/`>`	叶子有序，顺序扫	不支持，只能全扫
排序 / 最左前缀	支持	不支持
适用	默认首选，通用	仅等值、且无范围排序需求的场景

B+ 树（非叶子只存索引键，数据全在叶子）
        [ 10 | 20 ]
        /     |     \
    [5|8]  [12|15] [25|30]      ← 非叶子节点
      │       │       │
    叶子: 5→8→10→12→15→20→25→30   ← 叶子层有序双向链表

数据全在叶子层，非叶子只做路标，叶子用链表串起——故能等值也能范围。
树矮而胖（一节点存几百键），一次查找 2~4 次磁盘 IO，适合磁盘。

对比：B+ 树 vs 哈希——B+ 树有序 + 支持范围，是默认索引；哈希纯等值更快（O(1)），但范围/排序/前缀失效。有范围/排序/前缀用 B+ 树；仅等值无排序才考虑哈希。MySQL Memory 引擎支持哈希，InnoDB 默认 B+ 树（可建自适应哈希）。

9.3 聚簇索引 vs 非聚簇索引

维度	聚簇索引	非聚簇（二级）索引
叶子存什么	整行数据	索引键 + 主键值（指针）
每表数量	只能 1 个	可多个
主键即聚簇	是（InnoDB）	—
回表	无需	查到主键后再回聚簇索引取整行

InnoDB 主键索引即聚簇索引：数据按主键物理有序。二级索引（如对 name 建）叶子存「name → 主键」，要别的列还得回表再查主键索引，多一次 IO。

9.4 联合索引与最左前缀

联合索引（复合索引）按多列建一棵 B+ 树，列顺序至关重要：

CREATE INDEX idx_dept_age ON student(dept, age);

索引按 (dept, age) 排序。最左前缀原则：查询从最左列开始、按顺序命中才能用上：

WHERE dept = 'CS'                    -- 用上（最左列）
WHERE dept = 'CS' AND age > 20       -- 用上
WHERE age > 20                       -- 跳过 dept，用不上
WHERE dept = 'CS' AND age > 20 AND sname = 'x'  -- 前两列用上

建联合索引把等值、区分度高、常用的列放最左；顺序不对索引白建。

9.5 覆盖索引与执行计划

覆盖索引：查询所需列全在索引里，不用回表，一次索引扫描搞定。为此常把 SELECT 的列也加进联合索引。
EXPLAIN：看一条 SQL 走哪个索引、扫多少行、是否回表：

EXPLAIN SELECT * FROM student WHERE dept = 'CS';

关键字段：type（const > ref > range > index > ALL，ALL 全表扫描=最差）、key（用到的索引）、rows（预估行数）、Extra（Using index 覆盖索引，Using filesort 额外排序要警惕）。

对比：聚簇 vs 非聚簇——聚簇数据与主键绑一起物理存储，主键查询/范围极快且无回表，但只能一个、插入可能页分裂、主键要短且递增；非聚簇轻量、可多建、不重排数据，但查到主键后要回表。经典优化：让二级索引「覆盖」查询列，省回表、保持主键聚簇有序。