B 树(B-tree)与 B+ 树(B+-tree)是以磁盘为存储介质而设计的平衡多叉查找树。它们的核心指标不是比较次数,而是一次查找需要读取多少个页。本文讨论这两种结构的定义、维护过程与工程参数,磁盘与页缓存的关系见 linux: 页缓存与 IO 性能,在 MySQL 索引与执行计划中的落地方式见 mysql: 索引与执行计划,数据页与表空间的组织见 mysql: InnoDB 存储引擎,内存中有序结构的对照见 跳表 与 Redis 核心与数据结构,复杂度记号的口径见 复杂度与算法分析。

一、起源:磁盘访问代价与树高

1.1 内存与磁盘的代价差异

数据结构的基本操作由"比较"与"移动"构成,在内存中,这两件事的代价都在纳秒量级,因此二叉平衡树以比较次数的对数上界作为设计目标。一旦数据放在磁盘上,代价结构发生变化:

操作 数量级 说明
内存随机访问 纳秒级(约 100ns) 比较与指针跳转的代价
内存顺序访问 低于随机访问 缓存行命中时进一步降低
固态盘随机读 数十微秒量级 无机械动作,但仍受控制器与通道限制
机械盘随机读 毫秒量级 寻道与旋转等待主导
机械盘顺序读 单位数据代价远低于随机读 磁头几乎不移动,吞吐由转速与密度决定

内存与磁盘之间存在四到五个数量级的差距,其中随机访问与顺序访问之间的差距又有一到两个数量级。这一事实带来两点结论:

  1. 比较本身几乎免费,访问介质才是成本。 在内存中,多比较几次以减少一次指针跳转未必划算;在磁盘上,只要少读一个页,多比较几百次键都是值得的。这直接说明了为什么磁盘索引可以在节点内顺序比较大量键。
  2. 比较次数不再是首要指标,页访问次数才是。 一次查找的耗时近似为"访问的页数 × 单次页访问代价",因此索引结构的设计目标从"最小化比较次数"转为"最小化页访问次数"。

1.2 页:一次 IO 的数据量

磁盘不以字节为单位读写。块设备以扇区(通常 512 字节或 4096 字节)为最小寻址单位,文件系统以块为单位组织数据,内核与数据库又各自引入页的概念。层级如下:

应用程序请求  →  数据库页(InnoDB 默认 16KB)
              →  文件系统块(通常 4KB)
              →  块设备扇区(512B 或 4KB)
              →  设备内部页与擦除块(固态盘)

真正的物理约束是:设备一次读写会搬运一个不小于某个阈值的连续区间。这意味着:

  • 若一次只需要 40 字节的记录,而设备最小读取单位是 4KB,那么这次 IO 的实际代价与读取 4KB 相同,多出的部分被浪费。
  • 既然 IO 的代价与数据量近似阶梯式,把"一次 IO 需要的数据"尽量集中到同一区间,就相当于把多次 IO 合并成一次。

Linux 页缓存以 4KB 页为单位缓存文件内容,并在此基础上做预读与回写,其读写路径与脏页机制见 linux: 页缓存与 IO 性能。数据库在这层之上再定义自己的页(InnoDB 默认 16KB),由数据库自身而非内核决定缓存的粒度与淘汰策略,理由是数据库更清楚页内记录的语义与访问局部性,相关取舍见 mysql: InnoDB 存储引擎 第 2.2 节。

由此得到索引结构的第一个设计约束:一个树节点的大小应与一次 IO 的搬运单位对齐,即一个节点大致等于一个页。 一次节点访问对应一次页读取,节点内的比较在内存中完成、不产生额外 IO。

1.3 降低树高的直接手段

若节点的大小被固定为一个页(记为 P 字节),每个节点能容纳的子节点数(扇出,fanout)由"每个条目占用的字节数"决定。设每个键加子指针占 s 字节,则扇出 f ≈ P / s。

树高与扇出的关系,以完全平衡的多叉树近似:

叶子层节点数 ≈ n / (每叶可容纳的记录数)
树高(层数) ≈ log_f(节点总数) + 1
查找一次访问的页数 ≈ 树高

对同一数据量,扇出越大则树高越低。三种结构的对照估算如下(假设每行约 1KB、主键 8 字节、页大小 16KB):

结构 单节点容量 扇出 10⁶ 行的树高 10⁸ 行的树高
二叉平衡树 1 个键 2 约 20 层 约 27 层
B 树(键与行同放节点内) 约 16 个键 约 17 约 5 层 约 7 层
B+ 树(内部节点只存键,叶子存行) 内部节点约 1000 个键,叶子约 16 行 内部 1000,叶子 16 3 层 4 层

上表的口径需要说明:B 树的节点里同时存放键与整行数据,单节点能容纳的键数被行宽限制,扇出只有十几;B+ 树的内部节点不存行数据,同样的页可以容纳上千个键,扇出被放大到近千倍。因此 B+ 树在数据量增长三个数量级时树高几乎不变,这是它成为磁盘索引默认结构的根本原因。

表中的层数按节点平均填充率估算。若按"每个节点仅达到最小填充率"的最坏情形推算,高度上界要再高一层左右;而实际系统中树的上层节点通常常驻缓冲池,真正的磁盘读次数往往只有一到两次。

1.4 节点大小与页大小的对齐

节点大小与页大小的关系有两种做法:

  1. 节点等于页(页式索引)。 一个节点恰好占一个页,节点访问即页访问,页内偏移不需要额外寻址。InnoDB、MyISAM、多数数据库索引采用这种做法。
  2. 节点等于页的整数倍或子集(块式索引)。 文件系统与部分存储引擎使用固定块大小作为节点,块大小可独立于文件系统块大小配置。

选择第一类的理由是可预测:每次节点访问恰好对应一次 IO,缓存与预读的单位一致,统计"查找一次访问了几个页"才有意义。若节点小于页,一次页读取会浪费页内其余空间;若节点大于页,一次节点访问会拆成多次 IO,页访问次数与节点访问次数不再一一对应,复杂度分析失去意义。

页大小本身是一个参数而不是常量。页越大,单页能容纳的键越多、扇出越大、树高越低,但单次 IO 的数据量也越大,页内二分查找的比较次数增加,一次页分裂搬运的数据量也增加。该取舍在 2.6 节量化。


二、原理

2.1 磁盘友好的结构约束

2.1.1 页与块

两个概念需要区分:

  • 页(page):索引结构的基本存取单位,也是缓存与 IO 的单位。一个页存放一个节点,页内顺序排列若干键与子指针。
  • 块(block):存储层分配与传输的单位,大小通常小于或等于页。页在磁盘上按块边界对齐存放,一次页读取在内核层可能拆成多个块的请求,但对索引结构不可见。

页在磁盘上的物理位置不一定连续。InnoDB 用区(extent)把相邻页组织在一起以减少碎片,但一个索引的叶子页分散在多个区中是常态,因此"索引的物理读"以随机读为主,只有叶层的连续扫描才接近顺序读。

2.1.2 树高与 IO 次数的关系

一次查找的 IO 次数等于从根到命中节点访问的页数,即树高。树高与数据量的关系为对数关系,这带来三条工程结论:

  1. 数据量增长一百倍,IO 次数只增加一层左右。 以扇出 1000 计算,10⁶ 行与 10⁸ 行的层数可能只差一层,这就是索引对数据量增长不敏感的原因。
  2. 缓存的边际收益随层级递减。 根节点每次查找都要访问,必然常驻内存;越靠近叶子,页数越多、复用率越低,越容易在缓存中被淘汰。因此实际磁盘读集中在最下面一到两层,扩大缓冲池对索引查找的收益有上限。
  3. 树高是不可忽略的量。 层数从 3 增到 4 意味着每次查找多一次页访问。若这些页未命中内存,按随机读的毫秒量级估算,单次查询的延迟直接翻倍还多。

2.1.3 阶数与扇出

  • 阶(order)m:一个节点的子指针上限。B 树与 B+ 树的阶描述的是"最多能分出几个分支",因此一个内部节点最多有 m 个子指针、m − 1 个键。
  • 扇出(fanout):实际使用的子指针数。阶是容量上限,扇出是实际值,平均扇出决定实际树高。

扇出由三个因素决定:

因素 影响 典型取值
页大小 页越大,扇出越大 InnoDB 默认 16KB
键的长度 键越长,单页容纳的键越少 BIGINT 主键 8 字节,CHAR(36) 主键最多 144 字节
子指针的长度 页号的大小,通常固定 InnoDB 为 4 字节页号,加键长后每项约 12 至 20 字节

