数据库要把数据存到磁盘上，又要以尽可能少的磁盘 I/O 把数据找回来。这个矛盾催生了一系列面向磁盘的索引结构（Disk-oriented Index），其中最成功的就是 B-Tree 家族。从 1970 年 Rudolf Bayer 和 Edward McCreight 在波音科学研究实验室提出 B-Tree 起，这个数据结构统治了关系型数据库的索引层超过半个世纪。MySQL/InnoDB、PostgreSQL、SQLite、Oracle、SQL Server——几乎所有主流关系型数据库的默认索引结构都是 B+Tree，B-Tree 的一个变体。
B-Tree 的核心设计目标只有一个：把树的高度压到极低，让每次查找只需要 3 到 4 次磁盘 I/O。它做到这一点的方式是把节点大小对齐到磁盘页（Page），每个节点可以容纳成百上千个键（Key），从而获得极高的扇出（Fanout）。一棵扇出为 500 的 B+Tree，三层就能索引 1.25 亿条记录。
但教科书上的 B-Tree 和生产环境里的 B+Tree 之间隔着大量工程细节：页内怎么布局才能支持变长键值？节点分裂时怎么保证并发安全？怎么减少锁的粒度让读写互不阻塞？怎么批量加载数据而不是一条条插入？怎么通过前缀压缩和后缀截断在同一个页里塞进更多键？
本文从 B-Tree 的基本原理讲起，逐层拆解 B+Tree 的页内布局、分裂合并算法、并发控制方案、压缩优化手段、批量加载策略、写时复制变体，最后落到 InnoDB 的具体实现和可视化调试工具。
一、B-Tree 基本原理
1.1 为什么需要 B-Tree
内存里做查找，平衡二叉搜索树（Balanced Binary Search Tree）已经够用了——红黑树、AVL 树的查找时间复杂度都是 O(log n)。但当数据量大到必须存在磁盘上时，二叉树有一个致命问题：树太高了。
假设有 1 亿条记录，一棵完美平衡的二叉树高度是 log₂(10⁸) ≈ 27。每层一次磁盘 I/O，一次查找就需要 27 次随机读——在机械硬盘（HDD）上每次随机读约 10ms，一次查找就要 270ms，完全不可接受。
问题的根源在于二叉树每个节点只存一个键、只有两个子节点，扇出（Fanout）只有 2。如果把每个节点扩大到一整个磁盘页（通常 4KB 到 16KB），让每个节点能存几百个键、有几百个子节点，树的高度就能压下来。
这就是 B-Tree 的核心思想：用高扇出（High Fanout）换低高度（Low Height），从而把磁盘 I/O 次数降到最低。
1.2 B-Tree 的定义
一棵 m 阶（Order）B-Tree 满足以下性质：
- 每个节点（Node）最多有 m 个子节点；
- 每个非根的内部节点至少有 ⌈m/2⌉ 个子节点；
- 根节点（Root）至少有 2 个子节点（除非树只有根节点）；
- 一个有 k 个子节点的节点包含 k-1 个键；
- 所有叶子节点（Leaf Node）在同一层——这保证了树是完美平衡的。
这些约束保证了两件事：
- 树的高度是 O(log n)：因为每个节点至少半满，扇出至少为 ⌈m/2⌉；
- 查找、插入、删除的时间复杂度都是 O(log n)：每次操作最多从根到叶子走一遍。
1.3 高度估算
设 B-Tree 的阶数为 m，树中有 n 个键。最坏情况下（每个节点恰好半满），树的高度 h 满足：
h ≤ log_{⌈m/2⌉}((n+1)/2)以 InnoDB 为例：页大小 16KB，假设每个键占 8 字节（bigint 主键）、每个页指针占 6 字节，一个内部节点可以容纳约 16384 / (8 + 6) ≈ 1170 个指针，即扇出约 1170。则：
h = 1: 最多 1170 - 1 ≈ 1,169 条记录
h = 2: 最多 1170 × 1169 ≈ 1,367,730 条记录
h = 3: 最多 1170 × 1170 × 1169 ≈ 1.6 × 10⁹ 条记录
h = 4: 最多约 1.87 × 10¹² 条记录三层 B+Tree 就能索引超过 16 亿条记录。考虑到根节点和部分内部节点常驻内存，实际需要的磁盘 I/O 通常只有 1 到 2 次。
1.4 B-Tree 的基本操作
查找（Search）：从根节点开始，在每个节点内部用二分查找（Binary Search）定位键所在的区间，然后沿对应的子指针向下走，直到找到目标键或到达叶子节点。
插入（Insert）：先执行查找，定位到应该插入的叶子节点。如果叶子节点有空间，直接插入。如果叶子节点已满（包含 m-1 个键），需要分裂（Split）：把节点一分为二，中间键提升（Promote）到父节点。如果父节点也满了，继续向上分裂，最坏情况下一直分裂到根节点，树的高度增加 1。
删除（Delete）：先查找到目标键。如果键在叶子节点且删除后节点仍然至少半满，直接删除。否则需要从兄弟节点借键（Redistribution）或与兄弟节点合并（Merge）。如果合并导致父节点的键数低于下限，继续向上合并。
查找路径示意（m=4 的 B-Tree）：
[30]
/ \
[10, 20] [40, 50, 60]
/ | \ / | | \
[5] [15] [25] [35] [45] [55,65]
查找 key=45:
1. 根节点: 45 > 30 → 走右子树
2. [40, 50, 60]: 40 < 45 < 50 → 走第二个子指针
3. 到达叶子节点 [45] → 找到1.5 面向磁盘的设计
B-Tree 是专门为磁盘设计的数据结构，它的每一个设计决策都在减少磁盘 I/O：
- 节点大小等于磁盘页大小：每读一个节点刚好一次 I/O，不浪费带宽；
- 高扇出：树很矮，查找路径上的 I/O 次数少；
- 节点至少半满：空间利用率有下限，不会退化成瘦长的树；
- 有序存储：支持范围查询（Range Query），顺序扫描时可以利用磁盘的顺序读优势。
这些特性让 B-Tree 成为磁盘索引的标准选择，从 1970 年代沿用至今。
二、B+Tree 与 B-Tree 的区别
2.1 B+Tree 的核心改动
B+Tree 是 B-Tree 的一个变体，最早由 IBM 的研究人员在 1970 年代提出。它对 B-Tree 做了两个关键改动：
- 所有数据只存在叶子节点：内部节点（Internal Node）只存键和子指针，不存数据。这意味着内部节点可以塞进更多的键，扇出更高，树更矮。
- 叶子节点用链表（Linked List）串起来：每个叶子节点有一个指向下一个叶子节点的指针（通常是双向链表），范围查询时不需要回到父节点，直接沿链表顺序扫描。
B-Tree vs B+Tree 的结构对比：
B-Tree（数据散布在所有节点）：
[30, data₃₀]
/ \
[10, data₁₀, 20, data₂₀] [40, data₄₀, 50, data₅₀]
B+Tree（数据只在叶子节点）：
[30] ← 内部节点：只有键
/ \
[10, 20] ──→ [30, 40, 50] ← 叶子节点：键 + 数据
链表指针2.2 B+Tree 的优势
更高的扇出：内部节点不存数据，只存键和指针。同样 16KB 的页，B+Tree 的内部节点能容纳的键数量远多于 B-Tree。扇出越高，树越矮，查找需要的 I/O 越少。
范围查询效率高：B-Tree 做范围扫描需要中序遍历（Inorder Traversal），不断在内部节点和叶子节点之间跳转。B+Tree 只需要找到范围起点的叶子节点，然后沿链表顺序扫描，每个叶子节点恰好是一个磁盘页，顺序读性能远好于随机读。
扫描成本可预测：B+Tree 的全表扫描（Full Scan）成本等于叶子节点总数乘以每次 I/O 的时间，与内部节点数量无关。B-Tree 需要遍历所有节点。
缓存效率更好：热点数据的查找路径上只有内部节点，这些节点不包含数据，更小、更容易全部驻留在缓冲池（Buffer Pool）里。
2.3 B+Tree 的代价
单点查询略慢：在 B-Tree 中，如果目标键恰好在靠近根的内部节点，查找可以提前终止。B+Tree 必须走到叶子节点才能拿到数据，查找路径总是从根到叶。不过考虑到内部节点通常常驻内存，这个差异在实践中可以忽略。
键的重复存储：分隔键（Separator Key）在内部节点和叶子节点中都有副本。不过后面会看到，通过后缀截断（Suffix Truncation），内部节点存储的只是键的一个前缀，实际浪费的空间很少。
2.4 为什么数据库都选 B+Tree
对
OLTP（在线事务处理）数据库来说，范围查询是核心需求——SELECT ... WHERE id BETWEEN 100 AND 200
这样的查询无处不在。B+Tree
的叶子链表让范围查询变成顺序扫描，性能提升可达一个数量级。
同时，OLTP 的典型负载是大量的小事务，每个事务只读写几条记录。B+Tree 的内部节点可以全部缓存到内存里，每次单点查找只需要读 1 个叶子页。这让 B+Tree 在实际工作负载下的性能表现几乎是最优的。
下面的表格总结了两者的关键区别：
┌─────────────────┬────────────────────┬─────────────────────┐
│ 特性 │ B-Tree │ B+Tree │
├─────────────────┼────────────────────┼─────────────────────┤
│ 数据存储位置 │ 所有节点 │ 仅叶子节点 │
│ 叶子节点链表 │ 无 │ 有（双向链表） │
│ 内部节点扇出 │ 较低 │ 较高 │
│ 范围查询效率 │ 需要中序遍历 │ 叶子链表顺序扫描 │
│ 单点查找路径 │ 可能在中间层命中 │ 必须到叶子节点 │
│ 全扫描成本 │ 遍历所有节点 │ 只遍历叶子节点 │
│ 空间利用率 │ 键不重复 │ 分隔键有副本 │
│ 实际使用 │ 文件系统（部分） │ 几乎所有 RDBMS │
└─────────────────┴────────────────────┴─────────────────────┘三、页内布局
3.1 页的概念
B+Tree 的每个节点对应磁盘上的一个页（Page）。页是 B+Tree 与磁盘之间的 I/O 单位：读一个节点就是从磁盘读一个页，写一个节点就是把一个页刷回磁盘。
页的大小通常是固定的：InnoDB 默认 16KB，PostgreSQL 默认 8KB，SQLite 默认 4KB。页大小的选择是一个权衡：
- 页越大：扇出越高、树越矮、I/O 次数越少，但每次 I/O 传输的数据量越大，写放大越严重；
- 页越小：写放大小、缓冲池能缓存更多页，但树更高、I/O 次数更多。
3.2 槽位页（Slotted Page）布局
大多数数据库使用槽位页（Slotted Page）布局来组织页内数据。这种布局的核心思想是用一个间接层——槽位数组（Slot Array）——来管理页内变长记录（Variable-length Record）的物理位置。
一个槽位页的结构如下：
┌──────────────────────────────────────────────────┐
│ Page Header │
│ ┌──────────────────────────────────────────────┐ │
│ │ page_id │ page_type │ num_slots │ free_start │ │
│ │ free_end │ checksum │ lsn │ ... │ │
│ └──────────────────────────────────────────────┘ │
├──────────────────────────────────────────────────┤
│ Slot Array (grows →) │
│ ┌──────┬──────┬──────┬──────┬─────────────────┐ │
│ │ S[0] │ S[1] │ S[2] │ S[3] │ ... │ │
│ └──────┴──────┴──────┴──────┴─────────────────┘ │
│ │
│ Free Space（中间空闲区域） │
│ │
│ ┌─────────────────────────────────────────────┐ │
│ │ Cell[3] │ Cell[2] │ Cell[1] │ Cell[0] │ ... │ │
│ └─────────────────────────────────────────────┘ │
│ Cell Data (← grows) │
├──────────────────────────────────────────────────┤
│ Page Trailer │
│ ┌──────────────────────────────────────────────┐ │
│ │ checksum │ │
│ └──────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────┘Page Header：存储页的元数据——页
ID、页类型（叶子页 /
内部页）、槽位数量、空闲空间的起止偏移、校验和（Checksum）、日志序列号（LSN）等。InnoDB
的页头占 38 字节（FIL_PAGE_DATA
偏移量），加上页尾的 8 字节校验信息。
Slot Array：从页头之后向右增长。每个槽位（Slot）是一个 2 字节的偏移量，指向对应的单元（Cell）在页内的物理位置。槽位按键的逻辑顺序排列，但它们指向的单元在物理上可以是无序的。
Cell Data：从页尾向左增长。每个单元包含一条记录的实际数据。单元的物理顺序与逻辑顺序无关——插入新记录时，只需要在空闲区域的末尾追加单元，然后在槽位数组的正确位置插入一个新的偏移量。
Free Space：槽位数组和单元数据之间的空闲区域。当空闲空间耗尽时，先尝试整理碎片（Compaction）——把所有单元紧凑排列，回收被删除单元留下的空洞；如果整理后仍然不够，就触发页分裂。
3.3 为什么用槽位页
槽位页的核心好处是：插入和删除操作不需要移动大量数据。
在一个没有间接层的页中，记录按键顺序紧密排列。插入一条新记录到中间位置，需要把后面的所有记录向后移动。如果记录是变长的，还要处理对齐和碎片问题。
有了槽位数组，插入变成了两步：
- 把新记录的数据追加到单元区域的末尾——O(1)；
- 在槽位数组的正确位置插入一个新的偏移量——需要移动后续的槽位，但每个槽位只有 2 字节，移动的数据量很小。
删除则更简单：把对应的槽位从数组中移除，单元数据标记为可回收。
3.4 内部节点的单元格式
B+Tree 内部节点的每个单元包含一个键和一个子页指针（Child Page Pointer）：
内部节点单元格式：
┌────────────┬───────────┐
│ child_page │ key │
│ (4-6 B) │ (variable)│
└────────────┴───────────┘
内部节点布局（逻辑视图）：
P₀ │ K₁ │ P₁ │ K₂ │ P₂ │ K₃ │ P₃
含义：P₀ 指向所有 key < K₁ 的子树
P₁ 指向所有 K₁ ≤ key < K₂ 的子树
P₂ 指向所有 K₂ ≤ key < K₃ 的子树
P₃ 指向所有 key ≥ K₃ 的子树注意最左边的指针 P₀ 没有对应的键，它指向”小于第一个键”的子树。实现上通常在页头单独存储这个指针。
3.5 叶子节点的单元格式
叶子节点的单元包含键和数据值（或指向数据的指针）：
聚簇索引（Clustered Index）叶子单元：
┌─────────┬───────────────────────┐
│ key │ row data │
│(variable)│ (所有列的实际数据) │
└─────────┴───────────────────────┘
二级索引（Secondary Index）叶子单元：
┌─────────┬───────────────────┐
│ key │ primary key │
│(variable)│ (指回聚簇索引) │
└─────────┴───────────────────┘在 InnoDB 中，聚簇索引的叶子节点直接存储整行数据，而二级索引的叶子节点存储的是对应的主键值，查完二级索引还需要一次”回表”（Bookmark Lookup）到聚簇索引去取完整行。
3.6 页内查找
在页内定位一个键的过程通常使用二分查找（Binary Search）。槽位数组按键的逻辑顺序排列，二分查找直接在槽位数组上进行：
// 伪代码：页内二分查找
int page_search(Page *page, Key target) {
int lo = 0;
int hi = page->num_slots - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
Key mid_key = get_key_at_slot(page, mid);
int cmp = compare_keys(mid_key, target);
if (cmp == 0) return mid; // 找到
if (cmp < 0) lo = mid + 1; // 目标在右半部分
else hi = mid - 1; // 目标在左半部分
}
return lo; // 插入位置
}对于包含几百个键的页，二分查找最多需要约 10 次比较，全在内存中完成，耗时可以忽略不计。
四、分裂与合并
4.1 节点分裂（Node Split）
当一个节点已满（键的数量达到上限），需要插入新键时，就触发分裂。分裂是 B+Tree 维持平衡的核心机制。
叶子节点分裂的步骤：
- 创建一个新的叶子页；
- 把原页中后半部分的记录移动到新页；
- 更新叶子链表指针：新页插入到原页和原页的下一个兄弟之间；
- 把新页的最小键（分隔键）和新页的指针插入到父节点。
分裂前：
父节点：[... | 30 | ...]
|
叶子节点：[10, 15, 20, 25, 30] ← 已满，要插入 18
分裂后：
父节点：[... | 20 | 30 | ...]
| |
左叶子：[10, 15, 18] 右叶子：[20, 25, 30]
──────────→
叶子链表指针内部节点分裂的步骤类似，但中间键是被”提升”（Promote）到父节点，而不是被复制。
4.2 分裂的传播
如果父节点在接收新的分隔键后也满了，父节点也要分裂，分隔键继续向上传播。最坏情况下，分裂一路传播到根节点：根节点分裂后，创建一个新的根节点，树的高度增加 1。
这种传播在实际中很少发生。以 InnoDB 为例，一个 16KB 的内部节点可以容纳约 1170 个指针，节点满的概率随着层数向上递减。
根节点分裂（树长高 1 层）：
分裂前：
根节点：[10, 20, 30, 40, 50] ← 已满
分裂后：
新根：[30]
/ \
[10, 20] [40, 50]4.3 分裂策略的选择
传统 B+Tree 总是在节点正中间分裂，即左右各占一半（50/50 Split）。但在实际负载中，插入模式往往不是均匀随机的：
顺序插入（如自增主键）：每次插入都到最右边的叶子节点，50/50 分裂会导致左边的节点只有一半满就再也不会被写入，空间利用率只有约 50%。
改进策略：
- 90/10 分裂：InnoDB
检测到顺序插入模式时，只把最后一条记录放到新页，原页保持几乎满——这样空间利用率接近
100%。InnoDB 通过页头中的
PAGE_LAST_INSERT和PAGE_DIRECTION字段来判断插入模式。 - 前缀分裂（PostgreSQL）：选择分隔键时，尽量选择一个短前缀，减少内部节点存储分隔键的空间开销。
4.4 节点合并（Merge）与重分配（Redistribution）
删除操作可能导致节点低于半满的下限。B-Tree 规定此时需要重新平衡：
重分配（Redistribution）：如果兄弟节点有多余的键，从兄弟节点借一个键过来，同时更新父节点中的分隔键。
重分配示例：
操作前（左节点过空，右兄弟有余量）：
父节点：[... | 30 | ...]
| |
左叶子：[10] 右叶子：[30, 35, 40, 45]
操作后（从右兄弟借一个键）：
父节点：[... | 35 | ...]
| |
左叶子：[10, 30] 右叶子：[35, 40, 45]合并（Merge）：如果兄弟节点也没有多余的键（恰好半满），就把两个节点合并为一个，同时删除父节点中对应的分隔键。合并可能级联向上传播。
4.5 实践中的简化
很多数据库在实现中并不严格执行合并操作。原因有几个：
- 合并的代价高：需要加锁两个节点及其父节点，并发冲突大；
- 删除后往往很快又有插入：合并了很快又要分裂，白忙一场；
- 空间利用率的下限足够宽松：节点半满时空间利用率已经是 50%，可以接受。
PostgreSQL 的 B+Tree
实现（nbtree）不做合并，只标记空页供后续复用。InnoDB
在页中记录数低于某个阈值（由 MERGE_THRESHOLD
控制，默认 50%）时才尝试合并，且合并失败不会重试。SQLite
在页面使用率低于一定比例时才触发合并。
五、并发控制
5.1 问题的本质
B+Tree 的并发控制面临一个两难：
- 读操作不修改树，理论上多个读可以完全并行；
- 写操作可能触发分裂或合并，影响从叶子到根的整条路径上的多个节点；
- 如果简单地给整棵树加一把大锁，并发度就降为 1，性能不可接受。
目标是让读与读完全并行，读与写尽可能并行，写与写至少在操作不同叶子节点时可以并行。
5.2 闩锁与锁的区别
在讨论 B+Tree 并发控制之前，需要区分两个容易混淆的概念：
锁（Lock）：数据库事务级别的并发控制机制，由锁管理器（Lock Manager）管理，支持死锁检测，持续时间跨越整个事务。保护的是逻辑资源——行、表、键范围。
闩锁（Latch）：物理层的互斥原语，类似于操作系统的互斥锁（Mutex）或读写锁（RWLock），持续时间极短（通常是一次页操作的时间），不需要死锁检测（通过编码规范保证无死锁）。保护的是物理资源——内存中的页。
B+Tree 的并发控制用的是闩锁，不是锁。
┌─────────────┬──────────────────┬──────────────────┐
│ 属性 │ Lock（锁） │ Latch（闩锁） │
├─────────────┼──────────────────┼──────────────────┤
│ 保护对象 │ 逻辑资源（行等） │ 物理资源（页等） │
│ 持续时间 │ 整个事务 │ 一次操作 │
│ 死锁处理 │ 死锁检测 + 回滚 │ 编码保证无死锁 │
│ 等待策略 │ 等待队列 │ 自旋 / 睡眠 │
│ 模式 │ S/X/IS/IX/SIX │ Read / Write │
│ 开销 │ 较大 │ 很小 │
└─────────────┴──────────────────┴──────────────────┘5.3 闩锁耦合（Latch Coupling / Crabbing）
闩锁耦合（Latch Coupling），也叫螃蟹协议（Crabbing Protocol），是 B+Tree 并发控制的经典方案。核心思想是：在树上向下遍历时，像螃蟹一样交替地”抓住”和”放开”节点。
读操作的协议：
- 对当前节点加读闩锁（Read Latch）；
- 对子节点加读闩锁；
- 释放当前节点的读闩锁；
- 重复 2-3，直到到达叶子节点。
任何时刻，读操作最多持有两个读闩锁（当前节点和子节点），且持有时间很短。
写操作的协议（悲观方式）：
- 对当前节点加写闩锁（Write Latch）；
- 对子节点加写闩锁；
- 如果子节点是”安全的”（不会因为这次操作而分裂或合并），释放所有祖先节点的写闩锁；
- 重复 2-3，直到到达叶子节点。
“安全的”意思是：对于插入，节点还没满（不会分裂）；对于删除，节点超过半满（不会合并）。
闩锁耦合示意（插入操作）：
[R] ← ① 加 Write Latch
/ \
[A] [B] ← ② 对 A 加 Write Latch，A 未满 → 释放 R 的锁
/ \
[C] [D] ← ③ 对 C 加 Write Latch，C 未满 → 释放 A 的锁
↓
执行插入，释放 C 的锁5.4 悲观闩锁的问题
悲观方式的闩锁耦合有一个实际问题：写操作从根节点开始就加写闩锁。根节点是全局热点，所有操作都要经过它。如果一个写操作对根节点加了写闩锁，所有其他操作（包括读操作）都必须等待。
在高并发场景下，根节点上的写闩锁成为严重的瓶颈。
5.5 乐观闩锁耦合（Optimistic Latch Coupling）
为了解决悲观闩锁的根节点瓶颈，可以采用乐观策略：
- 乐观阶段：从根到叶子的遍历过程中，只对内部节点加读闩锁（而不是写闩锁），对叶子节点加写闩锁；
- 检查阶段：如果叶子节点的操作不需要修改任何内部节点（即不需要分裂或合并），直接完成操作；
- 回退阶段：如果需要分裂或合并，释放所有闩锁，用悲观模式重新从根节点开始。
大多数写操作（插入到未满的叶子、删除后叶子仍然超过半满）不会触发分裂或合并，因此乐观策略在绝大多数情况下都能成功，很少需要回退。这大大减少了根节点上写闩锁的竞争。
乐观闩锁耦合流程：
正常路径（大多数情况）：
R(read) → A(read) → C(read) → Leaf(write) → 插入成功 → 释放
回退路径（需要分裂时）：
R(read) → A(read) → C(read) → Leaf(write) → 发现需要分裂
→ 释放所有闩锁
→ R(write) → A(write) → C(write) → Leaf(write) → 分裂 + 插入5.6 B-link Tree
B-link Tree 是 Lehman 和 Yao 在 1981 年提出的一种并发友好的 B+Tree 变体（论文标题为”Efficient Locking for Concurrent Operations on B-Trees”）。核心改动是给每个节点增加一个”右链指针”（Right-link Pointer）和一个”高键”（High Key）。
右链指针：每个节点存储一个指向同层右兄弟的指针（叶子节点本来就有这个指针，B-link Tree 把它扩展到内部节点）。
高键：每个节点存储一个上界——这个节点中所有键都小于等于高键。如果要查的键大于高键，说明目标在右兄弟中。
这两个改动的好处是：在分裂过程中，即使一个读操作看到了”半完成”的分裂状态（新节点已创建但父节点还没更新），它也可以通过右链指针找到正确的节点。这意味着分裂操作不需要同时锁住父节点和子节点，每次只需要锁住一个节点，大大降低了锁的粒度。
B-link Tree 结构：
[30 | high=50] ──→ [70 | high=∞]
| |
[10, 20, 30] ──→ [40, 50] ──→ [60, 70, 80]
high=30 high=50 high=∞
分裂进行中（父节点尚未更新）：
[30 | high=50] ──→ [70 | high=∞]
| |
[10, 20] ──→ [25, 30] ──→ [40, 50] ──→ [60, 70, 80]
high=22 high=30 high=50 high=∞
新节点
此时查找 key=25：
1. 从父节点 [30] 向下走
2. 到达 [10, 20]，发现 25 > high=22
3. 跟随右链指针到 [25, 30] → 找到5.7 Optimistic Lock Coupling（OLC）
Optimistic Lock Coupling 是 Viktor Leis 等人在 2016 年提出的方案（论文：“The ART of Practical Synchronization”），后来在 2019 年的论文”Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method”中做了系统化阐述。
OLC 的核心思想是：用版本号（Version）代替读闩锁。每个节点维护一个版本计数器（Version Counter），写操作会递增版本号。读操作不加锁，而是在开始时记录版本号，在结束时检查版本号是否变化。如果版本号没变，说明读期间没有并发写，读到的数据是一致的；如果版本号变了，重试。
// OLC 伪代码
struct Node {
uint64_t version; // 低位为写锁标记，高位为版本号
// ...
};
// 读操作
uint64_t v = node->version;
if (is_locked(v)) { retry(); } // 如果正在被写，等待
// ... 读取数据 ...
if (node->version != v) { retry(); } // 数据可能被修改，重试
// 写操作
lock(node); // 设置写锁标记
// ... 修改数据 ...
unlock(node); // 清除写锁标记，递增版本号OLC 的读操作完全不修改共享状态（不加锁、不修改计数器），因此在多核 CPU 上不会产生缓存行失效（Cache Line Invalidation），扩展性非常好。Leis 等人的实验表明，OLC 在高并发读为主的负载下性能可以接近无锁数据结构。
六、前缀压缩与后缀截断
6.1 问题背景
B+Tree 的性能直接取决于扇出——每个页能容纳多少个键。扇出越高，树越矮，I/O 越少。因此，在同样大小的页中塞进更多的键，就是一个核心优化目标。
对于变长键（Variable-length
Key），尤其是字符串键，直接存储完整的键值往往非常浪费空间。同一个页内的键通常有很长的公共前缀（Common
Prefix）——比如一张 URL 表的索引，同一个页内的 URL 可能都以
https://www.example.com/products/ 开头。
6.2 前缀压缩（Prefix Compression）
前缀压缩的思想很简单：同一个页内的键，把公共前缀提取出来只存一份，每个键只存去掉公共前缀后的后缀部分。
未压缩：
Slot 0: "https://www.example.com/products/apple"
Slot 1: "https://www.example.com/products/banana"
Slot 2: "https://www.example.com/products/cherry"
Slot 3: "https://www.example.com/products/date"
前缀压缩后：
公共前缀: "https://www.example.com/products/" (存一次)
Slot 0: "apple"
Slot 1: "banana"
Slot 2: "cherry"
Slot 3: "date"实际实现中更常用的是增量编码（Delta Encoding）或前缀长度编码：每个键只存储与前一个键不同的部分，以及公共前缀的长度。
增量编码：
Slot 0: prefix_len=0, suffix="apple" (完整键)
Slot 1: prefix_len=0, suffix="banana" (与前一个键无公共前缀)
Slot 2: prefix_len=0, suffix="cherry"
Slot 3: prefix_len=0, suffix="date"
对于有公共前缀的键更有效：
Slot 0: prefix_len=0, suffix="user:1001:name"
Slot 1: prefix_len=9, suffix="02:name" (与前一个键共享 "user:100")
Slot 2: prefix_len=9, suffix="03:email"
Slot 3: prefix_len=9, suffix="03:name"PostgreSQL 的 B-Tree 实现使用了一种类似的前缀压缩方案（称为 deduplication 和 suffix truncation 的组合优化），在 PostgreSQL 13 及以后版本中引入了 deduplication 特性来减少索引大小。
6.3 后缀截断（Suffix Truncation）
后缀截断是针对内部节点的优化。内部节点中的分隔键（Separator Key）不需要完整——它只需要能区分左右子树就够了。
考虑分裂时的场景：左子树的最大键是
"Alexander"，右子树的最小键是
"Bert"。分隔键不需要是
"Bert"，它可以是 "B" 甚至
"B"——只要能把 "Alexander" 和
"Bert" 分开就行。
不使用后缀截断：
内部节点：[... | "Bert" | ...]
5 字节
使用后缀截断：
内部节点：[... | "B" | ...]
1 字节
节省了 80% 的空间后缀截断让内部节点中的每个分隔键变得更短，从而在同一个页中能容纳更多的分隔键，提高扇出。
PostgreSQL 的 nbtree 实现从 PostgreSQL 12 开始在插入路径中使用后缀截断（参见 Peter Geoghegan 的相关提交），这是一个显著的优化，对字符串索引的页扇出提升效果明显。
6.4 压缩的代价
前缀压缩增加了页内操作的复杂度：
- 查找变慢：二分查找时需要先重建完整键再比较，或者用特殊的比较函数直接在压缩格式上操作；
- 插入 / 删除变复杂：修改一个键可能影响相邻键的前缀长度；
- 随机访问性能下降：增量编码要从第一个键开始才能重建第 n 个键的完整值。
实际实现中通常做折中：把页内的键分成若干组（Group），每组内使用前缀压缩，组间不压缩。这样二分查找可以先在组间跳转（无需解压），定位到目标组后再在组内顺序解压比较。
分组前缀压缩（Group Prefix Compression）：
Group 0 (restart point):
[0] "user:1001:email" ← 完整键
[1] prefix=10, "02:email"
[2] prefix=10, "03:email"
[3] prefix=10, "04:email"
Group 1 (restart point):
[4] "user:1005:email" ← 完整键
[5] prefix=10, "06:email"
[6] prefix=10, "07:email"
[7] prefix=10, "08:email"
二分查找先比较 [0] 和 [4]（完整键），再在组内顺序查找。这种分组方式在 LevelDB/RocksDB 的 SSTable（Sorted String Table）中广泛使用——每隔 16 个键设一个重启点（Restart Point），重启点存完整键。
七、批量加载（Bulk Loading）
7.1 为什么需要批量加载
逐条插入数据到 B+Tree 的效率很低：
- 每次插入都要从根遍历到叶子：O(log n) 次页访问；
- 随机 I/O：如果键不是按顺序插入的，每次插入可能访问不同的叶子页，缓冲池命中率低；
- 大量分裂开销：节点不断地填满、分裂、再填满，浪费 CPU 和 I/O；
- 并发争用：分裂需要修改多个节点，闩锁冲突严重。
如果有大量数据需要一次性导入（比如初始化数据库、恢复备份），逐条插入可能需要数小时甚至数天。批量加载（Bulk Loading）可以把时间缩短到几分钟。
7.2 自底向上构建（Bottom-up Construction）
批量加载的标准方法是自底向上构建（Bottom-up Construction）：
- 对输入数据排序：按键的顺序排序所有记录。如果数据已经有序（如从另一个有序索引导出），可以跳过这一步；
- 填充叶子层：按顺序扫描排序后的数据，依次填入叶子页。每个叶子页填到目标装填因子（Fill Factor）后，创建一个新的叶子页，并记录分隔键；
- 构建内部层：收集叶子层产生的所有分隔键和页指针，用同样的方式填入内部节点页。如果内部节点层也超过一页，继续向上构建，直到根节点只有一页。
自底向上构建过程：
输入数据（已排序）：[5, 10, 15, 20, 25, 30, 35, 40, 45]
假设每个叶子页最多容纳 3 个键，装填因子 100%
第一步：填充叶子层
Leaf₁: [5, 10, 15] → 分隔键 20
Leaf₂: [20, 25, 30] → 分隔键 35
Leaf₃: [35, 40, 45]
第二步：构建内部层
Internal₁: [P(Leaf₁), 20, P(Leaf₂), 35, P(Leaf₃)]
第三步：Internal₁ 就是根节点
结果：
[20, 35]
/ | \
[5,10,15] [20,25,30] [35,40,45]
──→ ──→7.3 装填因子（Fill Factor）
装填因子控制每个页在批量加载时填充到多满。选择的依据取决于后续的写入模式：
- Fill Factor = 100%：页完全填满。空间利用率最高，但后续任何插入都会立即触发分裂；
- Fill Factor = 70-90%：每个页预留一些空间给后续的随机插入，减少分裂频率；
- Fill Factor = 50%：等同于逐条插入的最坏情况，通常没有必要这么低。
InnoDB 的 ALTER TABLE ... ALGORITHM=INPLACE
重建索引时使用的默认装填因子是约 93%（实际由
innodb_fill_factor 参数控制，默认
100，表示尽量填满，但会预留一些空间给页头和内部记录）。PostgreSQL
的 CREATE INDEX 默认装填因子是 90%（可通过
fillfactor 存储参数调整）。
7.4 实际数据库中的批量加载
InnoDB 的排序索引构建（Sorted Index
Build）：MySQL 5.7
及以后，CREATE INDEX 和
ALTER TABLE ... ADD INDEX
使用排序索引构建。流程是先扫描聚簇索引提取所有键值对，在内存中（或借助临时文件）排序，然后自底向上构建
B+Tree。这比旧版本的逐条插入快 3 到 5 倍。
PostgreSQL 的索引构建：PostgreSQL 的
CREATE INDEX
默认使用排序方式构建——先用外部排序（External
Sort）把数据排好序，然后自底向上构建
B-Tree。CREATE INDEX CONCURRENTLY
则使用逐条插入方式，以避免阻塞其他事务，但速度明显更慢。
SQLite 的排序器（Sorter）：SQLite 在
CREATE INDEX
时先把所有键值对写入一个临时的排序器，排序后批量写入 B-Tree
页。
-- PostgreSQL：创建索引时指定装填因子
CREATE INDEX idx_users_email ON users (email) WITH (fillfactor = 80);
-- MySQL/InnoDB：排序索引构建是默认行为
ALTER TABLE users ADD INDEX idx_email (email), ALGORITHM=INPLACE;7.5 批量加载的 I/O 模式
批量加载的 I/O 模式以顺序写为主：
- 排序阶段：如果数据量超过内存，使用外部归并排序，产生顺序读写的临时文件；
- 构建阶段：叶子页按顺序生成、按顺序写入磁盘，几乎没有随机 I/O。
相比逐条插入的大量随机 I/O，批量加载对磁盘更友好，尤其在 HDD 上性能差异可达数十倍。
八、写时复制 B-Tree
8.1 什么是写时复制 B-Tree
写时复制（Copy-on-Write，CoW）B-Tree 是一种特殊的 B+Tree 变体：修改一个节点时，不是就地更新（In-place Update）原页，而是把修改写到一个新页，然后更新父节点的指针指向新页。由于父节点也被修改了，父节点也要写到新位置——这个过程一直向上传播到根节点。每次事务提交都会产生一个新的根节点。
写时复制过程（修改叶子节点 C）：
原始状态：
Root → [A]
/ \
[B] [C] ← 修改 C
修改后：
Root' → [A'] ← 新根
/ \
[B] [C'] ← 新页 C'，原 C 保留
旧 Root → [A] ← 旧版本仍然完整可读
/ \
[B] [C]8.2 LMDB 与 BoltDB 的实现
LMDB（Lightning Memory-Mapped Database）是 CoW B+Tree 最著名的实现之一，由 Howard Chu 为 OpenLDAP 项目开发。BoltDB 是 LMDB 的 Go 语言移植版，被 etcd 用作底层存储引擎。
LMDB 的设计特点：
双根节点：LMDB 维护两个根节点（存储在文件头部的两个元数据页中），交替更新。事务提交时，新的树根写入未在使用的那个元数据页，然后通过
fdatasync()持久化。如果写入过程中崩溃，另一个元数据页仍然指向上一个一致的版本；不需要 WAL：传统的就地更新 B+Tree 需要预写日志（Write-Ahead Log，WAL）来保证崩溃恢复。CoW B+Tree 的旧版本始终保持完整，不需要 WAL——这简化了代码，也减少了写放大；
读事务无锁：旧版本的树在有读事务引用时不会被回收。读事务只需要记录自己开始时的根节点指针，就能看到一个一致的快照（Snapshot），不需要任何锁。
LMDB 的双元数据页机制：
Meta Page 0 → Root A (txn_id = 100)
Meta Page 1 → Root B (txn_id = 101) ← 当前最新
新事务提交：
Meta Page 0 → Root C (txn_id = 102) ← 更新这个
Meta Page 1 → Root B (txn_id = 101)
读事务使用 txn_id 最大的那个根8.3 CoW B-Tree 与 MVCC
CoW B-Tree 天然支持多版本并发控制（Multi-Version Concurrency Control，MVCC）。每次事务提交都产生一个新版本的树，旧版本在没有活跃读事务引用时才能被回收。
这和 PostgreSQL 的 MVCC 实现形成对比：PostgreSQL 在每一行中存储版本信息（xmin/xmax），需要定期 VACUUM 回收旧版本。CoW B-Tree 的版本管理在树的级别，粒度更粗但实现更简单。
8.4 CoW B-Tree 的代价
写放大：每次修改都要复制从叶子到根的整条路径。如果树有 4 层，每层一个 4KB 页，一次修改就需要写 16KB。如果一个事务修改了散布在不同叶子节点的多条记录，写放大更严重——每个叶子节点的修改都要独立传播到根；
碎片化：新页写到文件末尾或空闲位置，文件的物理布局会变得碎片化。LMDB 使用空闲页列表（Free Page List）来复用已释放的页，但碎片化仍然是长期运行中的问题；
空间回收延迟：只要有活跃的读事务引用旧版本，旧页就不能回收。一个长时间运行的读事务会阻止空间回收，导致数据库文件不断增长。LMDB 和 BoltDB 都有这个问题——长事务是它们在生产环境中最常见的陷阱。
8.5 适用场景
CoW B-Tree 适合以下场景：
- 读多写少：读事务完全无锁，写事务有路径复制的开销；
- 需要一致性快照：备份、复制、分析查询；
- 嵌入式场景：不需要独立的 WAL 模块，代码简单，依赖少（LMDB 的核心代码只有约 1 万行 C）；
- 配置存储：etcd 使用 BoltDB 存储集群配置，写入频率低但要求强一致性。
不适合的场景：写密集型负载、大量随机更新、需要长事务。
九、InnoDB B+Tree 实现分析
9.1 InnoDB 的索引组织
InnoDB 使用 B+Tree 作为唯一的数据存储结构——不仅索引是 B+Tree，数据本身也存储在 B+Tree 的叶子节点中。这种设计称为索引组织表（Index-Organized Table）。
聚簇索引（Clustered Index）：InnoDB 的每张表都有一个聚簇索引，通常是主键。聚簇索引的叶子节点存储完整的行数据。如果表没有显式主键，InnoDB 会选择一个唯一非空索引作为聚簇索引；如果也没有，InnoDB 会生成一个隐藏的 6 字节行 ID（Row ID）作为聚簇索引。
二级索引（Secondary Index）：二级索引的叶子节点存储的是索引键加上对应行的主键值。查询通过二级索引找到主键后，还需要到聚簇索引中做一次回表查找（Bookmark Lookup）。
InnoDB 索引结构示意：
聚簇索引（主键 = id）：
内部节点：[100 | 200 | 300]
/ | | \
叶子节点：
[id=1, name="Alice", ...] → [id=100, name="Bob", ...] → [id=200, ...]
二级索引（name）：
内部节点：["Bob" | "Eve"]
/ | \
叶子节点：
[name="Alice", pk=1] → [name="Bob", pk=100] → [name="Eve", pk=200]
查询 WHERE name = "Bob":
1. 在二级索引中查找 "Bob" → 得到 pk=100
2. 在聚簇索引中查找 id=100 → 得到完整行9.2 InnoDB 页结构
InnoDB 的默认页大小是 16KB（可通过
innodb_page_size 参数调整为 4KB、8KB、32KB 或
64KB）。每个页的结构如下：
InnoDB 16KB 页结构：
┌────────────────────────────────────────────┐
│ FIL Header (38 bytes) │
│ - 页号、页类型、校验和、LSN │
│ - 前一页和后一页的指针 │
├────────────────────────────────────────────┤
│ Page Header (56 bytes) │
│ - 记录数、堆顶指针、空闲链表指针 │
│ - 页方向、最后插入位置 │
│ - 页级别（叶子 = 0，内部 > 0） │
│ - 索引 ID │
├────────────────────────────────────────────┤
│ Infimum Record (13 bytes) │
│ - 虚拟最小记录（所有记录的逻辑起点） │
├────────────────────────────────────────────┤
│ Supremum Record (13 bytes) │
│ - 虚拟最大记录（所有记录的逻辑终点） │
├────────────────────────────────────────────┤
│ User Records │
│ - 实际的数据记录（变长） │
│ - 按插入顺序排列（物理无序） │
│ - 通过 next_record 指针形成有序链表 │
├────────────────────────────────────────────┤
│ Free Space │
├────────────────────────────────────────────┤
│ Page Directory (Slot Array) │
│ - 每 4-8 条记录一个槽位 │
│ - 用于页内二分查找 │
├────────────────────────────────────────────┤
│ FIL Trailer (8 bytes) │
│ - 校验和、LSN（用于校验页完整性） │
└────────────────────────────────────────────┘几个关键设计：
- Infimum 和 Supremum：每个页有两条虚拟记录——Infimum（下确界）比页中所有真实记录都小，Supremum（上确界）比所有真实记录都大。它们简化了边界处理逻辑；
- 记录链表：页内的记录通过
next_record偏移量形成单向有序链表。遍历页中记录的方式是从 Infimum 出发，沿next_record走到 Supremum； - Page Directory：InnoDB 不对每条记录都建立槽位，而是每 4 到 8 条记录建一个槽位（称为”稀疏目录”）。页内查找先对 Page Directory 做二分查找定位到一个组，再在组内顺序遍历。
9.3 记录格式
InnoDB 支持两种行格式（Row Format），以
COMPACT 格式为例（DYNAMIC 和
COMPRESSED 是其变体）：
InnoDB COMPACT 行格式：
┌─────────────────────┬────────────────────┬──────────────┐
│ Variable-length │ Record Header │ Column │
│ Field Lengths │ (5 bytes) │ Data │
│ (逆序存储) │ │ │
├─────────────────────┼────────────────────┼──────────────┤
│ len₃ | len₂ | len₁ │ info_bits(4) │ col₁ | col₂ │
│ │ n_owned(4) │ | col₃ | ... │
│ │ heap_no(13) │ │
│ │ record_type(3) │ │
│ │ next_record(16) │ │
└─────────────────────┴────────────────────┴──────────────┘其中 record_type
区分了普通记录（0）、内部节点记录（1）、Infimum（2）、Supremum（3）。
9.4 自适应哈希索引（Adaptive Hash Index）
InnoDB 有一个独特的优化：自适应哈希索引（Adaptive Hash Index，AHI）。它在 B+Tree 之上自动构建一个哈希索引（Hash Index），缓存热点页的查找路径。
工作原理：InnoDB 监控 B+Tree 的查找模式。当它发现某个索引前缀的查找非常频繁（命中率超过阈值），就自动为这些键建立一个内存哈希表，直接映射到叶子页中的记录，跳过 B+Tree 的遍历过程。
不使用 AHI：查找 key=42
Root Page → Internal Page → Leaf Page → Record
3 次页访问
使用 AHI：查找 key=42
Hash Table: 42 → (page_no, offset)
1 次直接定位AHI 在等值查询（Point Query）密集的场景下效果显著，但也有开销：
- 维护哈希表需要额外的内存（从缓冲池中分配）；
- 页分裂或页驱逐时需要更新或失效哈希表中对应的条目；
- 在某些负载下（如范围扫描为主），AHI 反而是负担。
可以通过 innodb_adaptive_hash_index
参数控制是否启用，默认启用。MySQL 8.0 将 AHI
分成了多个分区（由
innodb_adaptive_hash_index_parts 控制，默认
8），减少了全局闩锁争用。
9.5 InnoDB 的页分裂实现
InnoDB 的页分裂在源码中由
btr_page_split_and_insert() 函数实现（MySQL 8.0
源码路径：storage/innobase/btr/btr0btr.cc）。关键步骤：
选择分裂点：如果检测到顺序插入模式（
PAGE_LAST_INSERT指向页尾且PAGE_DIRECTION为PAGE_RIGHT），使用不对称分裂（右侧新页只包含新插入的记录）。否则使用对称分裂（从中间分）；创建新页：从表空间分配一个新的空闲页；
移动记录：把分裂点之后的记录从原页移动到新页；
更新链表指针：新页插入到叶子层的双向链表中——原页的
FIL_PAGE_NEXT指向新页，新页的FIL_PAGE_PREV指向原页；插入分隔键到父页：把新页的最小键和页号插入到父节点。如果父节点也满了，递归分裂；
写 redo log：整个分裂过程记录到 redo log，保证崩溃恢复后分裂状态一致。
9.6 InnoDB 的 Change Buffer
对于二级索引的插入和更新，如果目标叶子页不在缓冲池中，InnoDB 不会立即从磁盘读取该页。而是把修改操作缓存到变更缓冲区（Change Buffer），等到目标页下次因为其他查询被读入缓冲池时，再把缓存的修改合并（Merge）进去。
Change Buffer 本身也是一棵 B+Tree，存储在系统表空间（ibdata1）中。它可以显著减少二级索引维护的随机 I/O，特别是在写密集的负载下。
Change Buffer 工作流程：
1. INSERT INTO t (name) VALUES ('foo');
→ 二级索引页 P 不在缓冲池中
→ 把 "插入 name='foo'" 缓存到 Change Buffer
2. 后续查询需要读页 P
→ 从磁盘读入页 P
→ 合并 Change Buffer 中关于页 P 的所有操作
→ 页 P 现在包含了最新数据十、B+Tree 可视化与调试
10.1 为什么需要可视化
在排查数据库性能问题时，仅靠 EXPLAIN
和执行计划往往不够。有时候需要直接看 B+Tree 的物理状态：
- 某个索引的树高是多少？内部节点有几层？
- 叶子页的填充率如何？是不是有大量半空的页（说明频繁分裂）？
- 页分裂集中在哪些区域？是否存在热点页？
- 索引膨胀（Index Bloat）有多严重？空间利用率是多少？
10.2 InnoDB 的 innodb_ruby
innodb_ruby 是 Jeremy Cole 开发的一个 Ruby
工具（项目名为 innodb_ruby，GitHub 仓库
jeremycole/innodb_ruby），可以解析 InnoDB
的表空间文件（.ibd
文件），以可读的方式展示页结构、B+Tree
状态、记录内容等。
常用命令示例：
# 查看表空间概览
innodb_space -f t.ibd space-summary
# 查看 B+Tree 的层级结构
innodb_space -f t.ibd -p 3 page-dump
# 查看索引的树高和页数统计
innodb_space -f t.ibd space-index-pages-summary
# 遍历叶子页，统计每个页的记录数和填充率
innodb_space -f t.ibd -p 3 index-recurseinnodb_space space-index-pages-summary
的输出类似：
page index level data free records
3 15 2 462 15074 33
4 15 0 9812 5765 446
5 15 0 15234 342 692
6 15 0 15234 342 692
7 15 1 4776 10800 339
...其中 level=0 是叶子页，level=1
是第一层内部节点，level=2
是根节点。data 和 free
显示每个页的数据量和空闲空间，可以直接看出填充率。
10.3 PostgreSQL 的 pageinspect
PostgreSQL 内置了 pageinspect
扩展，可以直接查看 B-Tree 索引页的内容。
-- 启用扩展
CREATE EXTENSION pageinspect;
-- 查看 B-Tree 索引的元信息（根页、树高、叶子页数等）
SELECT * FROM bt_metap('idx_users_email');
-- 输出示例：
-- magic | version | root | level | fastroot | fastlevel | ...
-- --------+---------+------+-------+----------+-----------+
-- 340322 | 4 | 3 | 2 | 3 | 2 |
--
-- root=3: 根节点在第 3 页
-- level=2: 树高 2（不包含叶子层），实际有 3 层
-- 查看特定页的统计信息
SELECT * FROM bt_page_stats('idx_users_email', 3);
-- 输出示例：
-- blkno | type | live_items | dead_items | avg_item_size | ...
-- -------+------+------------+------------+---------------+
-- 3 | r | 42 | 0 | 18 |
--
-- type='r': root 页；'i': internal；'l': leaf
-- 查看页内的具体条目
SELECT * FROM bt_page_items('idx_users_email', 3);
-- 输出示例：
-- itemoffset | ctid | itemlen | data
-- ------------+---------+---------+--------------------------
-- 1 | (1,0) | 16 | 0x...
-- 2 | (3,1) | 18 | 0x616c69636510.4 理解页分裂
通过可视化工具，可以诊断页分裂问题。典型的诊断流程：
查看树高：如果索引很小但树高异常（如只有几千行但树高为 4），说明可能有大量空页或碎片；
检查叶子页填充率：如果大量叶子页只有 50% 左右的填充率，说明页分裂很频繁。正常情况下叶子页填充率应该在 70% 以上；
检查页的分布：如果页号不连续（如 3, 100, 5, 200, 7），说明物理顺序和逻辑顺序差异大，范围扫描会产生大量随机 I/O。
10.5 InnoDB 的 INFORMATION_SCHEMA 工具
MySQL 提供了一些系统表来观察 B+Tree 的状态：
-- 查看索引统计信息
SELECT
index_name,
stat_name,
stat_value,
stat_description
FROM mysql.innodb_index_stats
WHERE table_name = 'users';
-- 输出示例：
-- index_name | stat_name | stat_value | stat_description
-- -----------+------------+------------+------------------
-- PRIMARY | n_leaf_pages| 1024 | Number of leaf pages
-- PRIMARY | size | 1088 | Number of pages
-- PRIMARY | n_diff_pfx01| 500000 | Distinct valuesn_leaf_pages 是叶子页数量，size
是索引总页数（包含内部节点），两者之差就是内部节点页的数量。如果
size 远大于
n_leaf_pages，说明可能有大量空洞需要
OPTIMIZE TABLE 回收。
-- 查看缓冲池中各索引页的状态
SELECT
index_name,
COUNT(*) AS pages_in_buffer,
SUM(is_old) AS old_pages,
SUM(IF(is_old = 'NO', 1, 0)) AS young_pages
FROM information_schema.innodb_buffer_page
WHERE table_name LIKE '%users%'
GROUP BY index_name;10.6 调试页分裂的实战案例
场景：一个应用使用 UUID 作为主键，发现写入性能随数据量增长急剧下降。
分析思路：
- UUID 是随机值，插入位置随机分布在整个 B+Tree 中；
- 几乎每次插入都命中不同的叶子页，缓冲池命中率低；
- 大量叶子页只有约 50% 的填充率（因为 50/50 分裂），空间浪费严重；
- 页分裂频繁触发，每次分裂需要修改 3 个页（原页、新页、父页）并写 redo log。
解决方案：
- 使用有序 UUID（如 UUID v7，基于时间戳生成，保持时间顺序），让插入模式接近顺序插入；
- 或者使用自增整数主键，把 UUID 放到二级索引。
-- 查看 InnoDB 的页分裂次数（需要开启 innodb_monitor）
SELECT
name,
count
FROM information_schema.innodb_metrics
WHERE name LIKE '%page_split%';
-- 输出示例：
-- name | count
-- ------------------------------+-------
-- index_page_splits | 15234
-- index_page_reorg_attempts | 1823
-- index_page_reorg_successful | 1820参考资料
论文
R. Bayer, E. McCreight, “Organization and Maintenance of Large Ordered Indexes,” Acta Informatica, vol. 1, no. 3, pp. 173–189, 1972. B-Tree 的原始论文。
D. Comer, “The Ubiquitous B-Tree,” ACM Computing Surveys, vol. 11, no. 2, pp. 121–137, 1979. B-Tree 各种变体的经典综述。
P. L. Lehman, S. B. Yao, “Efficient Locking for Concurrent Operations on B-Trees,” ACM Transactions on Database Systems, vol. 6, no. 4, pp. 650–670, 1981. B-link Tree 的原始论文，提出了右链指针和高键的概念。
V. Leis, M. Haubenschild, T. Neumann, “Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method,” IEEE Data Engineering Bulletin, vol. 42, no. 1, 2019. Optimistic Lock Coupling 的系统阐述。
G. Graefe, “A Survey of B-Tree Locking Techniques,” ACM Transactions on Database Systems, vol. 35, no. 3, 2010. B-Tree 锁技术的全面综述。
G. Graefe, “Modern B-Tree Techniques,” Foundations and Trends in Databases, vol. 3, no. 4, pp. 203–402, 2011. 现代 B-Tree 工程技术的百科全书式综述。
书籍
A. Petrov, Database Internals: A Deep Dive into How Distributed Data Systems Work, O’Reilly, 2019. 第 2 至 7 章系统讲解了 B-Tree 的存储布局、分裂合并、并发控制和磁盘结构。
R. Ramakrishnan, J. Gehrke, Database Management Systems, 3rd Edition, McGraw-Hill, 2003. 第 9 至 11 章覆盖了 B+Tree 索引的基本理论。
源码与文档
MySQL/InnoDB 源码，
storage/innobase/btr/btr0btr.cc，B+Tree 分裂和合并的核心实现。版本参考：MySQL 8.0。PostgreSQL 源码，
src/backend/access/nbtree/，nbtree 模块。版本参考：PostgreSQL 16。Peter Geoghegan, “Suffix Truncation for B-Tree Indexes,” PostgreSQL 12 release notes。Howard Chu, LMDB: Lightning Memory-Mapped Database Technical Information, http://www.lmdb.tech/doc/. LMDB 的官方技术文档。
Jeremy Cole, innodb_ruby, https://github.com/jeremycole/innodb_ruby. InnoDB 表空间解析工具。
上一篇: 存储引擎概览：堆文件到 LSM-Tree 的演化路径 下一篇: Buffer Pool：数据库的内存管理
同主题继续阅读
把当前热点继续串成多页阅读，而不是停在单篇消费。
存储工程索引
汇总本站存储工程系列文章，覆盖 HDD、SSD、NVMe、持久内存、索引结构、压缩、分布式存储与对象存储。
【存储工程】存储引擎概览：堆文件到 LSM-Tree 的演化路径
数据库系统的架构可以划分为两大层：上层的查询处理层负责解析 SQL、生成执行计划、优化查询；下层的存储引擎（Storage Engine）负责把数据持久化到磁盘，并在需要时高效地把数据取回来。查询处理层决定"做什么"，存储引擎决定"怎么存、怎么取"。同一个查询处理层可以对接不同的存储引擎——MySQL 的 InnoDB…
【存储工程】索引结构：从 B+Tree 到倒排索引
数据库里存了一亿行数据，要找出 userid 42 的那一行。没有索引的做法是全表扫描（Full Table Scan）——从第一个数据页读到最后一个数据页，逐行比对。假设每个数据页 16 KB，一亿行占 20 GB，即使顺序读能跑到 500 MB/s，也需要 40 秒。加一个 B+Tree 索引，三次磁盘 I/O 就…
【存储工程】XFS 架构：大文件与高并发
XFS 诞生于 1993 年的硅谷图形公司（Silicon Graphics, Inc.），最初运行在 IRIX 操作系统上。 SGI 的核心业务是高性能计算和影视后期制作，客户需要处理的文件动辄几十 GB 甚至数 TB。 当时主流的 EFS（Extent File System）在面对这类工作负载时已经力不从心：元数…