索引与 B+ 树

索引让查询从全表扫描变成三次页访问。本章讲 B+ 树为什么对磁盘友好、聚簇与非聚簇索引、复合索引的最左前缀，以及写优化的 LSM 树（→ 二叉搜索树与平衡树）。

B+ 树：为磁盘而生

内存树的树高是 CPU 周期，磁盘树的树高是 I/O 次数——每次下钻一页。B+ 树让每个节点存几十上百个键（一个节点一个页，页大小与磁盘 I/O 单位对齐）：

100 万条数据、每页 100 键：树高三层——为什么查询从全表扫描变成三次 I/O；
叶子串成链表：范围查询变成顺着叶子扫——范围扫描是 B+ 树优于哈希索引的关键；
内部节点只放路标（键 + 子指针），数据全在叶子——每个节点能放更多路标，树更矮。

B+ 树的修改：插入/删除用分裂与合并保持平衡（填充因子通常留 50%–75%），批量顺序插入几乎免费（右侧追加不分裂）。

聚簇与非聚簇

	聚簇索引（clustered）	非聚簇索引（secondary）
内容	数据按索引键物理存放	索引键 → 主键（或行指针）
数量	每表一个	多个
代表	MySQL InnoDB 主键	InnoDB 二级索引、PostgreSQL 全部

InnoDB 的二级索引存的是主键：查到索引还要回表（再查聚簇索引）——覆盖索引（见下）避免回表。PostgreSQL 的堆表 + 索引：所有索引存行指针，更新不迁移行。

复合索引与最左前缀

复合索引 (a, b, c) 的键按 a, b, c 的字典序排列——最左前缀决定复合索引能否被用上：

WHERE a = ? → 用上；WHERE a = ? AND b = ? → 用上；
WHERE b = ?（无 a）→ 用不上（跳过最左列）；
WHERE a = ? AND c = ? → a 用上，c 靠索引内过滤；
WHERE a > ? AND b = ? → a 用范围后，b 不再有序——范围列放最右。

索引列顺序的原则：等值列在前，范围列在后。

覆盖索引

查询需要的列全在索引里，不用回表：

-- 索引 (user_id, created_at)
SELECT created_at FROM orders WHERE user_id = 42;
-- 索引即数据，零回表

覆盖索引是读优化的大杀器，代价是索引更宽（写放大与空间增加）。

索引不是免费的

索引不是免费的：写放大与空间——每个索引都是一棵要维护的 B+ 树，每次写要更新所有命中索引。索引数量的工程判断：读路径的收益 vs 写路径的代价——写密集表（日志、事件流）少索引，读密集表（用户、订单查询）多索引。未被使用的索引是纯负资产（占用写放大却不被查询命中）。

LSM 树：写优化的替代

B+ 树原地修改，随机写要跨盘。**LSM 树（Log-Structured Merge tree）**把写变成顺序追加：

写入内存表（memtable，跳表）；
满了刷成不可变的 SSTable（磁盘顺序写）；
后台**合并（compaction）**多层 SSTable，去重与整理。

B+ 树读优化，LSM 树写优化：LSM 写吞吐高一个量级（顺序写，→ I/O、总线与存储设备），代价是读要查多层（ Bloom 过滤器缓解）与 compaction 的后台 I/O 压力。LevelDB、RocksDB、Cassandra 的引擎。WAL + LSM 的组合是写密集系统的默认形态。

EXPLAIN 常见术语

术语	含义
seq scan / full table scan	全表扫描（无索引可用）
index scan	走索引
index only scan / using index	覆盖索引（不回表）
nested loop / hash join	连接算法
rows / estimated	优化器估计的行数（偏差大时计划走偏）

本章要点

B+ 树大节点 + 叶子链表：三次 I/O 定位 + 范围顺序扫
最左前缀决定复合索引能否被用上：等值列在前，范围列在后
覆盖索引零回表；索引不是免费的：写放大与空间
B+ 树读优化，LSM 树写优化：LSM 顺序写一个量级，代价是多层读与 compaction
看 EXPLAIN 是基本功：扫描方式、连接算法、行数估计