#B+Tree 索引原理

面试官问："MySQL 的索引是什么结构？为什么不用二叉树或红黑树？"

小赵想了想："是 B+ 树。因为 B+ 树矮，查找次数少，所以快。"

面试官追问："B+ 树矮，为什么就快？"

小赵："...因为树矮，IO 次数少。"

面试官继续："那 B 树和 B+ 树有什么区别？为什么 MySQL 用 B+ 树不用 B 树？"

小赵开始卡壳。

这道题，我问过的候选人里，80% 能说出"B+ 树矮所以快"，但真正能解释清楚"为什么 B+ 树矮"和"B+ 树 vs B 树的本质区别"的，不超过 20%。今天这篇，把 B+ 树从根讲透。

#一、B+Tree 的数据结构 🔴

#1.1 从二叉树说起

MySQL 的索引为什么不直接用二叉树（比如 AVL 树或红黑树）？

假设一张表有 100 万行数据，二叉树的高度大约是 log₂(1000000) ≈ 20。每次查找需要 20 次磁盘 IO（假设树在磁盘上）。

100 万行数据用二叉树，层数大约 20 层。换成 B+ 树，每层可以存更多节点。

核心原因：磁盘 IO 的代价极高，一次 IO 可以读取一整个页（通常 16KB），B+ 树可以让一次 IO 读取更多索引数据，从而大幅减少 IO 次数。

#1.2 B+Tree 的结构

InnoDB 的 B+ 树结构：

                    [页目录槽] [页目录槽] [页目录槽]
                          ↓        ↓        ↓
┌───────────────────────────────────────────────────────┐
│                     非叶子节点（索引页）                 │
│                                                        │
│    [主键15]     [主键30]     [主键45]     [主键60]     │
│   /   |   \   /   |   \   /   |   \   /   |   \       │
│  ↓    ↓    ↓   ↓    ↓   ↓   ↓    ↓   ↓    ↓          │
│ 页1  页2   页3  页4  页5  页6  页7   页8  页9           │
└───────────────────────────────────────────────────────┘
        ↓           ↓           ↓           ↓
┌────────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐
│  叶子节点   │ │  叶子节点   │ │  叶子节点   │ │  叶子节点   │
│  (数据页)   │ │  (数据页)   │ │  (数据页)   │ │  (数据页)   │
│            │ │            │ │            │ │            │
│  主键1→指针 │ │  主键5→指针 │ │ 主键10→指针 │ │ 主键15→指针 │
│  主键2→指针 │ │  主键6→指针 │ │ 主键11→指针 │ │ 主键16→指针 │
│  主键3→指针 │ │  主键7→指针 │ │ 主键12→指针 │ │ 主键17→指针 │
│  主键4→指针 │ │  主键8→指针 │ │ 主键9→指针  │ │ 主键18→指针 │
│     ↓       │ │     ↓       │ │     ↓       │ │     ↓       │
│  完整数据行  │ │  完整数据行  │ │  完整数据行  │ │  完整数据行  │
└────────────┘ └────────────┘ └────────────┘ └────────────┘
        ↓           ↓           ↓           ↓
    双向链表（按主键顺序串起来）

B+ 树的特点：

1. 非叶子节点只存索引键和指针：不存数据，可以容纳更多索引项，树更矮
2. 叶子节点包含所有数据：聚簇索引的叶子节点直接存完整数据行
3. 叶子节点双向链表连接：支持高效的范围查询和顺序访问
4. 所有数据在叶子层：层高一致，查找路径长度相同

#1.3 B+ 树 vs B 树的关键区别

#1.4 页（Page）的概念

InnoDB 存储的最小单位是页（Page），默认大小 16KB。

• 非叶子节点（索引页）：存储索引键和子页指针
• 叶子节点（数据页）：存储数据行或主键+指针

-- 查看 InnoDB 页大小
SHOW VARIABLES LIKE 'innodb_page_size';
-- 默认 16384 字节（16KB）

假设一行数据 1KB，一页能存 16 行。假设非叶子节点一个索引项 16 字节（主键8字节 + 指针8字节），一页能存约 1000 个索引项。

那么：

• 一棵 3 层 B+ 树：1000 × 1000 × 16 = 1600 万行数据
• 一棵 4 层 B+ 树：1000 × 1000 × 1000 × 16 = 16 亿行数据

所以大多数情况下，MySQL 的 B+ 树只有 34 层，查询最多只需要 34 次磁盘 IO。

#1.5 ❌ 错误示范

候选人原话："B+ 树是一种二叉树。"

问题诊断：完全混淆了数据结构分类。二叉树是每个节点最多两个子节点的树结构；B+ 树是一种多路平衡查找树（M-way tree），每个节点可以有 N 个子节点。