以 InnoDB 的 16KB 页为例,非叶节点每项为"键 + 4 字节页号",键为 8 字节时每项 12 至 14 字节(含记录头开销),单页约容纳 1000 项;键改为 144 字节的字符主键后每项接近 150 字节,单页只能容纳约 100 项,扇出下降一个数量级,树高相应上升。这是"主键应短"的结构性依据,其代价分析见 mysql: 索引与执行计划 第 2.2 节。

2.2 B 树

2.2.1 定义与性质

一棵 m 阶 B 树满足以下条件:

  1. 节点内键有序:每个节点内的键按升序排列,k₁ < k₂ < … < kⱼ。
  2. 子树区间划分:内部节点若有 j 个键,则有 j + 1 个子指针;子指针 pᵢ 指向的子树中所有键都落在区间 (kᵢ₋₁, kᵢ) 内,两端视为无界。即键把自己"夹"出一段区间,子树中的键不能越界。
  3. 所有叶子在同一层:树是完全平衡的,任何一条从根到叶的路径长度相同。
  4. 键数量的上下界:除根以外的每个节点至少含 ⌈m/2⌉ − 1 个键,最多含 m − 1 个键;根节点至少含 1 个键(空树除外)。
  5. 数据可以出现在任意节点:B 树中每个键只出现一次,行数据(或指向行的引用)与键存放在同一个节点里。

第 4 条是 B 树区别于普通多叉查找树的关键:它强制了节点的最低填充率。若没有下界,可能出现一条很长的链导致树高退化;下界保证每个节点至少分叉出 ⌈m/2⌉ 个分支,从而使树高被限制在对数范围内——这与平衡二叉树通过旋转维持平衡是同一个目的,只是手段换成了节点分裂与合并。

m = 4 的 B 树示意(每个节点 1 至 3 个键)

                  [ 20 | 40 ]                      根:2 个键,3 个子指针
                 /     |     \
       [ 8 | 12 ]   [ 25 | 30 ]   [ 50 ]
       /   |   \     /   |   \     /   \
    [1 3] [9] [15] [22] [27] [35] [45] [55]     所有叶子在同一层

第 2 条的性质决定了查找算法:在节点内定位键所在的区间后,沿着对应的子指针下降,进入的子树中所有键都在该区间内,因此下降过程中不会跳过目标。

2.2.2 查找

search(node, key):
    while node 不是叶子:
        在 node.keys 中二分,找到满足 keys[i-1] < key <= keys[i] 的位置 i
        if key == node.keys[i-1]:        # 该键存放在内部节点上
            return node                     # B 树可以在内部节点提前命中
        node = node.children[i]
    在叶子的 keys 中二分,命中则返回该节点,否则返回不存在

两个要点:

  • 节点内用二分查找。 节点可能容纳上百个键,顺序比较会使每层的比较次数达到 O(m)。二分把每层比较次数压到 O(log m),而比较在内存中的代价远低于一次页访问,因此页访问次数不变的前提下减少比较是纯收益。
  • 查找可能在内部节点提前结束。 这是 B 树的一个优势(见 2.3.1),代价是查找路径长度不固定,难以用"固定层数"描述所有的访问模式。

2.2.3 插入与分裂

插入总是发生在叶子层,然后自底向上修复。步骤为:

  1. 沿查找路径下降到目标叶子,记录路径上的所有节点(后续更新父节点时需要)。
  2. 若键已存在,按业务语义处理(拒绝或更新);否则按序插入到叶子的正确位置。
  3. 若插入后该节点的键数超过 m − 1,则分裂:
  • 取中间位置的键 k_mid,新建一个右兄弟节点;
  • 左节点保留 k_mid 之前的键,右节点保留 k_mid 之后的键;
  • k_mid 提升到父节点,并在父节点中插入指向新右兄弟的子指针(在 B 树中,k_mid 不在子节点保留副本,它是"上移"而不是"复制");
  • 若父节点因此超限,对父节点重复分裂,直到某个祖先未超限;
  • 若根节点分裂,则新建一个根,树高加一。
插入 26 到 m = 4 的树(m = 4 节点最多 3 个键;目标叶子 [ 25 | 28 | 30 ] 已满)

插入后:  叶子 [ 25 | 26 | 28 | 30 ]                     4 个键,超过上限 3
取中间键 28 上移,拆为两个节点:
    父节点 [ 20 | 40 ]  →  [ 20 | 28 | 40 ]             在原子指针位置插入分隔键与右兄弟指针
    左节点 [ 25 | 26 ]      右节点 [ 30 ]                键 28 上移后不在子节点保留

若父节点因此超过上限,对父节点重复上述过程;若分裂发生在根节点,则新建根,树高加一。

需要说明的是,分裂点不一定取正中间。取正中间使两个节点各占一半,空间利用率约 50%;若插入是单调递增的(自增主键),把分裂点偏向左侧可以只新建一个右节点、把原有大部分键留在左节点,使左节点接近满载。多数实现(含 InnoDB)对"插入到最右页且满"的情形做了顺序插入优化,直接分配新页而不分裂已有页。

分裂的代价:一次分裂至少写两个页(原节点与兄弟节点)、更新一个父节点,父节点满时继续向上。一次插入可能引起多页写入,这是写放大的来源之一。此外分裂过程中相关页需要加锁,是并发写入的争用点。

2.2.4 删除与借位合并

删除需要维持第 2.2.1 节第 4 条的填充率下界:

  1. 定位键所在的节点并删除。若该键在内部节点上,不能用"直接摘链"的方式删除(内部节点同时承担子树区间划分的职责),而是用中序前驱或后继替换它:取左子树的最大键或右子树的最小键上移到该位置,再在叶子层删除那个被取走的键。这样把一个内部节点的删除转化为叶子节点的删除。
  2. 若删除后节点键数低于 ⌈m/2⌉ − 1,发生下溢,按两个方向修复:
  • 借位(旋转):相邻兄弟节点的键数大于下界时,从兄弟借一个键。对 B 树,借位是"经父节点中转的旋转":兄弟的某个键上移到父节点,父节点原来的分隔键下降到本节点。
  • 合并:两个相邻兄弟的键数都等于下界时,把本节点、兄弟节点以及父节点中的分隔键合并为一个节点;合并后父节点少了一个键与一个子指针,可能继续下溢,自底向上重复处理。
  1. 若根节点因合并只剩一个子指针且没有键,把该子节点提升为新根,树高减一。
m = 4 删除导致的下溢(每个非根节点的键数下界为 ceil(4/2) - 1 = 1)
沿用 2.2.1 节的示例树:父节点 [ 8 | 12 ],子节点 [ 1 3 ]、[ 9 ]、[ 15 ]

借位(兄弟有余量):删除 9 → 节点为空,发生下溢;左兄弟 [ 1 3 ] 有 2 个键,大于下界
    左兄弟的最大键 3 上移到父节点,父节点的分隔键 8 下降到本节点
    结果:父节点变为 [ 3 | 12 ],子节点变为 [ 1 ]、[ 8 ]、[ 15 ]
    父节点的分隔键必须随旋转更新,否则区间划分与子树内容不一致

合并(兄弟也无余量):删除 27 → 节点为空;左右兄弟 [ 22 ] 与 [ 35 ] 都只有 1 个键
    父节点 [ 25 | 30 ] 中的分隔键 25 与两侧子节点并为一体
    结果:父节点变为 [ 30 ],子节点变为 [ 22 与 25 ]、[ 35 ]
    父节点少了一个键与一个子指针;若父节点因此下溢,则对它重复借位或合并

借位与合并的区别在于是否修改父节点的分隔键:借位后父节点的分隔键必须更新(区间边界变了),合并后父节点少一个键与一个子指针。这两处的下标账目最容易出错,细节见 3.1.4 节。

2.2.5 高度与节点数的关系

设 B 树的阶为 m,含 n 个键,记 t = ⌈m/2⌉ 为最小度数。

  • 每个节点的最小分叉数为 t。 根至少 2 个子节点,深度为 d 的层至少有 2·t^(d−1) 个节点。
  • 高度上界:n + 1 ≥ 2·t^(h−1) 推出 h ≤ log_t((n + 1) / 2) + 1(h 按层数计,根为第 1 层),这是各节点仅达到最小填充率时的最坏情形。
  • 高度下界即满载情形:h ≥ log_m(n + 1)。

以 m = 1000、n = 10⁹ 为例,t = 500,最坏情形上界为 log_500(5×10⁸) + 1 ≈ 4.2,即不超过 5 层;满载下界为 log_1000(10⁹ + 1) = 3 层。实际树高落在两者之间,取决于分裂与合并造成的平均填充率。这解释了 2.1.2 节的结论:扇出足够大时,数据量从百万增长到十亿,层数几乎不变。

