B+ 树索引

建表时到底要不要指定主键？指定了，为什么几乎都推荐 BIGINT AUTO_INCREMENT 而不是 UUID？这两个问题的答案不在「规范条文」里，而在 InnoDB 的数据组织方式里：InnoDB 的一张表，本质就是一棵以主键为排序依据的 B+ 树。主键选得不好，插入数据时就要频繁「拆页」。

1. 聚簇索引：数据就存在 B+ 树里

1.1 InnoDB 的表就是一棵 B+ 树

大多数数据库教科书先讲「表」，再讲「索引」，好像索引是表之外的附加结构。但在 InnoDB 里，这个顺序是反的：数据本身就存在一棵 B+ 树的叶子节点里，这棵树叫聚簇索引（Clustered Index）。

这意味着 InnoDB 的表必须有一棵聚簇索引，数据才有地方放。InnoDB 按下面的优先级自动确定聚簇索引：

有显式主键 → 用主键；
没有主键，但有「非空的唯一索引」→ 用第一个这样的索引；
都没有 → 生成一个隐藏的 DB_ROW_ID（6 字节，自增）充当聚簇索引。

所以「一张表可以没有主键」只是语法上的——底层 InnoDB 永远会想办法补一棵聚簇索引出来。第 3 种情况最糟：DB_ROW_ID 对你不可见，你无法用它做业务查询，还白白占 6 字节。这也是「每张表都显式指定主键」的底层依据。

sql

-- 推荐：显式指定主键，聚簇索引由主键充当
CREATE TABLE users (
    id   BIGINT PRIMARY KEY AUTO_INCREMENT,
    name VARCHAR(50)
) ENGINE = InnoDB;

1.2 聚簇索引长什么样

聚簇索引的叶子节点存的是完整的行数据，非叶子节点只存主键值，用于导航。整体结构：

两个值得注意的点：

叶子节点按主键有序。因此「按主键排序查询」不需要额外排序，天然有序。
叶子节点之间用双向链表连接。这让「主键范围扫描」可以顺着链表一路读下去，不必反复回到上层节点。

1.3 数据页的内部结构：为什么能快速定位一行

B+ 树的每个节点在磁盘上对应一个页（Page），InnoDB 默认页大小 16 KB。要理解「一次索引查找为什么快」，得先看清一个页里装了什么：

页从前往后依次是 File Header、Page Header、Infimum/Supremum、User Records、Free Space、Page Directory、File Trailer：两头是元数据，中间放真正的行数据。

页内查找一行，走的是「页目录 + 二分查找」：

Page Directory 里放着一组「槽」，每个槽指向一组记录（通常是 4~8 条）中最大的那条；
查找时先对槽做二分，定位到目标所在的槽；
再在槽内做线性扫描，找到目标行。

这一层的意义是：页内查找不是从头到尾逐条扫，而是「先二分定位到组，再在组内细找」。加上 B+ 树本身只有 3~4 层高（见 §3.1），一次等值查询的磁盘 IO 次数被压到了个位数。

隐藏列

页里的每行记录，除了你定义的列，还带着 DB_ROW_ID、DB_TRX_ID、DB_ROLL_PTR 三个隐藏列，支撑事务与 MVCC，见事务与 MVCC §2.2。

2. 二级索引与回表优化

2.1 二级索引：另一棵树，存的是主键

主键之外建的索引，叫二级索引（Secondary Index）。它也是一棵 B+ 树，但叶子节点存的不是完整行数据，而是主键值。

一次 SELECT * FROM users WHERE name = 'Tom' 要经过两步：

sql

-- 1. 在二级索引 idx_name 上，定位 name='Tom' 的叶子，取出主键 id=5
-- 2. 拿着 id=5 回到聚簇索引，再查一次，取出完整行

这第二步回到聚簇索引再查一次，就叫回表。回表是一次额外的随机 IO，是二级索引查询的主要成本。

2.2 覆盖索引：让查询不回表

如果二级索引的叶子节点里，已经包含了查询要的所有列，就不用回表了。这种索引叫覆盖索引（Covering Index）。

sql

-- 二级索引只含 name；要取 age，必须回表
SELECT age FROM users WHERE name = 'Tom';

-- 建一个 (name, age) 联合索引后，name 和 age 都在索引里
-- SELECT age FROM users WHERE name = 'Tom' 直接命中覆盖索引，不回表
CREATE INDEX idx_name_age ON users (name, age);

判断标准是执行计划里的 Extra 列：

sql

EXPLAIN SELECT age FROM users WHERE name = 'Tom';
-- Extra = Using index  → 覆盖索引，不回表
-- Extra = NULL（或含 Using where）→ 需要回表

Using index 是「这次查询没回表」的信号。频繁出现的列组合，值得考虑合并进一个联合索引，用「多占一点索引空间」换「省掉大量回表 IO」。

2.3 索引下推（ICP）：把过滤下沉到存储引擎

MySQL 5.6 引入索引下推（Index Condition Pushdown，ICP）。它的思路是：把 WHERE 里能用索引列的过滤条件，下沉到存储引擎层，在遍历索引时提前过滤，减少回表。

sql

SELECT * FROM users WHERE name LIKE '张%' AND age = 25;
-- 索引：idx_name_age (name, age)

没有 ICP 时，存储引擎只会用 name LIKE '张%' 定位到一批记录，把它们的主键全部回表，再由 Server 层判断 age = 25 是否成立——很多行的 age 根本不等 25，白回表了。

有 ICP 时，存储引擎在遍历 idx_name_age 这棵二级索引时，顺手把 age = 25 这个条件也判断了（age 是索引的第二个列，索引里就有它的值），不满足的行根本不回表。