候选人原话 2："B+ 树的查找时间复杂度是 O(log N)。"

问题诊断：这个说法没错，但太笼统。面试官追问的是"B+ 树矮为什么快"，答案应该落在磁盘 IO 次数上，而不是时间复杂度上。

【面试官心理】 这道题我通常分两层问：第一层问 B+ 树结构，第二层问 B+ 树 vs B 树 vs 二叉树。能说出 B+ 树矮所以 IO 少的是 P5 水平；能说出 B+ 树和 B 树本质区别的是 P6 水平；能说出 MySQL 页大小对树高影响、页分裂机制的是 P7 水平。

#二、查找过程 🔴

#2.1 聚簇索引查找流程

假设要查询 WHERE id = 25：

Step 1: 加载根节点页到内存
        [15]    [30]    [45]
        25 > 15, 继续右边子树
        ↓

Step 2: 加载中间节点页到内存
        [5] [10] [15]   [20] [25] [28]   [31] [35]
        找到 25，在第二个区间
        ↓

Step 3: 加载叶子节点页到内存
        在页内二分查找，定位到主键=25 的行
        ↓

Step 4: 返回完整数据行

整个过程最多 3 次磁盘 IO（假设树高为 3）。

#2.2 范围查询的优势

查询 WHERE id BETWEEN 10 AND 30：

Step 1: 定位到 id=10 所在的叶子节点
Step 2: 从 id=10 开始，沿着叶子节点的双向链表顺序遍历
Step 3: 直到 id > 30，停止遍历

不需要回溯到父节点重新查找，所有数据都在叶子层的链表上，顺序读即可。

#三、页分裂机制 🟡

#3.1 什么情况下会页分裂？

当向一个已满的页插入数据时，InnoDB 会进行页分裂：

-- 页原本按主键 1,5,10 排列，页满了
-- 现在要插入主键 7

-- 触发页分裂：
-- 将原页从中间分开，左半部分保留小值，右半部分存大值
-- 新插入的 7 可能在新页或旧页中

页分裂会导致页的物理存储顺序和逻辑顺序不一致，增加随机 IO。

#3.2 自增主键 vs UUID

使用自增主键，插入操作总是在页尾部追加，触发页分裂的概率很低。

使用 UUID（随机字符串）作为主键，新插入的行主键大小随机，大概率落在已有数据页的中间位置，频繁触发页分裂。

#3.3 索引页合并

与页分裂相反的是页合并。当删除数据导致相邻页利用率很低时，InnoDB 会合并相邻的两个页，减少空间浪费。

#四、生产避坑 🟡

#4.1 主键选择不当

场景：表使用 UUID 作为主键，数据量 500 万，插入速度只有 500 条/秒。

根因：UUID 随机性强，每次插入都在随机位置，频繁触发页分裂，大量随机磁盘 IO。

解决方案：

• 用自增 bigint 作为主键（推荐）
• 如果必须用业务主键（如订单号），创建一个自增 bigint 主键，业务主键作为唯一索引
• 如果用雪花 ID，可以按时间排序，但插入时仍然可能分裂，尽量批量插入

#4.2 索引不是越多越好

场景：表有 50 个字段，加了 20 个索引，数据量 1000 万，插入速度 100 条/秒。

根因：每次 DML 操作不仅要修改数据，还要更新所有相关索引。索引越多，维护成本越高。

解决方案：每个索引都是一个 B+ 树，插入时需要同时更新所有索引的 B+ 树。根据查询场景建立必要的索引，删除不使用的索引。

#五、工程选型

#5.1 为什么 MySQL 不用跳表？

Redis 的 ZSet 用跳表而不是 B+ 树，是因为：

• Redis 数据都在内存，内存访问不需要考虑磁盘 IO
• 跳表实现简单，容易做范围查询和并发控制
• 跳表的插入不需要页分裂，内存操作灵活

MySQL 选 B+ 树是因为数据在磁盘，需要最小化磁盘 IO 次数，B+ 树的磁盘友好性无可替代。

#5.2 为什么不用 LSM-Tree？

LSM-Tree（LevelDB/RocksDB/Cassandra 使用）适合写多读少的场景，写入性能极高。但范围查询需要合并多个层级，效率不如 B+ 树。MySQL 作为 OLTP 数据库，读写比例相对均衡，B+ 树是更平衡的选择。

【面试官心理】 问 B+ 树原理，不是为了考候选人背书。我是想确认他有没有理解"为什么 MySQL 用这个数据结构"，以及"这个数据结构对业务有什么影响"。能说出页分裂和自增主键的候选人，说明他真正看过原理、踩过坑。