02.1 - B+ 树索引结构
定位：MySQL InnoDB 的默认索引结构，理解 B+ 树的设计是理解一切索引优化的基础 面试高频度：⭐⭐⭐⭐⭐ 考查方式：为什么用 B+树不用 B 树/红黑树/哈希？B+树层高和数据量的关系？范围查询如何工作？
一、这是什么？为什么需要它？
是什么
B+树是一种自平衡的多路搜索树，是 B 树的变体。它的核心特征：
- 内节点只存 key（不存数据）→ 扇出（fan-out）极高，树极矮
- 叶子节点存所有 key 对应数据（或指向数据的指针）
- 叶子节点之间用链表串联 → 范围查询极其高效
为什么数据库需要 B+树？
想象没有 B+ 树的数据库：
用哈希表？ 等值查询 O(1)，但无法范围查询（
WHERE age > 20→ 全表扫描），也无法排序。数据库的日常工作大量是范围查询和排序。用二叉树/红黑树？ 树高 log₂N。1 亿行数据 → 树高约 27 层 → 每次查询需要 27 次磁盘 IO → 大约 270ms（磁盘每次 IO 约 10ms）。
用 B 树？ 好很多，但内节点也存数据，扇出较低（每个节点只能存 2-3 个 key），且范围查询需要"中序遍历回溯"（从子节点回溯到父节点再找兄弟节点）。
B+树的解决方案：
- 内节点只存 key → 每个节点可存 几百个 key → 1 亿行数据 → 树高仅 3-4 层 → 3-4 次磁盘 IO
- 叶子节点链表 → 找到起始 key 后直接沿着链表遍历 → 不需要回溯
核心 insight：B+树的所有设计都针对磁盘 IO 昂贵这一前提。用"冗余 key"（数据只存一次，key 在内节点中复制）换取"极矮的树"和"高效的范围遍历"。
二、原理拆解
2.1 B+树结构详解
B+树（三层示例）
┌────────────────────────┐
│ [50, 100] │ ← 内节点：存 key，不存数据
│ / | \ │ 扇出 = 3（实际 Innodb ~470+）
└───────┼────┼────┼──────┘
┌──┘ │ └──┐
▼ ▼ ▼
┌────────┐ ┌────────┐ ┌────────┐
│[10,30, │ │[60,80, │ │[120, │
│ 40,50] │ │ 90,100]│ │ 150] │ ← 第二层内节点
└───┬────┘ └───┬────┘ └───┬────┘
┌────┼───┐ ┌──┼───┐ ┌──┼───┐
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│ 1 │ │ 11│ │ 31│ │ 51│ │ 61│ │ 81│ │ 101│ │121│ │151│
│行数据│ │行数据│ │行数据│ │行数据│ │行数据│ │行数据│ │行数据│ │行数据│ │行数据│
└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
└───────────────────────────────────────────────────────┘
叶子节点层：存完整数据（或主键+行指针），链表相连
←─────────────────────────────────────────────────────→
叶子节点链表：范围查询从这里遍历2.2 扇出（Fan-out）为什么重要？
扇出 = 一个内节点能存储的子节点指针数量。
InnoDB 每个节点 = 1 个数据页（默认 16KB）。
一个数据页大小: 16KB = 16,384 字节
一个 key 占用: 约 8-20 字节
一个指针占用: 约 6 字节
一个(key+指针)对: 约 14-26 字节
一个节点的 key 数 ≈ 16KB / 20字节 ≈ 800 个
扇出 ≈ 800+ （实际考虑页内元数据，约 470+）
因此：
树高 1 层: ~500 行
树高 2 层: ~500 × 500 = 250,000 行
树高 3 层: ~500 × 500 × 500 = 125,000,000 行
树高 4 层: ~625 亿行
结论：对于绝大多数 OLTP 数据库（百万 ~ 亿级），B+树高度为 3-4 层
每次查询最多 3-4 次磁盘 IO2.3 B+树 vs B 树 vs 红黑树对比
B+树 B 树 红黑树/AVL
┌────────── ────────── ────────── ───────────────
│ 内节点 只存 key 存 key + data 存 key + data
│ 叶子节点 存所有 key + data 同内节点 同内节点
│ 叶子链表 ✅ 有（范围查询快） ❌ 无 ❌ 无
│ 扇出 极大（~500） 小（~2-3） 最小（2）
│ 树高(1亿) 3-4 层 约 8-10 层 约 27 层
│ 磁盘 IO 3-4 次 8-10 次 27 次
│ 范围查询 O(N) 极快 O(N*logN) 慢 O(N*logN) 慢
│ 插入性能 良好（自动分裂） 良好 可能需要旋转2.4 插入与分裂
插入 key = 25（假设叶子节点已满）：
分裂前：
[20, 30, 40, 50] ← 叶子节点已满（假设阶=4）
↑ 插入 25
分裂后：
[30] ← 新的内节点 key（提升）
↙ ↘
[20, 25] [40, 50] ← 两个半满的叶子节点为什么分裂从叶子向上传播？ B+树以叶子节点为数据存储层，分裂产生的"key 提升"保证内节点始终是路由信息。与 B 树不同，数据永远不会放在内节点上——这让树的形状更稳定。
三、图解全景
B+树 vs B 树 vs 红黑树对比图
B+树 B 树
┌────────────────┐ ┌────────────────┐
│ [50, 100] │ │ [50, data] │ ← 内节点就有数据
│ ↙ ↓ ↘ │ │ ↙ ↓ ↘ │ 扇出更小
│ [10,30] [60, │ │ [10,30][60] │
│ 80] [120] │ │ [80][120,150]│
│ ↓ ↓ ↓ ↓ ↓ ↓ ↓│ │ ↓ ↓ ↓ ↓ ↓ │
│ 1~9│11~29│...││ │ 1~9│11~29│...││
│ └─────────┘ │ │ └─────────┘ │
│ 叶子节点链表→→→│ │ (无叶子链表) │
│ (范围查询快) │ │ (范围查询慢) │
└────────────────┘ └────────────────┘
红黑树 哈希表
┌────────────────┐ ┌────────────────┐
│ A │ │ bucket[] │
│ ↙ ↘ │ │ [0]: 1, 11,... │
│ B C │ │ [1]: 2, 22,... │
│ ↙ ↘ ↙ ↘ │ │ ... │
│ D E F G │ │ 范围查询: ❌ │
│ 树高: log₂N │ │ 等值查询: O(1) │
│ 范围查询: ❌ │ └────────────────┘
└────────────────┘四、实战验证
查看 B+树层高
sql
-- 查看表的索引树高度（近似）
SELECT
b.name AS table_name,
a.name AS index_name,
INDEX_HEIGHT(a.space, a.page_no) AS height
FROM information_schema.INNODB_TABLES b
JOIN information_schema.INNODB_INDEXES a ON b.table_id = a.table_id
WHERE b.name = 'your_db/your_table';⚠️ 注意：
INDEX_HEIGHT()是调试函数，MySQL 8.0 可能需要打开innodb_debug参数。
估算 B+树层高
sql
-- 根据表行数估算 B+树层数
-- 假设:
-- 页大小 = 16KB
-- 主键 = BIGINT (8字节)
-- 指针 = 6字节
-- 每行数据 ≈ 200字节
--
-- 内节点每页存: (16KB - 元数据) / (8 + 6) ≈ 1170 个 key
-- 叶子节点每页存: 16KB / 200 ≈ 80 行
SELECT
ROW_COUNT,
CEIL(LOG(1170, ROW_COUNT / 80)) + 1 AS estimated_height
FROM (SELECT 1000000 AS ROW_COUNT) AS t;
-- 100万行 → 树高约 2 层
-- 1亿行 → 树高约 3 层验证 B+树范围查询效率
sql
-- 创建测试表
CREATE TABLE test_btree (
id INT PRIMARY KEY AUTO_INCREMENT,
val INT,
INDEX idx_val (val)
);
-- 插入 100 万行数据
-- ... (省略插入过程)
-- 等值查询
EXPLAIN SELECT * FROM test_btree WHERE id = 500000;
-- 预期: type=const, 1 row
-- 范围查询（主键）
EXPLAIN SELECT * FROM test_btree WHERE id BETWEEN 500000 AND 500100;
-- 预期: type=range, 101 rows, Extra: Using index condition
-- 排序
EXPLAIN SELECT * FROM test_btree ORDER BY id LIMIT 10;
-- 预期: type=index, Extra: Using index（B+树直接遍历叶子链表）五、面试视角
| 追问 | 答案要点 |
|---|---|
| 为什么不用红黑树做数据库索引？ | 树高 log₂N，1 亿行 ≈ 27 层 IO；且无法利用磁盘预读（B+树一页读几百 key） |
| B+树和 B 树的核心区别？ | B+树内节点只存 key（扇出大），B 树内节点存数据（扇出小）；B+树叶子节点有链表（范围查询快） |
| B+树层高怎么算？ | 树高 = log_{扇出}(行数/叶子节点每页行数) + 1。通常 3-4 层够存亿级数据 |
| 为什么不用哈希做索引？ | 哈希不支持范围查询（>、<、BETWEEN），不支持排序，不支持最左前缀 |
| InnoDB 索引页大小可以改吗？ | 可配置 innodb_page_size（4KB/8KB/16KB/32KB/64KB），但数据文件不可移植 |
| 为什么 B+树插入也高效？ | 节点分裂是局部操作（最多影响相邻页），且页内有序可二分查找 |
📚 相关链接
- 索引实践：**聚簇索引与二级索引**
- 优化进阶：**索引优化策略**
- 分析工具：**EXPLAIN与查询优化**
- 上游存储：**InnoDB 架构**
- ← 返回 **索引与查询优化索引**