数据库索引与 B+ 树

slug

数据库索引与 B+ 树

type

Post

status

Published

date

May 14, 2026

MySQL InnoDB 的核心数据结构。本笔记重点建立物理图景，而非死记概念。

一、为什么必须建索引

设一张表存 10 亿条微博，无索引顺序扫描：

用户查一条微博要等 578 天——不是慢，是根本不可用。

B+ 树的目标：把 578 天压缩到几毫秒（10 个数量级的差距）。

二、核心物理图景

节点 = Page = 磁盘 I/O 单位

一个 B+ 树节点 = 操作系统的一个 page（InnoDB 默认 16KB）

一次磁盘 I/O 读一个 page（约 5ms）

关键观念：磁盘 I/O 才是成本，节点内的 CPU 比较几乎免费

两种节点

类型	别名（类比新华字典）	装的东西
非叶子节点	目录页 / 拼音索引页	路标 + 子节点页号
叶子节点	内容页 / 正文页	真实数据

字典类比是理解 B+ 树最直接的钩子：

拼音索引页一行只有"字 + 页码"，信息密度高，一页能塞很多条

正文页一个词条占半页，信息密度低

设计者智慧：把"指路用的指针"和"真正的内容"分开存

节点内部结构

一个 (key + ptr) 配对约占 16 byte（key 8B + ptr 8B）

pointer 数 = key 数 + 1（永远绑定）

key 之间的"缝隙"自然有 pointer 填进去

Pointer 是什么

Pointer 就是子节点在磁盘文件中的页号（一个整数，通常 8 byte）。

类比字典目录里"李 → 234 页"，那个 234 就是 pointer。

数据库文件被切成连续编号的 16KB 页：

操作系统拿到页号即可计算 offset 直接读盘。寻址这件事简单到让人怀疑人生。

Key 的语义

非叶子节点的 key 是分界线（separator），不是分类标签。

例：[ptr0, 25, ptr1, 50, ptr2, 75, ptr3] 的含义：

key < 25 → 走 ptr0

25 ≤ key < 50 → 走 ptr1

50 ≤ key < 75 → 走 ptr2

key ≥ 75 → 走 ptr3

注意：25 这个 key 同时存在于父节点（当路标）和某个叶子里（当真实数据）——它是"复印件"。

Key 的顺序谁决定？

比较规则（Comparator）是建表时由工程师指定的。 一旦定了，全树的插入、查询都用同一套规则：

整数：自然序

字符串：字典序（按 ASCII / Unicode 码点）

中文：可选拼音、笔画、Unicode 等

类比：新华字典之所以能让你"跳查"，是因为印刷前编辑已按某规则排好序。

三、Fan-out 与树的高度

Fan-out 定义

fan-out = 一个节点最多扇出的子节点数（口语等价于"一张 page 最多装几个 key"）。

Fan-out 不是工程师拍脑袋定的，是被"页大小 / entry 大小"逼出来的：

单位换算速查

计算机里 "K" 默认 = 1024（2^10），不是 1000。严格场合用 KiB 表示 1024，KB 表示 1000，但工程实践 99% 直接 KB = 1024。

层数 vs 数据量（fan-out = 1000）

层数	可索引的数据量
1	1,000
2	1,000,000
3	1,000,000,000（10 亿）
4	1,000,000,000,000（1 万亿）

通用公式：所需层数 = ⌈log_fanout(N)⌉

为什么节点必须"胖"

如果像二叉树那样 fan-out = 2，管 10 亿数据需要 log₂(10⁹) ≈ 30 层 → 30 次磁盘 I/O = 150ms。 B+ 树 fan-out = 1000 时只要 3 层 = 15ms。差 10 倍。

同样一次 5ms 的 I/O，读 4 个 key 和读 1000 个 key 代价一样，当然要塞满。节点的"胖"是被磁盘物理特性逼出来的最优解。

实际查询为什么常常只要 1 次 I/O

根节点 + 第一层加起来只有几 MB

操作系统会自动把它们缓存在内存里

所以查任意一条数据，通常只有 1 次真正的磁盘 I/O

四、查询全过程（实战）