反过来,这个公式也说明下界填充率直接决定最坏树高。若实现允许节点高度稀疏(长期只含少量键),最坏树高会向 log_t 一侧靠拢;B* 树通过把下界提高到 2/3 来压缩这一差距(见 2.4 节)。

2.3 B+ 树

2.3.1 与 B 树的差别

B+ 树可以看作对 B 树的三处修改:

维度 B 树 B+ 树
数据存放位置 键与行数据可以出现在任意节点 行数据(或行引用)只存放在叶子节点
内部节点内容 键与数据,键不重复 只存分隔键与子指针,分隔键是叶子键的副本
叶子节点连接 无横向连接 叶子节点按序以链表(通常双向)相连
键是否重复 每个键出现一次 内部节点与叶子节点中各出现一次
查找路径长度 可变,可能在内部节点命中 固定,必须走到叶子
单节点容纳的键数 受行宽限制,扇出小 内部节点扇出大,可比 B 树高一个数量级
删除内部键的处理 需用前驱或后继替换 内部节点的分隔键可以保留,只删叶子中的副本
范围查询 需要中序遍历并回溯 定位起点后沿叶子链表顺序推进
m = 4 的 B+ 树示意

                    [ 20 | 40 ]                    内部节点:只有分隔键
                   /     |     \
                  /      |      \
     [ 8 | 12 ]      [ 25 | 30 ]      [ 50 | 60 ]  更下层的内部节点
      /   |   \       /   |   \        /   |   \
   ┌────┬────┬────┬────┬────┬────┬────┬────┬────┐
   │1 3 │ 8  │9 12│15 20│22 25│27 30│35 40│45 50│55 60│
   └─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┴─┬──┘
     └────┴────┴────┴────┴────┴────┴────┴────┘      叶子:全部键 + 数据,横向链表

三点结构性推论:

  1. B+ 树的键在内部与叶子各存一份。 内部节点的分隔键只是路标,指向"这个键及之后的记录在右侧子树中"。因此 B+ 树的内部键可以比叶子中最小的实际键更大(删除后不回溯更新),实现上允许"过期分隔键",只要它仍能把区间正确划分即可。
  2. 查找路径长度固定,等于树高。 每次查找都要走到叶子,无法提前返回。代价是固定多一次比较,收益是查找代价可预测,且所有记录位于同一层,访问代价均匀。
  3. 叶子链表是范围扫描的基础。 这是 B+ 树区别于 B 树最重要的一点,2.3.2 节展开。

2.3.2 数据库为什么偏爱 B+ 树

在磁盘索引的场景下,B+ 树相对 B 树有三项优势与一项劣势。

优势一:内部节点能容纳更多键,扇出更大、树高更低。 B 树的节点里同时放键与行,单节点能容纳的键数被行宽限制;B+ 树的内部节点只有键与页号,行数据全部下沉到叶子。同一页大小下,B+ 树的内部扇出可以高出约两个数量级。按 1.3 节的估算,10⁶ 行数据在 B 树中需要约 5 层,在 B+ 树中只需要 3 层,每次查找少读两个页。

优势二:叶子链表使范围扫描与顺序访问可直接推进。 WHERE id BETWEEN a AND b、ORDER BY 扫描、前缀匹配这些操作,在 B+ 树中的实现是"定位第一个不小于 a 的叶子,然后沿叶子链表向右推进直到超过 b"。推进过程访问的页在逻辑上连续,实际读取接近顺序读;若换成 B 树,范围查询需要按中序遍历回溯到父节点再下降到下一个叶子,访问模式变成随机的页跳转。这一差别在只查少量行时不明显,在扫描大量行时决定数量级的差距,机制与页缓存、预读的配合见 3.3 节。

优势三:维护操作更简单,且删除不必回溯。 B+ 树删除记录时只删叶子中的条目,内部节点的分隔键可以保留不动(过期键只影响区间边界的精确性,不影响正确性),因此无需在中序遍历中寻找前驱或后继来替换内部键。内部节点的分裂与合并仍然存在,但涉及的键是纯路标,不携带数据,搬运的数据量小。

劣势:查找路径固定,无法提前命中。 若某个高频查询的键恰好位于上层内部节点,B 树可以在更少的 IO 内返回,B+ 树仍必须走到叶子。当树高为 2 至 3 层且上层常驻内存时,这项差异通常小于其他三项带来的收益,因此数据库在两者之间普遍选择 B+ 树。MySQL 的两种索引结构对照与选择依据见 mysql: 索引与执行计划 第 2.1.1 节。

2.3.3 聚簇索引与二级索引

B+ 树在数据库中的落地有两种形态,区别在于叶子节点存放什么。

形态 叶子内容 数量 用途
聚簇索引(clustered index) 完整行记录 每表一个 表数据本身,按主键有序组织
二级索引(secondary index) 索引列值 + 主键值 可多个 加速非主键列的定位

InnoDB 采用索引组织表(index-organized table):表数据就是聚簇索引的叶子,两者不是两份独立结构。由此产生三条结构性后果:

  1. 主键决定数据在磁盘上的排列顺序。 主键单调递增时,新记录总是追加到最右侧叶子页,写入接近顺序写;主键随机(UUID、哈希值)时,插入位置散布在整棵树中,持续触发页分裂与随机写。这是"主键应尽量单调"的结构性原因,与 2.2.3 节的分裂策略直接相关。
  2. 二级索引的叶子里存的是主键值,不是行地址。 行地址会随页分裂与页整理变化,无法稳定引用;存主键则可以通过一次聚簇索引查找定位到最新位置。代价是查询非索引列时需要用主键回到聚簇索引取整行,即回表。
  3. 主键长度被放大到所有二级索引。 每个二级索引的每条记录都要附加一份主键值,主键从 8 字节变为 36 字节的字符串时,索引体积、缓冲池占用与 IO 次数同步上升。回表代价、覆盖索引与联合索引列顺序的规则见 mysql: 索引与执行计划 第 2.2 至 2.4 节,行格式与页内记录组织见 mysql: InnoDB 存储引擎 第 2.3.3 节。

一种常见的非聚簇形态是 MyISAM 与多数"堆表"数据库:表数据按插入顺序存放在堆文件中,所有索引都是二级索引,叶子存放行地址(row identifier)。这种组织方式的插入代价与主键无关,但按主键范围扫描需要额外排序或大量随机读,且行地址会随行移动而变化。

2.4 B 树家族的变体

B 树(填充率提高到 2/3)。* B 树的节点填充率下界为 1/2,导致最坏树高与平均树高之间存在约一层的差距,也让空间利用率的下限停在 50%。B* 树把下界提高到 2/3,并改变分裂策略:当节点满时先检查相邻兄弟是否还有空间,有则把部分键迁移(redistribute)过去而不分裂;兄弟也满时,把两个节点与新增键分成三个节点(2 变 3),每个节点填充率约 2/3。收益是空间利用率与最坏树高同时改善,代价是实现复杂度上升,且分裂时需要同时锁定两个兄弟节点。

聚簇与非聚簇。 2.3.3 节已讨论。需要补充的是聚簇的推广形态:部分数据库支持"索引组织表 + 溢出段",把超宽行拆到溢出页,使聚簇索引的叶子仍只存较窄的记录头与主键,从而维持内部扇出;InnoDB 的 DYNAMIC 行格式即把超长变长列存放到溢出页,页内只保留指针,其取舍见 mysql: InnoDB 存储引擎 第 2.3.4 节。

写时复制与消息下推。 两类针对特定工作负载的变体:

  • 写时复制(copy-on-write)B 树。 修改节点时不原地改写,而是把新版本写到新位置并自底向上更新父指针,最后原子地切换根指针。收益是旧版本保持完整,可支持快照与崩溃一致性;代价是写放大明显,随机主键下尤其严重。btrfs 与 ZFS 的元数据树采用这一思路。
  • 消息下推树(fractal tree index)。 在内部节点中设置一块消息缓冲区,把插入与删除先作为消息追加到缓冲区并只写一条顺序日志,待缓冲区满时批量下推到子节点。收益是把随机写转换为顺序写,代价是读操作需要合并路径上所有缓冲区中的消息。TokuDB 采用这一结构。

