📌 今日关键词：B+ 树、页分裂、页合并、聚簇索引、二级索引、回表、磁盘 I/O
大家好，我是数据库小学妹 👋
经过前面的学习，我们知道了索引能让查询从 O(n) 降到 O(log n)，速度快了不少。但最近研究索引底层原理时，几个问题一直搞不清楚：
为什么数据库索引用的是 B+ 树，而不是二叉树或哈希表？
一棵 B+ 树到底能存多少数据？
插入数据时为什么会发生"页分裂"？
"主键要用自增"，又是为什么？
这些问题困扰了我很久，直到真正理解了 B+ 树的底层实现，才明白索引的设计哲学是为了让磁盘 I/O 次数最少。
今天就把这段时间踩过的坑、查过的资料整理出来，聊聊 B+ 树的底层原理。
一、为什么数据库选 B+ 树？
先看看几种常见数据结构的查询效率：
| 数据结构 | 查询效率 | 适合场景 | 为什么数据库不用 |
|---|---|---|---|
| 二叉查找树 | O(log n) | 内存查询 | 树太高，磁盘 I/O 太多 |
| B 树 | O(log n) | 文件系统 | 叶子节点不相连，范围查询慢 |
| B+ 树 | O(log n) | 数据库索引 | 叶子节点有序链表，范围查询快 |
| 哈希表 | O(1) | 精确查询 | 不支持范围查询 |
B+ 树的核心优势
树的高度很低（一般只有 2-4 层）
B+ 树是多路查找树，每个节点可以存很多子节点（比如几百个）。这意味着：
二叉树：1000 万条数据，树高约 24 层，查询需要 24 次磁盘 I/O
B+ 树：1000 万条数据，树高约 3 层，查询只需要 3 次磁盘 I/O
磁盘 I/O 是数据库性能的最大瓶颈，所以 B+ 树的设计就是让树尽可能"矮胖"。
叶子节点形成有序链表
[根节点]
/ \
[内部节点] [内部节点]
/ \ / \
[叶子]--[叶子]--[叶子]--[叶子]
(有序链表，范围查询超快)
执行 WHERE id BETWEEN 100 AND 200 时，B+ 树只需要找到 id=100 的叶子节点，然后沿着链表往后扫描到 id=200。
B 树的叶子节点没有链表，需要反复回溯，效率低很多。
二、B+ 树的一个节点有多大？
InnoDB 的存储基本单位是页（Page），默认大小是 16KB。
树高多少，每一层的一个节点就是一个页（16KB）。B+ 树的高度其实就是"要读取多少次 16KB 的页"。
InnoDB 页的结构（简化版）
┌─────────────────────────────┐
│ 页头 (Page Header, 56B) │ 页的元信息
├─────────────────────────────┤
│ 记录区 (User Records) │ ← 这里存索引记录
├─────────────────────────────┤
│ 空闲空间 (Free Space) │ 剩余空间
├─────────────────────────────┤
│ 页目录 (Page Directory) │ 稀疏索引，加速查找
├─────────────────────────────┤
│ 页尾 (File Trailer, 8B) │ 校验信息
└─────────────────────────────┘
记录区存索引数据的地方，一个页能存多少条记录，取决于你的索引列有多大。
三、一棵 B+ 树能存多少数据？（实战计算）
假设一张用户表：
CREATE TABLE users (
id BIGINT PRIMARY KEY, -- 8 字节
name VARCHAR(32), -- 假设最多 32 字节
age INT -- 4 字节
);
1️⃣ 计算聚簇索引（主键索引）能存多少数据
聚簇索引的叶子节点存的是完整行数据，每行记录大约：
id (8B) + name (32B) + age (4B) + 隐藏字段 (26B) + 变长字段长度列表 (3B) + NULL 值位图 (1B)
≈ 74 字节
一个 16KB 的页能存多少行？
16384 字节 ÷ 74 字节 ≈ 221 行
但 InnoDB 每页最少要有 2 条记录，实际会因为页目录等开销，假设每页存 200 行。
B+ 树高度为 3（最常见情况），能存多少数据？
第 1 层（根节点）：1 页，约 200 个指针 → 指向第 2 层的 200 个节点
第 2 层（内部节点）：200 页，每个节点 200 个指针 → 指向第 3 层的 200×200 = 40,000 个节点
第 3 层（叶子节点）：40,000 页，每页 200 行
总数据量 = 40,000 × 200 = 800 万行
一棵 3 层高的 B+ 树，能存约 800 万行数据。查询只需要 3 次磁盘 I/O。
2️⃣ 二级索引能存多少数据？
对 name 字段建二级索引：
CREATE INDEX idx_name ON users (name);
二级索引的叶子节点存的是：索引列值 + 主键 ID
name (32B) + id (8B) + 其他开销 ≈ 50 字节
一个 16KB 的页能存：
16384 ÷ 50 ≈ 327 条索引记录
同样是 3 层 B+ 树：
总索引记录数 = 200 × 200 × 327 ≈ 1300 万条
二级索引能存比主键索引更多的数据，因为它只存索引列+主键，不存完整行数据。
四、页分裂：为什么会发生？
往 B+ 树插入数据时，如果某个页已经满了，InnoDB 会怎么做？
场景模拟：非自增主键
当前有一个页，存的是这些 ID：
[10, 20, 30, 40, 50, 60, 70, 80] (页满了，只能存 8 条)
插入 id=15，会怎样？
InnoDB 需要把 15 插到 10 和 20 之间，但页已经满了，没有空间。触发页分裂，把页拆成两个：
原页分裂后：
[10, 15, 20, 30] ← 页 1
[40, 50, 60, 70, 80] ← 页 2
页分裂需要申请新的页（磁盘 I/O）、复制一半数据（CPU + 内存）、更新父节点的指针（更多 I/O）。频繁页分裂会导致索引碎片和性能下降。
场景模拟：自增主键
用的是自增主键（1, 2, 3, 4, 5...）：
[1, 2, 3, 4, 5, 6, 7, 8] (页满了)
插入 id=9，9 直接追加到页的末尾（顺序插入）。如果页满了，申请新页就行，不需要页分裂。
自增主键能避免页分裂，这就是为什么老师总说"主键要用自增"。
五、页合并：什么时候触发？
页分裂的反向操作。删除大量数据后，页的使用率低于某个阈值，InnoDB 会把相邻的页合并。
InnoDB 的合并策略
页的使用率低于 50%，会尝试和兄弟页合并。合并能减少页的数量，提高缓存命中率。
-- 查看表的页碎片情况
SELECT table_name, data_free/1024/1024 AS free_mb
FROM information_schema.tables
WHERE table_schema = 'your_db' AND data_free > 0;
发现碎片太大时，可以通过以下方式重建索引：
-- 方式 1：重建表
ALTER TABLE users ENGINE = InnoDB;
-- 方式 2：优化表（会锁表，慎用）
OPTIMIZE TABLE users;
-- 方式 3：通过导出导入（推荐用于大表）
mysqldump ... | mysql ...
六、聚簇索引 vs 二级索引：回表的代价
聚簇索引（主键索引）
叶子节点：存的是完整行数据
查询速度：快（一次索引查找就能拿到所有数据）
每张表只能有一个聚簇索引（主键）
-- 使用聚簇索引（快）
SELECT * FROM users WHERE id = 100; -- 1 次索引查找
二级索引（普通索引）
叶子节点：存的是索引列值 + 主键 ID
查询速度：取决于是否需要"回表"
-- 只查索引列（快，不需要回表）
SELECT id, name FROM users WHERE name = '小明'; -- 1 次索引查找
-- 查非索引列（慢，需要回表）
SELECT * FROM users WHERE name = '小明'; -- 1 次索引查找 + 1 次聚簇索引查找 = 2 次 I/O
什么是回表？
先在二级索引里找到 name = '小明' 的记录，拿到主键 id = 100，再用 id = 100 去聚簇索引里查找完整行数据。这个过程就叫回表。
覆盖索引：避免回表
如果查询的列都在索引里，就能避免回表：
-- 建立联合索引
CREATE INDEX idx_name_age ON users (name, age);
-- 查询列都在索引里（覆盖索引）
SELECT id, name, age FROM users WHERE name = '小明'; -- 不需要回表，1 次索引查找搞定
所以常说"要避免 SELECT *"，可能触发回表，增加 I/O 开销。
七、实战：查看你的索引高度
1. 查看表的索引信息
-- 查看表的索引
SHOW INDEX FROM users;
2. 估算 B+ 树高度
-- 查看表的统计信息
SELECT
table_name,
table_rows,
avg_row_length,
data_length/1024/1024 AS data_mb,
index_length/1024/1024 AS index_mb
FROM information_schema.tables
WHERE table_schema = 'your_db' AND table_name = 'users';
根据 index_length 可以估算 B+ 树的高度：
index_mb ≈ 页数 × 16KB
页数 = index_mb × 1024 / 16
假设有 50,000 个页，每个内部节点最多 200 个指针：
第 1 层：1 页
第 2 层：最多 200 页
第 3 层：最多 200 × 200 = 40,000 页
第 4 层：最多 200 × 200 × 200 = 8,000,000 页
50,000 个页，B+ 树高度约 3-4 层。
3. 使用 EXPLAIN 验证索引使用
EXPLAIN SELECT * FROM users WHERE id = 100;
关注 key 列（用到哪个索引）和 rows 列（预计扫描多少行）。
八、新手避坑指南（血泪总结）
❌ 坑 1：主键用 UUID
-- 错误示范
CREATE TABLE users (
id CHAR(36) PRIMARY KEY, -- UUID，随机字符串
name VARCHAR(32)
);
UUID 是随机的，插入时会导致大量页分裂。UUID 占用 36 字节，比自增主键（8 字节）大 4 倍，同样的页能存的数据量少很多。
-- 用自增主键
CREATE TABLE users (
id BIGINT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(32)
);
❌ 坑 2：二级索引建太多
-- 错误示范
CREATE INDEX idx_name ON users (name);
CREATE INDEX idx_age ON users (age);
CREATE INDEX idx_city ON users (city);
CREATE INDEX idx_phone ON users (phone);
-- ... 建了 10 个索引
每次插入、更新、删除，都要更新所有索引。索引越多，写入越慢，占用大量磁盘空间。
只为高频查询的列建索引，遵循"5 个以内"原则（中小表）。
❌ 坑 3：忘记建立外键索引
-- 错误示范
CREATE TABLE orders (
id BIGINT PRIMARY KEY,
user_id BIGINT, -- 外键，但没建索引
amount DECIMAL(10, 2),
FOREIGN KEY (user_id) REFERENCES users(id)
);
这种查询会全表扫描：
SELECT * FROM orders WHERE user_id = 100; -- user_id 没索引，很慢
-- 给外键建索引
CREATE INDEX idx_user_id ON orders (user_id);
❌ 坑 4：SELECT * 查询
SELECT * FROM users WHERE name = '小明'; -- 可能触发回表
如果 name 有索引，但查 SELECT *，需要回表，增加了磁盘 I/O。
-- 只查需要的列（如果这些列都在索引里，就是覆盖索引）
SELECT id, name, age FROM users WHERE name = '小明';
九、今日学习心得
今天的内容不少，但核心就这几句话：
- B+ 树的设计目标是让磁盘 I/O 次数最少，树高一般只有 2-4 层
- 一棵 3 层的 B+ 树能存约 800 万行数据（聚簇索引），查询只需要 3 次 I/O
- 页分裂是插入数据的性能杀手，用自增主键能避免
- 二级索引查询可能需要回表，覆盖索引可以避免
- 索引不是越多越好，要权衡查询加速和写入成本
以前觉得"索引建了就能快"，现在才知道索引的设计和选择，要考虑磁盘 I/O、页分裂、回表成本。
就像给书建目录，目录页太多也不好，会增加翻书的负担。合理的索引策略，才能真正让查询飞起来。
👋 我是数据库小学妹，一个用设计师思维学数据库的转行人。我们一起，把复杂的技术变得简单有趣！💕
本文示例基于 MySQL 8.0 + InnoDB。理解 B+ 树底层原理，对掌握索引优化和数据库性能调优非常有帮助。