设树长这样：

查 post_id = 60：

步骤	动作	代价
1	磁盘 I/O：读 page #0 进内存	5ms
2	内存里二分查找：60 落在 50~75，跟随 ptr→#132	纳秒级
3	磁盘 I/O：读 page #132 进内存	5ms
4	内存里找到 60 的真实数据	纳秒级

总 I/O = 2 次。在真实 3 层树上 = 3 次 I/O ≈ 15ms。

五、B+ 树的生长机制

关键事实：B+ 树不是 DBA 设计出来的，是数据自己"长"出来的。

生长全过程（fan-out = 4 演示）

阶段 1：插入第 1 条，只有一张叶子，无根

阶段 2：叶子陆续填满

阶段 3：插入第 5 个（如 40），叶子分裂，自动诞生根

阶段 4-N：继续插入，叶子陆续分裂，每次"复制"一个 separator 到根

阶段 N+1：根 page 自己也满了 → 根分裂 → 诞生新的根 → 树长高一层

两条核心不变量

所有叶子在同一层（完美平衡 / Perfectly Balanced）

任意一条数据的查询代价完全一样

延迟可预测——这在生产系统里比"平均快"重要得多

整个过程对应用透明，无需 DBA 介入

数据从 1 条扩展到 100 亿条，DBA 什么都不用做

B+ 树自带弹性增长，永远不需要重建表

数据涨了树会怎么变？

数据量	树层数	查询 I/O 数	延迟
< 1000	1	1	5ms
< 100 万	2	2	10ms
< 10 亿	3	3	15ms
< 1 万亿	4	4	20ms

每多承载 1000 倍数据，只多 5ms 延迟（且实际上根 + L1 常驻内存，几乎无感知）。

六、B+ 树 vs B 树：关键区别

分裂时 separator 的处理方式：

ㅤ	B 树	B+ 树
separator	移动到父节点（叶子里没了）	复制到父节点（叶子里保留）

为什么 B+ 树必须"复制"

B+ 树的灵魂：所有真实数据只住在叶子层，非叶子节点只是路标。

若 separator 被"移走"，那个 key 对应的真实数据就丢了——用户查 post_id = 70 时只在父节点找到孤零零的数字，没有微博内容、作者、时间。

MySQL InnoDB 选 B+ 树而非 B 树，正因为：

非叶子节点更瘦 → fan-out 更大 → 树更扁 → I/O 更少

叶子能装完整行数据

叶子之间有链表 → 范围查询友好（待补）

七、面试常见拷问点

1. 为什么 MySQL 用 B+ 树而不是哈希表？

哈希不支持范围查询、排序

哈希在大数据量下有冲突链表退化问题

哈希在做模糊匹配（LIKE）时无法利用索引

2. 为什么用 B+ 树而不是 B 树？

非叶子节点更瘦 → fan-out 更大 → 树更扁 → I/O 更少

叶子层有链表 → 范围查询效率高

所有查询代价稳定（必到叶子，路径长度统一）

3. InnoDB 一个 B+ 树节点能存多少条数据？

关键：从页大小、key 大小、指针大小一路推导，不要背数字。

4. 为什么 B+ 树高度通常只有 3-4 层？

fan-out 大（~1000），指数级增长

3 层 = 10 亿数据

根节点和第一层基本常驻内存缓存

实际只需 1 次真磁盘 I/O

5. B+ 树的查询、插入、删除时间复杂度？

都是 O(log_fanout N)，fan-out 大所以常数极小

工程上等同于 O(常数 ≈ 3~4)

八、关键术语索引

中文	English	一句话定义
页	Page	磁盘 I/O 最小单位，InnoDB = 16KB
扇出	Fan-out	一个节点最多扇出的子节点数
分界线	Separator Key	非叶子节点里的 key，划分子节点范围
指针	Pointer	子节点在文件中的页号
非叶子节点	Internal Node	装路标的节点
叶子节点	Leaf Node	装真实数据的节点
分裂	Split	page 满后的拆分操作
完美平衡	Perfectly Balanced	所有叶子在同一层
比较函数	Comparator	决定 key 顺序的规则