关键前提：ICP 能下推的，只能是索引里含有的列的条件。age 不在任何索引里时，它无法下推，只能回表后再过滤。

3. 性能与代价

3.1 B+ 树高度与数据量：3~4 层够装下亿行

B+ 树的「矮胖」决定了它查找快。以主键 BIGINT（8 字节）+ 页指针（6 字节）为例，粗略推算：

txt

非叶子节点每个键值：8（主键）+ 6（指针）= 14 字节
每页 16 KB，扣掉页头/页尾约 1 KB 开销，可用约 15 KB
非叶子节点每页可存：15 × 1024 / 14 ≈ 1097 个键值（取约 1170）

叶子节点每行假设 200 字节：15 × 1024 / 200 ≈ 76 行（取约 80）

高度=2：1170 × 80         ≈ 9 万行
高度=3：1170 × 1170 × 80  ≈ 1 亿行
高度=4：1170 × 1170 × 1170 × 80 ≈ 1000 亿行

结论是：树高 3~4 层，就能装下上亿行数据，一次等值查询只需 3~4 次磁盘 IO。 这正是 B+ 树被选作 InnoDB 索引结构的原因——扇出大、树矮、IO 次数稳定。这也是它优于「二分查找有序数组」的地方：数组插入要整体挪动，B+ 树插入只影响局部的页。

3.2 页分裂：为什么主键要自增

这是主键选型的核心，也是本文最该讲透的一点。B+ 树的页有固定容量，写满后要页分裂（Page Split）：分配一个新页，把原页约一半的数据搬过去，再在父节点插入一条指向新页的记录。

页分裂的代价取决于「新数据落在树的什么位置」，而这正是自增主键和随机主键的本质区别。

自增主键：永远往最右插。

新数据永远追加到树的最右端。最右的页满了，只需开一个新页接在链表末尾，父节点加一个指针。分裂几乎只发生在最右一个页，且旧页不需要移动任何数据，是「追加」而非「拆分」。

随机主键（UUID）：往中间插。

随机值插入时，目标页往往已经写满，必须分裂。分裂后约一半数据要搬到新页，父节点也要插入新指针；如果父节点也满，还要向上递归分裂。更糟的是，分裂产生的新页插在链表中间，磁盘上数据页的物理顺序与主键逻辑顺序脱节，后续的范围扫描会退化成大量随机 IO。

两者对比：

特性	自增主键 `BIGINT AUTO_INCREMENT`	随机主键（UUID）
插入位置	始终最右，顺序追加	随机落位，频繁插入中间
页分裂	仅最右页，接近无成本	频繁分裂，且可能向上递归
索引大小	8 字节	`CHAR(36)` 占 36 字节
二级索引体积	存的主键小，二级索引小	存的主键大，二级索引随之膨胀
数据页连续性	好，范围扫描快	差，范围扫描退化为随机 IO
全局唯一	表内唯一	天然全局唯一

UUID 的「全局唯一」在分布式场景确实有价值，但代价是页分裂和索引膨胀。折中做法是雪花算法（Snowflake） 生成的 ID：既全局唯一，又大体递增（时间戳在高位），兼顾了「分布式的唯一性」和「顺序写入的性能」。

sql

-- 推荐：单库单表用自增主键
CREATE TABLE orders (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    ...
) ENGINE = InnoDB;

-- 注意：分布式用雪花 ID（应用层生成，时间戳高位保证递增）
-- id BIGINT PRIMARY KEY,  -- 值由 Snowflake 算法生成

3.3 索引的代价：不是越多越好

索引用空间和写入时间，换读取时间。

空间代价：每建一个索引，就多一棵完整的 B+ 树，磁盘占用随之增加。

写入代价：写操作要同步维护所有索引。

INSERT：主键索引和每个二级索引都要插入一条；
UPDATE：改到索引列时，等于在旧位置删除、在新位置插入；
DELETE：主键索引和每个二级索引都要删除（InnoDB 的 DELETE 实际是标记删除，真正的清理交给 Purge，见 Undo Log）。

sql

-- 查看某张表的索引占用空间
SELECT
    index_name,
    ROUND(stat_value * @@innodb_page_size / 1024 / 1024, 2) AS index_mb
FROM mysql.innodb_index_stats
WHERE table_name = 'users' AND stat_name = 'size';

4. 最佳实践

显式指定自增主键：BIGINT AUTO_INCREMENT，避免落入隐藏 DB_ROW_ID，并享受顺序写入。
分布式场景用雪花 ID：兼顾全局唯一与递增，避免 UUID 的页分裂。
频繁查询的列组合建成覆盖索引：让 Extra 显示 Using index，省掉回表。
索引数量控制在 5~6 个以内：每个索引都是写入负担，用 sys.schema_unused_indexes 定期清理无用索引。
避免在高频更新的列上建索引：更新索引列的代价高于普通列。

B+ 树索引 ​

1. 聚簇索引：数据就存在 B+ 树里 ​

1.1 InnoDB 的表就是一棵 B+ 树 ​

1.2 聚簇索引长什么样 ​

1.3 数据页的内部结构：为什么能快速定位一行 ​

2. 二级索引与回表优化 ​

2.1 二级索引：另一棵树，存的是主键 ​

2.2 覆盖索引：让查询不回表 ​

2.3 索引下推（ICP）：把过滤下沉到存储引擎 ​

3. 性能与代价 ​

3.1 B+ 树高度与数据量：3~4 层够装下亿行 ​

3.2 页分裂：为什么主键要自增 ​

3.3 索引的代价：不是越多越好 ​

4. 最佳实践 ​