内存中的 B 树变体(Bw-tree)。 在内存中,B 树原本的页对齐优势消失,但它的扇出特性仍可减少缓存缺失。Bw-tree 的做法是:节点内容不可原地修改,每次更新生成一条增量记录(delta record)挂到该节点的增量链头部,用一次内存中的 CAS 原子地完成挂接;定期把长增量链合并为新的基本节点并更新一个映射表(mapping table)中的指针。这样写操作完全无锁,读操作需要沿增量链合并出差分结果。它把 B 树从"页对齐的磁盘结构"改造成"无锁的内存索引",思路与跳表用局部指针改写替代旋转是一致的。

2.5 与平衡二叉树和跳表的对照

三种结构都是有序索引,差异来自它们面向的存储介质与维护方式;平衡二叉树的有序性、退化成因与平衡手段见 二叉树与二叉搜索树 与 平衡树:AVL 与红黑树。

维度 二叉平衡树(AVL、红黑树) 跳表 B+ 树
每个节点的分支数 2 期望 1/(1 − p) 个后继指针 页内扇出可达上千
树高(10⁶ 元素) 约 20 层 约 log₂n,即约 20 层 3 层
查找一次的介质访问 20 次指针跳转,对应 20 次页访问(磁盘上不可接受) 层间下降为随机访问 3 次页访问
平衡方式 旋转与重新着色 随机层数 节点分裂与合并,按页平衡
最坏复杂度 O(log n),确定 O(n),概率极低 O(log n),由填充率下界保证
范围查询 中序遍历需要栈或线索化 沿第 0 层顺序推进 定位起点后沿叶子链表顺序推进
结构开销 每节点三个指针加颜色位 期望 p/(1 − p) 个后继指针 页内指针,页级开销分摊到上百条记录
缓存局部性 沿指针自根向下,节点分散在堆中 底层顺序推进好,层间下降随机 页内连续,页间按需读取
并发更新 旋转影响多个节点的父子关系,无锁实现困难 局部指针 CAS,无锁实现成熟 页级闩锁,可做到只锁路径上的页
适用介质 内存 内存 磁盘

对照得出的结论可以分三层:

  1. 树高决定了磁盘上的可行性。 二叉平衡树与跳表的层数都是 log₂n 量级,在内存中每层跳转是纳秒级,20 层跳转的代价可以接受;在磁盘上每一层都可能对应一次页访问,20 次随机读按毫秒量级计算就是几十毫秒,不可接受。B+ 树把每个节点能容纳的分支数提高三个数量级,直接把层数压到 3 至 4 层,这是它能用于磁盘的唯一理由。
  2. 范围查询的代价又反过来影响选择。 在内存中,哈希表的等值查找优于所有有序结构,但它不支持范围查询;需要有序性时,跳表与红黑树的量级相同,差异落在实现成本、排名支持与常数因子上,取舍依据见 跳表 第 3.6 节。B+ 树在磁盘上的叶子链表不仅是范围查询的实现手段,也直接决定了顺序扫描是否为顺序 IO。
  3. "页"这一约束在内存中不成立。 内存没有"一次 IO 搬运一页"的阶梯式代价,因此把节点做得很大(如 16KB)只会浪费内存带宽与缓存行、加剧一次修改的搬运量。B+ 树的优势依赖页对齐,脱离磁盘场景后这一优势消失。Redis 的有序集合因此选择跳表而非 B+ 树,其编码切换条件与理由见 Redis 核心与数据结构 第 2.2 节;内存中的并发有序映射在 Java 侧由 ConcurrentSkipListMap 承担,对照见 Java 集合框架实现原理。

关于最坏情况的表述口径需要保持一致:B+ 树的高度上界是确定的,前提是填充率下界被严格执行;跳表的对数结论是期望值,最坏为 O(n)。两者的差别见 跳表 第 2.2.4 节与 复杂度与算法分析 第 2.3 节。

2.6 工程参数

2.6.1 页大小、扇出与树高

扇出的计算。 内部节点每项占用"键长 + 子指针长 + 记录头开销"。以 InnoDB 为例,键为 8 字节 BIGINT、页号为 4 字节,加上每项约 2 至 4 字节的管理开销,每项约 14 字节;16KB 页扣除页头页尾约 200 字节后,单页可容纳约 1100 项,取整按 1000 估算。

树高的计算。 记叶子可容纳记录数为 L、内部扇出为 F、总记录数为 n:

叶子层页数         = ceil(n / L)
树高(层数)       = 1 + ceil(log_F(叶子层页数))
查找一次的页访问数 = 树高

代入 L = 16、F = 1000 的估算:

记录数 n 叶子层页数 内部层数(含根) 树高 查找的页访问数
10⁴ 625 1 2 2
10⁶ 62500 2 3 3
10⁸ 6.25×10⁶ 3 4 4
10¹⁰ 6.25×10⁸ 3 4 4
10¹² 6.25×10¹⁰ 4 5 5

记录数从 10⁴ 增长到 10¹²(八个数量级),页访问数只从 2 增到 5。这是 B+ 树最重要的定量特征,也是"索引性能对数据量不敏感"的准确来源。

页大小的取舍。 若其他条件不变,页从 16KB 改为 4KB:扇出下降为约 280,叶子容纳记录数下降为约 4。代入上表的口径,10⁸ 行时叶子层页数由 6.25×10⁶ 增到 2.5×10⁷,内部层数由 3 增到 4,树高由 4 变为 5,每次查找多读一页;反之页放大到 32KB 可使同一数据量的树高减少一层(16KB 下 10⁸ 行 4 层,32KB 下 3 层),但一次页分裂搬运的数据量翻倍,页内与其他结构的 IO 粒度也一并变大。InnoDB 的页大小在建库时确定后不可更改,因此这一参数需要在初始化阶段结合平均行宽与访问模式一次性确定。

2.6.2 键长对扇出的影响

扇出与键长成反比,因此键的选择会直接改变树高:

主键类型 键长 内部节点每项字节数 单页约容纳项数 10⁸ 行时的树高
INT 4 约 10 约 1600 4
BIGINT 8 约 14 约 1100 4
二进制 16 字节(UUID 压缩存放) 16 约 22 约 740 4
CHAR(36)(utf8mb4,UUID 文本) 最多 144 约 150 约 100 5

结论与做法:

  1. 键长的惩罚是非线性的。 键长增长 18 倍(8 字节到 144 字节)使内部扇出下降到约十分之一,而树高在中等数据量下可能只增加一层;但在特别大的数据量下,一层的差距会被每次查询的页访问次数放大。此外键变长会同时放大所有二级索引的体积。
  2. 对随机标识符做编码压缩。 UUID 有 128 位,用 16 字节二进制列存放比用 36 字节文本列存放节省大量空间;若必须使用文本形式的主键,其代价应在设计阶段显式确认。
  3. 代理键与业务键的取舍。 若业务键较长且长度不一,常用的做法是引入短的单调递增代理键作为聚簇索引,再对业务键建立唯一索引,把"长键"的代价限制在单个二级索引内。这属于数据建模层面的取舍,与索引列的覆盖范围、回表代价一并评估,见 mysql: 索引与执行计划 第 2.4 节。

2.6.3 填充因子与分裂策略

分裂点决定空间利用率与写放大。 假设节点满载时插入新键:

分裂策略 分裂后填充率 适用场景 代价
50/50 对半分裂 两节点各约 50% 随机插入 平均填充率长期停留在低位,空间占用约为数据量的两倍
偏向一侧分裂 一侧高、一侧低 单调递增或递减插入 需要判断插入位置,否则会在反方向插入时退化为低填充率
顺序插入优化:直接分配新页 原页保持高填充率 严格单调插入的最右页 仅对最右页有效,乱序插入仍触发分裂
迁移代替分裂(B* 树思路) 两节点各约 2/3 兄弟有空间时 需要额外锁定兄弟节点

填充因子的两个层面。

  • 页内填充率:一页中有效数据占已分配空间的比例。页内随机删除与更新会造成空洞,称为页内碎片。
  • 页间填充率:相邻页的实际使用程度。分裂产生的大量半满页称为页间碎片。

两者的共同外部表现是表空间与索引体积大于数据量,且顺序扫描需要读取更多的页。InnoDB 通过 DATA_FREE 与 information_schema.TABLES 中的长度字段可以观察碎片程度,判断口径与整理方式见 mysql: InnoDB 存储引擎 第 3.3 节。

预留空间的做法。 部分数据库提供"建索引时预留填充比例"的参数,使索引建立后每页保留一定空闲空间,用于吸收后续插入、减少分裂次数。代价是索引立即变大、顺序扫描需要读更多的页。它适合"建索引后马上会有大量插入"的场景,不适合静态或只读的表;MySQL 侧的对应参数与取值依据可在建表与索引变更流程中一并确认,参见 mysql: 表结构变更与运维治理。

