B+ Tree Indexes: Internals and Optimization
Why B+ trees, page splits and fill factor, clustered vs secondary, composite index ordering, covering indexes, and index-only scans.
Why a B+ Tree
Databases read data in fixed-size pages (InnoDB: 16KB). A B+ tree keeps every path from root to leaf the same height, so a point query touches exactly height pages — a 3-level tree indexes tens of millions of rows with 3 disk-range reads. Only leaf nodes hold data, and leaves form a linked list for fast range scans.
[根节点]
/ | \
[内部节点 ...] ← 只存索引键 + 子页指针
/ | \
[叶子] → [叶子] → [叶子] → ← 存数据（聚簇）或主键值（二级）
树高估算：每页约存 1170 个键（16KB / ~14B）
3 层 = 1170 × 1170 × 16 ≈ 2 千万行
4 层即可覆盖数十亿行（多一层 IO）Clustered vs Secondary Indexes
-- 聚簇索引（主键）：叶子存整行数据，一张表只有一个
-- 二级索引：叶子存主键值，查到主键后要回表再取整行
CREATE TABLE t (
id BIGINT AUTO_INCREMENT PRIMARY KEY, -- 聚簇
email VARCHAR(128),
user_id BIGINT,
UNIQUE KEY uk_email (email), -- 二级（唯一）
KEY idx_uid (user_id) -- 二级
);
SELECT * FROM t WHERE email = 'a@b.com';
-- 1. uk_email 找到主键 id（一次 B+ 树查找）
-- 2. 回表（第二次 B+ 树查找）取整行
-- 为什么主键要用自增整型：
-- 顺序写入不触发随机页分裂；整型比较与二级索引体积都小
-- 用 UUID 做主键？二级索引体积膨胀 + 随机插入频繁分裂Composite Index Ordering
-- 原则：等值列在前，范围列在后
KEY idx (status, created_at, user_id)
SELECT * FROM orders WHERE status = 1
AND created_at >= '2026-10-01' AND created_at < '2026-11-01';
-- status 等值定界 + created_at 范围扫描 ✓
SELECT * FROM orders WHERE created_at > '2026-10-01';
-- ✗ 跳过 status，违反最左前缀
-- 排序也要用上索引：ORDER BY 与索引顺序一致则免 filesort
SELECT * FROM orders WHERE status = 1
ORDER BY created_at DESC LIMIT 10;
-- 命中 (status, created_at)，无需额外排序
-- 选择性差的列放前面会怎样？
-- WHERE sex = 'M' AND age > 30：sex 只有 2 值，几乎不裁剪行
-- 应把选择性高/能定界的列放前面
-- 前缀索引：长字符串场景
ALTER TABLE t ADD KEY idx_name (name(20)); -- 前 20 字符
-- 注意：前缀索引无法做覆盖索引与 ORDER BY 优化Page Splits and Insert Patterns
- Page split: inserting a row into a full page copies half to a new page — random keys (UUID) make splits and fragmentation constant.
- Auto-increment keeps inserts sequential: splits only at the rightmost edge, pages stay dense.
- Optimize table rebuilds the index to defragment — a long, table-copying operation; schedule in low traffic.
- Batch insert in chunks (a few thousand rows) to amortize log and page costs over big imports.
Covering Indexes and Index-Only Scans
-- 回表的成本：每行多一次 B+ 树查找
-- 覆盖：把 SELECT 用到的列全部塞进索引
-- 反面：SELECT * 强制回表
SELECT * FROM orders WHERE user_id = 7;
-- 正面：只取索引里的列
SELECT user_id, status FROM orders WHERE user_id = 7;
-- KEY idx (user_id, status) → Extra: Using index，不回表
-- 典型优化：分页深翻页
SELECT * FROM orders ORDER BY id LIMIT 1000000, 10;
-- 扫 100 万行才返回 10 条 → 改成两段
SELECT o.* FROM orders o
INNER JOIN (
SELECT id FROM orders ORDER BY id LIMIT 1000000, 10
) x ON x.id = o.id;
-- 子查询在主键索引上纯索引扫描，命中 10 行再回表
-- 索引扫描代替全表：count(*) 的替代方案
EXPLAIN SELECT COUNT(*) FROM orders WHERE status = 1;
-- 若 (status) 有索引，Extra 为 Using index，扫描数据量骤降Check EXPLAIN Extra for 'Using index' as the goal: it means the query never touches the table rows. Every hot query should aim for it.
为什么是 B+ 树
数据库按固定大小的页（InnoDB 16KB）读写。B+ 树从根到叶的每条路径等高，点查恰好经过「树高」个页——3 层的树用 3 次读取就能定位数千万行。只有叶子存数据，叶子间用链表相连，范围扫描极快。
[根节点]
/ | \
[内部节点 ...] ← 只存索引键 + 子页指针
/ | \
[叶子] → [叶子] → [叶子] → ← 存数据（聚簇）或主键值（二级）
树高估算：每页约存 1170 个键（16KB / ~14B）
3 层 = 1170 × 1170 × 16 ≈ 2 千万行
4 层即可覆盖数十亿行（多一层 IO）聚簇索引与二级索引
-- 聚簇索引（主键）：叶子存整行数据，一张表只有一个
-- 二级索引：叶子存主键值，查到主键后要回表再取整行
CREATE TABLE t (
id BIGINT AUTO_INCREMENT PRIMARY KEY, -- 聚簇
email VARCHAR(128),
user_id BIGINT,
UNIQUE KEY uk_email (email), -- 二级（唯一）
KEY idx_uid (user_id) -- 二级
);
SELECT * FROM t WHERE email = 'a@b.com';
-- 1. uk_email 找到主键 id（一次 B+ 树查找）
-- 2. 回表（第二次 B+ 树查找）取整行
-- 为什么主键要用自增整型：
-- 顺序写入不触发随机页分裂；整型比较与二级索引体积都小
-- 用 UUID 做主键？二级索引体积膨胀 + 随机插入频繁分裂复合索引的列顺序
-- 原则：等值列在前，范围列在后
KEY idx (status, created_at, user_id)
SELECT * FROM orders WHERE status = 1
AND created_at >= '2026-10-01' AND created_at < '2026-11-01';
-- status 等值定界 + created_at 范围扫描 ✓
SELECT * FROM orders WHERE created_at > '2026-10-01';
-- ✗ 跳过 status，违反最左前缀
-- 排序也要用上索引：ORDER BY 与索引顺序一致则免 filesort
SELECT * FROM orders WHERE status = 1
ORDER BY created_at DESC LIMIT 10;
-- 命中 (status, created_at)，无需额外排序
-- 选择性差的列放前面会怎样？
-- WHERE sex = 'M' AND age > 30：sex 只有 2 值，几乎不裁剪行
-- 应把选择性高/能定界的列放前面
-- 前缀索引：长字符串场景
ALTER TABLE t ADD KEY idx_name (name(20)); -- 前 20 字符
-- 注意：前缀索引无法做覆盖索引与 ORDER BY 优化页分裂与写入模式
- 页分裂：满页插入要把一半数据拷到新页——随机键（UUID）导致持续分裂与碎片。
- 自增主键保持顺序插入：只会在最右边缘分裂，页保持紧凑。
- OPTIMIZE TABLE 重建索引去碎片，但要拷整表、耗时长，安排在低峰。
- 大批导入拆成每批几千行，摊薄日志与页操作开销。
覆盖索引与纯索引扫描
-- 回表的成本：每行多一次 B+ 树查找
-- 覆盖：把 SELECT 用到的列全部塞进索引
-- 反面：SELECT * 强制回表
SELECT * FROM orders WHERE user_id = 7;
-- 正面：只取索引里的列
SELECT user_id, status FROM orders WHERE user_id = 7;
-- KEY idx (user_id, status) → Extra: Using index，不回表
-- 典型优化：分页深翻页
SELECT * FROM orders ORDER BY id LIMIT 1000000, 10;
-- 扫 100 万行才返回 10 条 → 改成两段
SELECT o.* FROM orders o
INNER JOIN (
SELECT id FROM orders ORDER BY id LIMIT 1000000, 10
) x ON x.id = o.id;
-- 子查询在主键索引上纯索引扫描，命中 10 行再回表
-- 索引扫描代替全表：count(*) 的替代方案
EXPLAIN SELECT COUNT(*) FROM orders WHERE status = 1;
-- 若 (status) 有索引，Extra 为 Using index，扫描数据量骤降检查 EXPLAIN 的 Extra 是否出现 Using index——这代表完全没回表；每条热查询都值得往这个方向优化。