数据库系统内幕

B

树的实现

｜

61

≤

≤ ≥

图

4-2

：最右指针

这个额外的指针可以存储在头部，例如，其在 SQLite 中的具体实现便是如此。

如果最右侧的子树被拆分，并且新的单元格被追加到其父节点上，则必须对最右侧的子

指针重新赋值。如图 4-3 所示，拆分后追加到父节点的单元格（灰色）包含被提升的键，

并指向拆分节点。此时分配了一个指向新节点的指针来替代原先的最右指针。SQLite 描

述并实现了类似的方法。

注 1

拆分前 拆分后

图

4-3

：节点拆分期间最右指针的更新（被提升的键用灰色表示）

4.1.4

节点的高键

我们可以采用一种稍微不同的方法，将单元格中的最右指针与节点的

高键

（high key）存

储在一起。节点的高键表示当前节点下的子树中可能存在的最高的键。PostgreSQL 使用

了这种方法，称为 Blink 树（有关此方法隐含的并发含义，请参见 5.3.8 节 ）。

B 树有 N 个 键 （用 K

i

表示）和 N+1 个指针（用 P

i

表示）。在每个子树中，键以 K

i-1

≤

K

s

<K

i

为

界。K

0

= - ∞是隐含的，并不在节点中表示。

Blink 树向每个节点添加一个 K

N+1

键。它指定了指针 P

N

指向的子树中所存储的键的上

注 1：你可以在项目仓库（

https://databass.dev/links/15

）中的 balance_deeper 函数中找到该算法。