写放大的量化。 一次插入的写入量由三部分组成:目标叶子页的改写、可能触发的分裂(两个叶子页加一个父节点页)、以及为保证持久性而产生的日志写入。分裂越频繁,写入放大越高;随机主键会使分裂持续发生,因为每次插入都命中不同页。以每页 16KB、页填充率 50% 计算,索引占用的磁盘空间约为数据量的两倍,缓冲池中能缓存的有效记录数也相应下降,这是随机主键除了 IO 模式之外的第二重代价。


三、实现

3.1 结构定义与基本操作要点

3.1.1 节点结构与键与子指针数组

一个节点需要保存三部分信息:

节点(页)结构
├── 元信息:页号、页类型(内部/叶子)、键数量、空闲空间位置、链表前后指针(叶子)
├── 键数组:keys[0 .. j-1],升序
├── 子指针数组(内部节点):children[0 .. j],长度比键数多 1
├── 值数组(叶子节点):values[0 .. j-1],与键一一对应
└── 空闲空间:页尾未使用的区域,新记录从空闲区分配并插入到有序位置

三处设计决定会渗透到所有操作的实现:

  1. 内部节点的子指针数恒为键数加一。 这个不变式是"键划分区间"的直接体现,也是下标偏移最容易出错的地方:插入键与插入子指针的位置不同,删除时两者要成对处理。
  2. 叶子与内部节点是否共用同一结构。 共用可以简化页管理与代码(InnoDB 用同一套页结构与记录格式,只按页类型区分解释方式),代价是节点内会有少量未使用字段;分开定义则类型清晰但两套代码路径需要各自维护。
  3. 记录在页内如何组织。 常见做法是页内维护一条按序的单向链表加一个稀疏目录(page directory),页内定位先用目录做粗二分、再沿链表细查,避免在页内搬移记录。这使页内插入与删除只需维护链表指针与目录槽,而不必整体搬移数组,代价是页内记录不再连续存放。InnoDB 的页结构即为此形式,见 mysql: InnoDB 存储引擎 第 2.3.3 节。

3.1.2 查找实现:节点内二分

内部节点内定位:
    lo = 0, hi = key_count - 1
    在 keys 中二分,返回第一个满足 key <= keys[i] 的位置 i
    若 i < key_count 且 keys[i] == key 且本节点为 B 树内部节点:
        命中,直接返回
    下降:node = children[i]        # i 可能等于 key_count,表示落在最后一个区间

叶子节点内定位:
    在 keys 中二分,命中则返回 values[i],否则返回不存在

要点:

  • 二分的边界语义要与子指针下标对齐。 内部节点用"第一个不小于目标的键的位置"作为子指针下标,可以直接得到正确分支;若改用"最后一个小于目标的键的位置",则需要加一,两处不一致就会导致下降到的子树区间错误。
  • 比较的是键的比较器,不是字节。 字符串键、复合键、非 ASCII 排序都需要一致的比较规则;比较器与索引的排序规则不一致时,二分得到的顺序与树中实际顺序不符,查找会漏掉命中项。数据库中的字符集与排序规则一致性问题即属此类。
  • 页内比较不必访问子节点。 键与子指针同在页内,比较过程不产生额外 IO,因此页内可以放心使用更复杂的索引(如页目录)加速定位。

3.1.3 插入的分裂与父节点更新

插入的关键是把自底向上的传播拆成两步:

插入:
    path = 沿查找路径记录所有访问过的节点与在其中选择的分支下标
    在目标叶子中插入键与值
    若未超限:结束
    否则向上传播:
        while 当前节点超限:
            分裂当前节点,得到右兄弟与上移/复制的分隔键
            若存在父节点(从 path 弹出):
                在父节点插入分隔键与指向右兄弟的子指针
                当前节点 = 父节点
            否则:
                新建根节点,把分隔键与两个子节点挂上,树高加一,结束

三种实现细节:

  1. B 树的分裂把中间键"上移"(从子节点移除),B+ 树的叶子分裂把右兄弟的最小键"复制"到父节点(子节点保留)。 混淆这两者会导致键丢失或重复。
  2. B+ 树的内部节点分裂时,中间键同样是上移(内部节点的键只是路标,上移后不再保留在两侧),只有叶子分裂采用复制。同一棵树中两种规则并存,是实现的常见出错点。
  3. path 数组是必需的。 分裂需要修改父节点,而树中不保存父指针;用显式栈记录路径可以避免"分裂后向上查找父节点"的额外遍历。若节点中保存父指针,则需要在分裂与合并时同步维护该指针,反而增加出错面。

3.1.4 删除的借位与合并

删除的下标处理比插入复杂,原因是一次删除可能同时改动父节点的键与子指针。

删除 leaf 中的键:
    若删除后键数 >= 下界:结束(B+ 树中父节点的分隔键可保持不变)
    否则若左或右兄弟的键数 > 下界:
        借位:把兄弟的一个键经父节点旋转到本节点,更新父节点的分隔键
    否则:
        合并:把本节点、父节点中的分隔键、兄弟节点并为一体
        在父节点中删除该分隔键与对应的子指针
        若父节点下溢,对父节点重复上述过程
    若根节点没有键且只有一个子指针:把子节点提升为根,树高减一

三处容易出错的地方:

  1. 键与子指针的下标错位。 父节点中,删除键键 kᵢ 时要删除子指针 children[i+1](右兄弟一侧),删除子指针 children[i] 时要删除键键 kᵢ₋₁(左侧一侧)。选择哪一侧取决于合并方向,写反会使树的结构与键的区间划分不一致,症状是某些键查找不到而非报错。
  2. 借位时父节点分隔键的更新方向。 从左兄弟借一个键时,父节点的分隔键下降为本节点的新最小键、兄弟的最大键上移为父节点的新分隔键;从右兄弟借时方向相反。B+ 树中叶子层借位后,父节点的分隔键通常应更新为右节点的当前最小键,若沿用旧值可能出现"分隔键小于右子树实际最小键"的不一致,虽不影响查找正确性(只是区间边界退化,可能出现键被分到左节点的情形),但会让范围查询的起点定位出现偏差。
  3. 过期分隔键与范围查询的交互。 B+ 树允许内部节点保留已从叶子删除的键。这在等值查找中无害(走到叶子后再判断是否存在),但若范围查询的实现依赖"分隔键等于某叶子首键"这一假设,就会定位到错误的起点。可靠的实现是:定位起点时不对分隔键的精确性做任何假设,落到叶子后取其第一个不小于下界的键,若该叶子中所有键都小于下界则继续沿链表右移(3.2 节的示例即采用这一写法,结果始终正确)。

3.1.5 指针与下标处理的通用难点

难点 说明 处置
键数上下界的判定 根节点不受下界约束,计算下界时需区分根与非根 把"最小键数"抽成一个按节点角色返回的函数,避免各处硬编码
子指针数组长度 内部节点删除键后子指针需同步删除,反之亦然 用"键数加一"的不变式断言校验,插入与删除后统一检查
分裂点的选择 分裂点影响填充率与后续分裂频率 分裂点抽成策略函数,按插入位置(是否最右)返回不同比例
树高变化 根分裂使树高加一,根合并使树高减一 树高不做为独立状态保存,由根节点是否叶子推导,避免状态不同步
空树与单节点 空树的根是叶子且没有键;只有一个根时根可以是叶子 所有操作都需要覆盖"根即叶子"的分支,删除后需检查是否退化为空树
复合键的比较 多列索引的比较需要逐列比较且注意各列的长度与类型 比较器由索引定义统一生成,键的编码与比较规则保持单一来源

3.2 简化实现示例

以下是一份教学用 B+ 树实现,覆盖查找、插入与范围查询,用 Python 列表表示页内的记录数组,用对象引用表示子指针。它省略了删除、并发控制、持久化与页管理,目的是把 3.1 节的分裂传播与下标规则以可运行的代码呈现出来。

import bisect


class Node:
    """一个节点对应树中的一个页。"""

    __slots__ = ("leaf", "keys", "children", "values", "next")

    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []          # 升序键数组
        self.children = []      # 内部节点:子指针数组,长度 = len(keys) + 1
        self.values = []        # 叶子节点:与 keys 一一对应的载荷
        self.next = None        # 叶子节点:指向右兄弟,用于范围扫描


