B+ 树索引
问题
为什么数据库普遍使用 B+ 树作为索引结构？B+ 树和 B 树、红黑树、跳表有什么区别？什么是聚簇索引和非聚簇索引？
答案
B+ 树结构
B+ 树是一种多路平衡搜索树，所有数据存储在叶子节点，非叶子节点只存储索引键值。
核心特点
| 特点 | 说明 |
|---|---|
| 多路平衡 | 每个节点可以有多个子节点（通常数百个） |
| 数据在叶子 | 所有实际数据/指针都存在叶子节点 |
| 叶子有链表 | 叶子节点通过双向链表相连，支持范围查询 |
| 矮胖结构 | 树的高度通常只有 2-4 层 |
| 非叶仅索引 | 非叶子节点只存 key，不存数据 |
B+ 树的高度与数据量
以 InnoDB 为例，假设一行数据 1KB、索引 key + 指针占 12 字节、页大小 16KB：
| 树高度 | 非叶子节点扇出 | 可存储数据量 |
|---|---|---|
| 2 层 | ~1365 | ~1365 × 16 ≈ 2 万行 |
| 3 层 | ~1365 | ~1365 × 1365 × 16 ≈ 3000 万行 |
| 4 层 | ~1365 | ~1365³ × 16 ≈ 百亿行 |
InnoDB 中 3 层 B+ 树就能存储 约 2000-3000 万行数据，每次查询只需 2-3 次磁盘 IO（根节点通常缓存在内存中）。这是 B+ 树被数据库广泛使用的核心原因。
为什么用 B+ 树
B+ 树 vs B 树
| 对比项 | B 树 | B+ 树 |
|---|---|---|
| 数据存储 | 所有节点都存数据 | 只有叶子节点存数据 |
| 非叶子节点 | 存 key + data | 只存 key + 指针 |
| 扇出能力 | 较小（data 占空间） | 更大（非叶只存 key） |
| 范围查询 | 需要中序遍历整棵树 | 叶子链表直接扫描 |
| 查询性能 | 不稳定（有的在根就找到） | 稳定（一定到叶子） |
B+ 树的核心优势：
- 扇出更大 → 树更矮 → 磁盘 IO 更少
- 范围查询高效 → 叶子链表顺序扫描
- 查询性能稳定 → 每次都查到叶子，时间可预测
B+ 树 vs 红黑树
| 对比项 | 红黑树 | B+ 树 |
|---|---|---|
| 每个节点子节点数 | 2 | 数百到数千 |
| 100万数据树高度 | ~20 层 | 2-3 层 |
| 磁盘 IO 次数 | ~20 次 | 2-3 次 |
| 适用场景 | 内存数据结构 | 磁盘数据结构 |
红黑树是二叉树，树太高了，每层都要读一次磁盘 —— 磁盘 IO 是数据库性能的最大瓶颈。
B+ 树 vs 跳表
| 对比项 | 跳表 | B+ 树 |
|---|---|---|
| 磁盘友好 | ❌ 随机指针 | ✅ 顺序页 |
| 范围查询 | ✅ 底层链表 | ✅ 叶子链表 |
| 实现复杂度 | 简单 | 复杂 |
| 使用场景 | Redis（内存） | MySQL（磁盘） |
Redis 是纯内存数据库，不需要考虑磁盘 IO。跳表实现简单、范围查询方便、内存友好，是更好的选择。B+ 树的优势在于磁盘 IO 优化，对纯内存场景不适用。
B+ 树 vs 哈希
详见 哈希索引。简单概括：哈希 定点查找快，但不支持范围查询和排序。
聚簇索引 vs 非聚簇索引
这是数据库索引中最核心的概念之一。
聚簇索引（Clustered Index）
聚簇索引 = 索引结构的叶子节点直接存储完整的数据行。
InnoDB 中，主键索引就是聚簇索引。数据按主键顺序物理存储。
特点：
- 每个表只能有 一个 聚簇索引（因为数据只能按一种顺序物理存储）
- InnoDB 自动选择主键作为聚簇索引；没有主键则选唯一非空索引；都没有则生成隐藏的 ROW_ID
- 查主键 → 一次 B+ 树查找即可获取完整数据
非聚簇索引（Secondary Index / 二级索引）
非聚簇索引 = 叶子节点存储索引键值 + 主键值，不存完整数据。
回表（Table Lookup）
通过二级索引查找数据时，先在二级索引中找到主键值，再回到聚簇索引中查找完整行数据。这个过程叫 回表。
-- 假设 name 字段有索引
SELECT * FROM users WHERE name = '张三';
执行过程：
- 在 name 的二级索引 B+ 树中查找
'张三'→ 得到pk = 10 - 拿着
pk = 10到聚簇索引 B+ 树中查找 → 得到完整行数据 - 两次 B+ 树查找 = 两次索引查找
回表的性能影响：
- 少量回表（几行）：影响可忽略
- 大量回表（上千行）：可能比全表扫描还慢，优化器可能选择不用索引
- 避免回表：使用 覆盖索引
InnoDB vs MyISAM 索引实现
| 特性 | InnoDB | MyISAM |
|---|---|---|
| 聚簇索引 | ✅ 主键即聚簇索引 | ❌ 没有聚簇索引 |
| 二级索引叶子 | 存主键值 | 存行指针（物理地址） |
| 回表代价 | 需要查一次主键索引 | 直接读物理地址（更快） |
| 主键查询 | 极快（直接定位） | 需要查索引 + 读地址 |
主键设计的影响
InnoDB 中主键直接影响数据物理存储顺序，主键设计至关重要。
| 主键类型 | 优势 | 劣势 |
|---|---|---|
| 自增 ID | 顺序插入，页分裂少 | ID 可预测，分布式不友好 |
| UUID | 全局唯一 | 随机插入，页分裂多，索引膨胀 |
| 雪花 ID | 有序 + 全局唯一 | 时钟回拨问题 |
UUID 是随机的，导致新数据随机插入 B+ 树的各个位置：
- 频繁页分裂：需要调整已有页的数据，成本高
- 索引膨胀：UUID 36 字节 vs 自增 ID 4/8 字节，每个二级索引的叶子都存主键
- 缓存命中率低：数据不连续，Buffer Pool 缓存效果差
常见面试问题
Q1: 为什么 MySQL 索引用 B+ 树而不用 B 树？
答案：
三个核心原因：
- 扇出更大：B+ 树非叶子节点不存数据，同样大小的页能容纳更多 key，树更矮，磁盘 IO 更少
- 范围查询高效：B+ 树叶子节点有双向链表，范围查询直接顺序扫描；B 树需要中序遍历
- 性能稳定：B+ 树每次查询都到叶子，查询路径等长；B 树有时在中间节点就命中，性能不稳定
Q2: 什么是回表？如何减少回表？
答案：
回表是指通过二级索引查到主键后，再到聚簇索引查完整数据的过程。每次回表是一次额外的 B+ 树查找。
减少回表的方法：
- 覆盖索引：让查询需要的字段都在索引中，
SELECT a, b FROM t WHERE a = 1时建(a, b)联合索引 - 减少
SELECT *：只查需要的字段 - 索引下推（ICP）：MySQL 5.6+ 自动优化，在索引层面过滤更多数据
Q3: InnoDB 为什么推荐用自增 ID 做主键？
答案：
- 自增 ID 保证顺序插入，新数据总是追加在 B+ 树的最右边，不会引起页分裂
- 自增 ID 占 4/8 字节，所有二级索引叶子节点存的主键值更小，索引更紧凑
- 连续插入保证了数据局部性，Buffer Pool 缓存命中率高
对比 UUID：随机插入导致频繁页分裂（50% 的概率）、36 字节导致索引膨胀、缓存命中率低。
Q4: 一个表可以有多少个索引？
答案：
理论上没有硬限制，但实际中：
- 建议不超过 5-6 个索引
- 每个索引都会增加写入成本（INSERT/UPDATE/DELETE 需要维护所有索引）
- 每个索引占用额外存储空间
- 索引太多，优化器选择成本也增加
Q5: B+ 树索引中，什么是页分裂和页合并？
答案：
页分裂：当一个页（16KB）写满后，新插入的数据无法放下，InnoDB 会：
- 申请新页
- 将原页约 50% 的数据移到新页
- 更新父节点指针
页合并：当删除数据导致一个页的数据量低于 50%（MERGE_THRESHOLD），InnoDB 会尝试将相邻页合并。
自增主键几乎不会触发页分裂（总是在最后追加）。随机主键（如 UUID）会频繁触发页分裂。