class BPlusTree:
    def __init__(self, order=4):
        if order < 3:
            raise ValueError("阶至少为 3")
        self.order = order
        self.root = Node(leaf=True)

    @property
    def _max_keys(self):
        return self.order - 1

    # ---------- 查找 ----------

    def _find_leaf(self, key):
        """下降到可能包含 key 的叶子节点。"""
        node = self.root
        while not node.leaf:
            # children[i] 中所有键都小于 keys[i](首个不小于 key 的键)
            i = bisect.bisect_right(node.keys, key)
            node = node.children[i]
        return node

    def get(self, key):
        leaf = self._find_leaf(key)
        i = bisect.bisect_left(leaf.keys, key)
        if i < len(leaf.keys) and leaf.keys[i] == key:
            return leaf.values[i]
        return None

    # ---------- 插入 ----------

    def put(self, key, value):
        """插入或更新一个键,返回是否新增。"""
        path = []                       # 记录 (节点, 下降时选择的分支下标)
        node = self.root
        while not node.leaf:
            i = bisect.bisect_right(node.keys, key)
            path.append((node, i))
            node = node.children[i]
        i = bisect.bisect_left(node.keys, key)
        if i < len(node.keys) and node.keys[i] == key:
            node.values[i] = value
            return False
        node.keys.insert(i, key)
        node.values.insert(i, value)
        self._split_leaf(node, path)
        return True

    def _split_leaf(self, leaf, path):
        """叶子分裂:右兄弟的最小键复制到父节点,两侧都保留该键。"""
        if len(leaf.keys) <= self._max_keys:
            return
        mid = len(leaf.keys) // 2
        right = Node(leaf=True)
        right.keys = leaf.keys[mid:]
        right.values = leaf.values[mid:]
        leaf.keys = leaf.keys[:mid]
        leaf.values = leaf.values[:mid]
        right.next = leaf.next            # 维护叶子链表
        leaf.next = right
        self._insert_into_parent(leaf, right.keys[0], right, path)

    def _split_internal(self, node, path):
        """内部节点分裂:中间键上移到父节点,两侧都不保留。"""
        if len(node.keys) <= self._max_keys:
            return
        mid = len(node.keys) // 2
        sep = node.keys[mid]
        right = Node(leaf=False)
        right.keys = node.keys[mid + 1:]
        right.children = node.children[mid + 1:]
        node.keys = node.keys[:mid]
        node.children = node.children[:mid + 1]
        self._insert_into_parent(node, sep, right, path)

    def _insert_into_parent(self, left, sep, right, path):
        if not path:                      # 根已分裂:新建根,树高加一
            root = Node(leaf=False)
            root.keys = [sep]
            root.children = [left, right]
            self.root = root
            return
        parent, i = path.pop()
        parent.keys.insert(i, sep)
        parent.children.insert(i + 1, right)
        self._split_internal(parent, path)

    # ---------- 范围查询 ----------

    def range(self, lo, hi):
        """返回键落在 [lo, hi) 内的条目,按键升序。"""
        leaf = self._find_leaf(lo)
        i = bisect.bisect_left(leaf.keys, lo)
        out = []
        while leaf is not None:
            while i < len(leaf.keys):
                if leaf.keys[i] >= hi:
                    return out
                out.append((leaf.keys[i], leaf.values[i]))
                i += 1
            leaf = leaf.next              # 沿叶子链表推进
            i = 0
        return out

代码要点与 3.1 节的对应关系:

  1. _find_leaf 用 bisect_right,get 用 bisect_left。 前者求"第一个大于目标的分隔键位置"以选择子分支,后者求"第一个不小于目标的位置"以判断是否命中。两者混用会导致下降分支错误或漏判命中。
  2. 叶子分裂复制键、内部节点分裂上移键。 _split_leaf 把 right.keys[0] 复制到父节点(两侧保留),_split_internal 把中间键 sep 上移(两侧不保留),这与 3.1.3 节的规则一致。
  3. 分裂只触发一次,但可能递归上溯。 put 只调用一次 _split_leaf,若叶子分裂导致父节点超限,_insert_into_parent 会继续调用 _split_internal 并沿 path 上溯,直到某个祖先未超限或新建根。
  4. 范围查询沿 next 推进,不重新查找。 定位起点为 O(树高),之后每读取一个结果只做一次页内推进,总代价 O(树高 + M)。若在推进中重新调用 _find_leaf,代价会退化为 O(M × 树高)。

这份实现与工程实现的差距,按差距大小排列:

差距 教学实现 工程实现
并发控制 完全没有 页级闩锁、闩锁耦合(下降时先锁子再释放父)、或用 B-link 树加右指针向右分裂实现无锁读
持久化 数据只在内存,进程退出即丢失 修改前写预写日志(WAL),页带校验和,配合双写缓冲防止部分页写入
页管理 用 Python 列表,插入时整体搬移元素 页有固定大小与空闲空间管理,记录在页内以链表加目录组织,分裂时按页复制,页的分配与回收由表空间管理
删除 未实现 需要借位与合并,并处理根合并导致树高减一
键的存储 保存完整键对象 键按定义的类型编码,比较器与排序规则绑定到索引定义
统计信息 无 维护索引基数、页数与采样直方图,供优化器估算扫描量
缓存 无 页在缓冲池中被缓存,含 LRU 分代、邻页预读与脏页回刷
事务语义 无 页的修改参与 MVCC:保留旧版本、支持一致性读与回滚

其中并发控制与页管理两项是教学实现与工程实现之间最大的一段距离:前者决定了索引能否承受多线程写入,后者决定了索引的读写是否真的是"一次节点访问等于一次页访问"。B-link 树的思路值得一提:它在每个节点上增加一个指向右兄弟的指针,分裂时先在原节点写入新高键并向右分裂,查找遇到"目标键大于本节点高键"时改走右指针,从而使查找无需加读锁即可越过正在分裂的节点。这与 Bw-tree 用增量链避免原地改写是同一类思路——把"结构变更的可见性"问题转化为"读路径上的额外判断"。

3.3 与存储系统的衔接

3.3.1 数据页与索引页的读写流程

B+ 树在存储引擎中的一次读操作路径:

查询条件 → 优化器选择索引 → 从根页开始
    ↓ 缓冲池按 (表空间 ID, 页号) 查找
    ├─ 命中:直接返回内存页,页内二分,取子页号
    └─ 未命中:发起磁盘随机读装入缓冲池(可能触发淘汰与刷脏),再页内二分
    ↓ 重复上述过程直到叶页
    ↓ 聚簇索引:叶页即完整行;二级索引:叶页给出主键,需再走一次聚簇索引(回表)

一次写操作(插入)的路径:

定位目标叶页(同读路径,未命中则先读入)
    ↓ 在页内插入记录并更新页内链表与目录
    ↓ 页被标记为脏页;写 undo(用于回滚与 MVCC)与 redo(用于崩溃恢复)
    ↓ 事务提交时按刷盘策略把 redo 落盘(顺序写)
    ↓ 脏页由后台刷脏线程异步写回表空间(随机写)
    ↓ 若页已满:先分裂,可能需要读写新页并更新父页,父页同样可能分裂

读写路径的完整结构与参数含义见 mysql: InnoDB 存储引擎 第 2.2 与 2.3 节。对索引结构而言,需要从中提取三条结论:

  1. 写操作把随机写转成了顺序写。 页的修改不立即落盘,只追加一条顺序日志;真正的随机写被推迟并批量执行。因此索引插入的延迟主要由日志刷盘与页的闩锁竞争决定,而不是由页的物理写回决定。
  2. 读操作的成本由命中率决定。 树的上层页几乎总是命中的,叶页是否命中取决于工作集与缓冲池大小的关系。缓冲池无法容纳工作集时,每次查找都会产生随机读,这是索引性能出现台阶式下降的位置。
  3. 分裂是写路径上唯一会改变结构、并把随机性放大的动作。 分裂需要分配新页、搬移记录、更新父页,且新页在磁盘上未必与原页相邻,因此一次逻辑插入可能变成两到三次物理写。

3.3.2 缓冲池、脏页与预读

  • 缓冲池与页缓存的关系。 操作系统的页缓存与数据库的缓冲池都缓存磁盘数据。若数据库以缓冲方式打开文件,同一页会同时存在于两处,内存被双重占用;多数数据库在生产环境使用直接 IO 绕过页缓存,让刷盘时机完全由数据库控制。两种路径的机制与取舍见 linux: 页缓存与 IO 性能 中 Buffered IO 与 Direct IO 一节,与 mysql: InnoDB 存储引擎 第 2.6.3 节。
  • 缓存淘汰策略要考虑索引的访问模式。 树的根与上层页被高频访问、必须常驻;叶子页的复用率较低。若使用朴素 LRU,一次全表扫描或范围扫描会把大量一次性使用的叶子页放到链表头部,挤出上层页与热点页。分区 LRU 把新页先插入冷区、只有停留足够久后被再次访问才晋升,正是针对这一模式的防护。
  • 预读在范围扫描中有明显收益。 沿叶子链表推进时访问的页在逻辑上连续,若这些页在磁盘上也接近连续,预读可以把多次随机读合并为顺序读。若叶子页分散在多个区中,实际收益取决于局部性。预读的触发条件与自适应窗口见 linux: 页缓存与 IO 性能 中预读一节。

3.3.3 范围扫描与顺序读性能

范围扫描的性能由三部分构成:

  1. 定位起点的树高次页访问,通常只有最下一层可能未命中。
  2. 沿叶子链表读取 M 条记录,需要读取的叶子页数约为 M / 每页记录数。这一段的页访问模式在逻辑上连续,是顺序 IO。
  3. 回表带来的随机读(若查询列不被索引覆盖)。回表位置由主键决定,与叶子链表的顺序无关,因此表现为 M 次随机读,是范围扫描中最大的成本项。

第 3 项说明了为什么"覆盖索引"在范围查询中收益显著:它把 M 次随机读整体消除。索引覆盖的判定条件与 Using index 的读法见 mysql: 索引与执行计划 第 2.3 节。

反过来,若范围查询命中的行数占表比例很高,沿索引扫描加上回表的页访问数可能超过全表扫描的页数,此时优化器会选择全表扫描。索引并不总是更快,"减少页访问次数"才是判断依据。

3.3.4 随机写与页分裂的代价

一次插入在索引层引起的写入量取决于是否触发分裂:

情形 页写入量 说明
页有空闲空间 1 个页 仅目标叶页被修改(加日志写入)
页满但顺序插入到最右页 2 个页 原页与新分配的页,不搬移已有记录
页满且随机位置插入 2 个页加可能上溯的父页 原页与右兄弟各约半满,父页需更新,父页满则继续
大规模乱序写入 上述代价乘以分裂频率 页填充率长期偏低,索引体积与页数同步上升

分裂的代价不止于本次写入:分裂后两页的平均填充率下降,后续范围扫描需要读取更多页;页内的碎片使同样的记录数占用更多页;若父页也满,分裂向上传播,最坏情况到达根,树高加一。这一链条解释了批量导入、随机主键表与长期反复更新的表表空间持续膨胀的机理,观察与治理方式见 mysql: InnoDB 存储引擎 第 2.8.3 与 3.3 节。

3.4 应用实例

3.4.1 关系数据库的索引与主键

关系数据库是 B+ 树最主要的应用场景,其落地形态在 2.3.3 节已展开。核心结论是:聚簇索引决定数据的物理排列与主键的选择,二级索引决定回表代价与覆盖能力。主键的选择因此同时影响三件事——插入的 IO 模式、所有二级索引的体积、单页能容纳的记录数(进而影响树高)。这三者的取舍分析见 mysql: 索引与执行计划 第 2.2 与 3 节,写入放大对性能的影响与排查手段见 mysql: 性能诊断与调优。

3.4.2 文件系统与元数据索引

文件系统的元数据天然是"按键查找 + 范围扫描"的负载,因此大量文件系统用 B 树族结构组织元数据:

文件系统或子系统 结构 用途
XFS B+ 树 空闲空间索引、inode 索引、目录项索引
NTFS B+ 树 主文件表中的目录索引
btrfs 写时复制 B 树 数据与元数据的统一索引,支持快照
ext4 目录 htree(B 树的变体) 目录项较多时按文件名哈希组织,避免线性查找
ZFS 写时复制树 对象集与块指针的组织,配合快照与校验

这类索引的键通常是"inode 号"、"逻辑块号"或"文件名"。共同需求是:按键定位单个条目、按键范围枚举一段条目(如目录列表、连续块分配)、以及在大目录下保持对数级查找。三者正好是 B+ 树的强项,因此文件系统与数据库在同一类结构上收敛。

日志结构文件系统与写时复制的联系值得单独说明。 日志结构文件系统把所有写入组织为顺序追加的日志段,元数据索引的更新也随之写新位置而不原地改写;写时复制文件系统(btrfs、ZFS)把这一思路收缩到树结构内部:修改叶子节点时写一个新页,再自底向上写新的内部节点,最后原子切换根指针。收益是任何时刻都有一棵完整一致的树可用于快照与崩溃恢复,代价是写放大明显,尤其对随机主键。这一取舍与 LSM 树把随机写转换为顺序写的动机相同,但 B 树家族的实现方式是在树上原地或写时复制,而 LSM 是整体改为分层合并(见 3.4.3)。文件系统层次的通用概念见 linux: 文件系统基础。

3.4.3 键值存储的索引层

键值存储的索引层有两种主流选择,分工明确:

结构 写路径 读路径 适用负载
LSM 树(内存表 + 有序静态表 + 分层合并) 写内存表按有序结构组织,批量落盘为有序文件,后台合并冲突版本 从新到旧逐层查找,需要布隆过滤器减少无效查找 写多读少、追加型写入(日志、时序、计数器)
B+ 树 原地更新页,写日志保证持久性 沿树定位到页,页内二分 读多写少、需要范围查询与低延迟点查

两类结构中都可能出现 B 树族的组件:LSM 树的内存表通常用跳表或内存 B 树(写入局部化、便于并发);每个有序静态表(SSTable)内部按块组织,块索引用于在文件内定位目标块,块索引本身是按键组织的紧凑结构,部分实现用前缀压缩的有序数组甚至有限状态转换器来替代完整的 B 树索引,以压缩体积。选择依据可以概括为:需要在原位置更新单个键、且读多写少时用 B+ 树;写入以追加为主、允许读放大与后台合并时用 LSM。 两类结构在工程系统中的组织方式(缓冲池与页分裂、LSM 的分层合并与写放大、布隆过滤器在存储引擎中的位置)与观测指标见 工程中的数据结构。

3.4.4 搜索引擎的词典结构

全文检索的词典需要在前缀查询、通配查询与拼写纠错等场景下快速定位词项,并支持顺序枚举一段词项。它的键是字符串、数据量远大于内存、且以只读或批量重建为主,因此三种做法并存:

  1. 有序词典加二分。 把词项与其倒排表偏移量按序排列,用块索引加二分定位。结构简单、写入只发生在重建阶段,是批量索引的常见做法。
  2. 前缀树与其紧凑化表示。 共享词项公共前缀,天然支持前缀查询,节省空间;紧凑化后可用一次磁盘读定位一段前缀。跳表在索引层承担的作用与之类似:都是把顺序结构加上一层索引以缩小比较范围,跳表的实现与对照见 跳表 第 1.2 节;前缀树的节点语义、子节点表示方式与压缩变体见 字典树与字符串索引。
  3. 有限状态转换器(FST)。 把词项集合表示为一个有向无环图,共享前缀与后缀,体积通常远小于哈希表,且支持按键的有序遍历。代价是构建较慢、只适合批量写入,因此多用于索引的只读阶段。

搜索引擎往往同时对倒排表的文档号列表使用跳转结构(跳表式跳读)以加速多个词项列表的合并求交,其思路与 B 树内部节点的"跳过整段不可能命中的区间"一致。

3.5 常见问题与排查

现象 可能原因 验证与处置
点查延迟随数据量增长而上升 索引键过长导致扇出下降、树高加一层;或叶页未命中缓冲池 计算实际扇出与树高(页大小除以每项字节数);检查键长与主键类型;确认缓冲池命中率与工作集大小
范围查询未走索引而全表扫描 条件列缺少可用索引;条件列上使用了函数或隐式类型转换;前缀通配;范围条件之后的列无法参与定位 查看执行计划的访问类型与估算扫描行数;核对索引的最左前缀是否成立;失效情形的完整清单见 mysql: 索引与执行计划
写入吞吐低于预期,且与更新频率不成比例 页分裂导致的写放大:随机主键、乱序批量写入、页填充率长期偏低 观察表空间与索引体积相对数据量的膨胀程度、DATA_FREE 占比;检查主键是否单调;评估批量写入是否按主键排序
主键随机导致插入热点 随机主键使插入位置散布在整棵树中,每次插入命中不同页,触发分裂与随机写;同时页填充率下降、索引体积约为数据量两倍 改用单调递增的短主键(自增整数或有序编码的时间戳加序列);若业务必须使用 UUID,压缩为 16 字节二进制列并确认其有序性
唯一索引在高并发写入时出现等待 唯一性校验必须立即读取目标页以判断冲突,无法像非唯一索引那样延迟;并发插入同一唯一键区间时页闩锁争用 缩短唯一索引的键;评估是否可用业务侧的去重或幂等替代;写入冲突特别集中的唯一键考虑改为非唯一索引加应用层校验
重复键的处理导致索引膨胀 非唯一索引中重复键需要附加主键以保证条目唯一,重复度越高附加的主键越多、单条索引记录越大 重复度极高的列(如状态、布尔标志)不适合单独建索引,选择性不足时索引收益低于维护成本
删除大量数据后空间不释放、扫描变慢 删除只把记录标记为可复用,页内碎片与页间碎片保留,文件不缩小 观察碎片比例;在低峰期用重建表的方式整理;日常通过控制随机主键与批量删除粒度来抑制碎片产生,见 mysql: InnoDB 存储引擎 第 3.3.4 节
范围查询耗时与返回行数不成比例 回表造成的随机读;或每次取一条记录都重新查找一次起点 让索引覆盖查询涉及的列以消除回表;确认范围推进是沿叶子链表前进而不是逐次查找
索引维护使整体写入变慢 每个索引都要随写操作更新,索引数量与写入放大成正比;日志与刷盘压力同步上升 核对每个索引是否有明确的查询模式支撑;移除冗余索引(被联合索引最左前缀覆盖的索引);写入延迟的定位手段见 mysql: 性能诊断与调优
索引体积异常大于数据量 主键过长放大所有二级索引;页填充率低;索引列包含长字符串(如 URL、备注) 核对主键类型与长度、参与索引的列长度;对比索引长度与数据长度的比例

排查这类问题的通用手段有三项:计算扇出与树高(把页大小、键长、行宽代入 2.6.1 节的公式,得到理论页访问次数)、观察页数与填充率(索引长度与数据长度之比、空闲空间占比)、核对访问路径(执行计划给出的访问类型与估算扫描量是否与索引设计一致)。多数索引性能问题在这三项中都能定位到。

3.6 索引设计评审检查清单

3.6.1 键的选择与长度

  • 是否存在显式的、短且稳定的主键;主键是否单调递增;若使用随机标识符,是否压缩为二进制列并评估了其有序性。
  • 参与索引的列长度是否必要;长字符串列是否可以用前缀索引、哈希列或独立检索系统替代。
  • 索引列的类型是否与查询条件的类型一致(避免隐式转换导致索引失效)。
  • 键的排序规则与比较器是否与查询的排序需求一致(字符集、大小写敏感性、排序规则)。

3.6.2 列顺序与覆盖

  • 联合索引的列顺序是否满足最左前缀:等值条件列在前、范围条件列在后、排序列与等值列的组合是否被同一索引满足。
  • 高频查询是否被覆盖:查询涉及的过滤列、排序列、分组列与返回列是否都落在同一个索引内;覆盖带来的索引体积增长是否可接受。
  • 是否存在冗余索引:其列集合被其他索引的最左前缀完全包含的索引应删除。
  • 索引数量是否与写入量匹配:写入密集的表应控制索引数量,每个索引都贡献一份写入放大。

3.6.3 参数与维护

项目 判断依据
页大小 在建库或初始化阶段确定(多数引擎不支持在线修改),依据是平均行宽与访问模式;页越大树高越低而单次 IO 与分裂搬运量越大
索引的填充预留 仅在"建索引后立即有大量插入"的场景需要;静态表不预留
分裂策略 顺序插入场景应启用顺序插入优化;随机插入场景接受 50% 填充率或按业务接受度调整
批量写入方式 尽量按主键有序写入,使插入集中在最右页,减少分裂;分批次提交避免长事务
碎片治理 以碎片比例与空闲空间占比为触发条件,而不是定期无条件重建;重建需评估磁盘余量与流量影响,见 mysql: 表结构变更与运维治理
变更流程 索引的增删属于结构变更,需经过灰度与回滚流程;变更期间对写入与复制延迟的影响需要事先评估
验证方式 变更后用执行计划核对实际访问路径与估算扫描行数,确认收益来自页访问次数的下降,而不只是主观感受变快

清单中的每一项都落在同一个判断上:索引以空间与写入代价换取页访问次数的下降。 当某个索引无法证明它减少了页访问次数时,它的维护代价就没有对应的收益。


四、总结

问题与约束。 磁盘访问的代价比内存高四到五个数量级,且设备一次读写搬运一个不小于某个阈值的连续区间。这两个事实决定了磁盘索引的设计目标:让每个节点的大小与一次 IO 的搬运单位对齐,让一次查找经过的节点数尽量少。节点数与分支数的关系是对数关系,因此"降低树高"的唯一有效手段是"增加每个节点的分支数"。

从二叉树到多叉树。 二叉平衡树每层只有两个分支,树高为 log₂n 量级,在内存中可以接受,在磁盘上意味着二十次以上的页访问。把节点容量提升为一个页、分支数提升到上千之后,同样数据量的树高降到三到四层。B 树与 B+ 树都是在这一目标下的产物,区别在于节点里放什么。

B 树的定义与维护。 B 树的每个节点内键有序,键把取值区间划分给各个子指针指向的子树,所有叶子在同一层,节点键数有上下界(非根节点至少 ⌈m/2⌉ − 1 个)。插入只在叶子发生,超限时把中间键上移到父节点并分裂,可能自底向上传播到根;删除后若低于下界,先尝试向兄弟借位(经父节点旋转),兄弟也没有余量时与父节点中的分隔键一起合并,可能同样向上传播。高度上界由填充率下界与节点数共同决定,为 log_{⌈m/2⌉}((n+1)/2) + 1。

B+ 树的三点差异与结果。 B+ 树把行数据全部下沉到叶子,内部节点只保留分隔键与子指针,叶子之间用链表相连。由此得到三项优势:内部节点的扇出比 B 树高约两个数量级,树高更低;范围查询定位起点后沿叶子链表顺序推进,接近顺序 IO,而 B 树需要中序遍历回溯;删除时内部节点的分隔键可以保留,维护逻辑更简单。劣势是查找路径固定,无法在内部节点提前命中。数据库普遍选择 B+ 树,正是前两项在实际负载中的权重更大。

索引组织方式。 InnoDB 的表就是一棵按主键组织的 B+ 树,聚簇索引的叶子存放完整行,二级索引的叶子存放索引列与主键值。主键因此同时决定数据的物理排列顺序、所有二级索引的体积、以及单页能容纳的记录数。主键随机会持续触发页分裂与随机写,主键过长会使所有索引同步膨胀,这是"主键应短且单调"的结构性依据。

工程参数。 扇出由页大小除以每项字节数得到,树高由叶子页数与扇出的对数得到;以 16KB 页、8 字节主键、行宽约 1KB 估算,10⁶ 行的树高为 3 层,10¹² 行也只有 5 层。键长从 8 字节增加到 144 字节会使内部扇出下降约一个数量级。分裂点的选择决定页填充率,进而决定空间占用、范围扫描读取的页数与后续分裂频率;随机插入下的平均填充率约为 50%,对应索引体积约为数据量的两倍。

实现难度集中在三处。 一是下标账目:内部节点的子指针数恒为键数加一,键与子指针的插入删除位置错开,B 树的键上移与 B+ 树叶子分裂的键复制规则并存;二是自底向上的传播:分裂与合并都可能沿路径上溯到根并改变树高,需要显式记录路径;三是并发与持久化:工程实现需要页级闩锁或 B-link 树式的无锁读、预写日志、页校验与双写,这些是教学实现与生产实现之间最大的一段距离。

与内存结构的边界。 在内存中,"一次 IO 搬运一页"的约束不成立,把节点做成页大小只会浪费内存带宽与缓存行,因此内存中的有序结构选择红黑树或跳表——它们以简单的局部更新实现同一量级的时间复杂度;磁盘上的有序结构选择 B+ 树——它以页内扇出把页访问次数压到个位数。同一种抽象数据类型(有序映射)在不同介质上有不同实现,这一对应关系见 抽象数据类型(ADT)。

工程落点与排查。 B+ 树出现在关系数据库的聚簇与二级索引、文件系统的元数据索引、键值存储的索引层与搜索引擎的词典结构中;键值存储的另一条路线 LSM 树用"追加有序文件加后台合并"换取写入吞吐,与 B 树的原地更新形成不同取舍。日常问题的定位可以归到三个量上:扇出与树高是否因键过长而恶化,页访问次数是否因缺少覆盖而增加,页分裂与碎片是否导致写入放大与空间膨胀。理解了页与树高的关系,也就理解了索引设计中几乎所有取舍的来源。