2024-06-26 (UPDATED 2024-06-29)

浅谈B+树

前言

B⁺树是B树的一个变种, 它把所有卫星数据存储在叶子结点中, 内部结点只存放关键字和孩子指针. 对于B树, 可以参考《算法导论》^[1], 这里不再介绍.

首先对B⁺树做一个定义. 我们这里采用的定义方法可能和网上常见的资料略有差异, 但也无伤大雅. B⁺树满足以下性质^[2]

每个结点 $x$ 有以下属性
1. $x.n$ : $x$ 的关键字个数.
2. $x.key_i$ : 关键字, 以非降序存放. ( $i = 0, \cdots, x.n-1$ )
3. $x.leaf$ : 如果 $x$ 是叶子结点, 则为TRUE.
4. $x.c_i$ : 如果 $x$ 是内部结点, 表示孩子指针. ( $i=0,\cdots,x.n$ )
5. $x.val_i$ : 如果 $x$ 是叶子结点, 表示卫星数据. ( $i=0,\cdots,x.n-1$ )
6. $x.p$ : $x$ 的父亲结点.
7. $x.next$ : 如果 $x$ 是叶子结点, 则 $x.next$ 指向下一个叶子结点.
令 $k_i$ 为以 $x.c_i$ 为根的子树中的任意关键字. 满足
$k_0 \leqslant x.key_0 \leqslant k_1 \leqslant x.key_1 \leqslant \cdots \leqslant x.key_{x.n-1} \leqslant k_{x.n}$

B⁺树的度数 $d>2$ . 这是由叶子结点分裂所要求的.

结点类型	最小关键字个数	最大关键字个数
内部结点	$\lfloor(d-1)/2\rfloor$	$d-1$
叶子结点	$\lceil(d-1)/2\rceil=\lfloor d/2\rfloor$	$d$

尽管根结点也是一种特殊类型的结点, 但是并没有专门区分的必要. 当树中仅有一个结点时, 它被看作叶子结点. 否则, 看作内部结点.

内部结点只存放关键字和孩子指针. 叶子结点只存放关键字和卫星数据.
所有叶子结点间用指针串联起来, 构成单向链表.

同时我们做一些约定.

对于叶子结点 $x$ , 我们将 $x.key_i$ 和 $x.val_i$ 合称为一个记录.
对于内部结点 $x$ , 我们将 $x.key_i$ 和 $x.c_i, x.c_{i+1}$ 合称为一个记录, 并将 $x.c_i$ 和 $x.c_{i+1}$ 分别称为此记录的左孩子和右孩子. 注意, 第 $i$ 个记录的右孩子事实上是第 $i+1$ 个记录的左孩子.
我们用希腊字母 $\alpha, \beta, \gamma, \cdots$ 来表示内部结点的关键字, 并用小写字母 $a, b, c, \cdots$ 来表示叶子结点的关键字. 其孩子结点或者卫星数据隐含地与关键字相关联.

简单起见, 我们首先规定关键字不可重复. 此时性质2化为性质2’

k_0 < x.key_0 \leqslant k_1 < x.key_1 \leqslant \cdots < x.key_{x.n-1} \leqslant k_{x.n+1}

如果关键字可以重复, 将会造成很大的麻烦. 首要的问题就是选取哪个记录会产生歧义. 文章的最后我们会讨论对于允许关键字重复的无卫星数据 (因此所有关键字相同的记录等价) 的B⁺树应当怎样修改以维持树的合法性.

以下是一棵度数为4的B⁺树

简单的例子

搜索

搜索较为简单. 假定我们要搜索的关键字为 $k$ . 我们从根结点开始, 比较结点的关键字, 并递归地搜索包含 $k$ 的子树. 由性质2’, 我们可以简单地写出以下伪代码

def BPT_SEARCH(x: node, k: key) -> val:
    leaf = BPT_SEARCH_LEAF(x, k)
    for i in range(x.n):
        if k == x.key[i]:
            return x.val[i]
    return NIL

def BPT_SEARCH_LEAF(x: node, k: key) -> node:
    if x.leaf:
        return x
    for i in range(x.n):
        if k < x.key[i]:
            break
    return BPT_SEARCH_LEAF(x.c[i], k)

首先调用辅助过程BPT_SEARCH_LEAF查找 $k$ 在哪个叶子结点里, 其中的小于号是由性质2’决定的. 然后比较叶子结点的关键字, 检查 $k$ 是否存在. 如果找到, 返回相应的卫星数据; 否则, 返回NIL (如果没有卫星数据, 也可以是TRUE和FALSE).

遍历则更为平庸. 由性质5可知, 如果要遍历所有记录, 只需获得首叶子结点, 然后遍历结点和链表即可.

插入

由性质3, 我们可以知道, 叶子结点和内部结点的插入和删除需要单独考虑. 方便起见, 我们分别记叶子结点和内部结点的最小关键字数量为 $T_l$ 和 $T_i$ . 假定我们要插入的记录为 $(k,v)$ .

首先讨论一种平庸的情况. 如果是空树, 那么直接创建一个叶子结点作为根结点, 将记录插在其中即可.

对于非空的树, 我们执行搜索, 检查 $k$ 应当被插在哪个叶子结点中, 并插入记录. 注意此时可能破坏性质3, 即超过了最大允许的关键字数. 这种情况下我们需要分裂叶子结点 $x$ . 不妨令分裂后的左结点包含 $\lfloor x.n/2\rfloor$ 个记录, 并将剩余的放在右结点中. 由于新增了一个结点, 我们也需要在其父亲结点插入一个新的记录.

考虑一棵如下所示的子树

叶子结点插入

我们将叶子结点 $\bf a$ 分裂成了两个. 很明显我们需要在其父亲结点的 $\alpha$ 和 $\beta$ 中间插入一个记录 $\gamma$ (注意 $\gamma$ 同时也表示记录的关键字) 来索引分裂出的叶子结点. 根据性质2’, $\gamma$ 应当满足 $a_k < \gamma \leqslant a_{k+1}$ . 显然我们可以把 $\gamma$ 设置为 $a_{k+1}$ .

同样的, 在父亲结点插入一个关键字也可能违反性质3, 考虑如下的子树

内部结点插入

其中 $\boldsymbol \alpha^{(1)}$ , $\boldsymbol \beta^{(1)}$ , $\boldsymbol \gamma^{(1)}$ 是叶子或者内部结点. 不同于我们对叶子结点的分裂, 这里我们直接提升内部结点的中间关键字 (这就是B树的分裂方式. 我们不能对叶子结点这样操作, 因为叶子结点不能被提升为内部结点).

内部结点插入后

容易看到, 这样分裂后, 并不会违反性质2’. 首先关注 $\alpha$ 和 $\gamma$ , 它们的左右孩子均没有发生任何变化. 对于 $\beta$ , 因为 $\alpha < \beta < \gamma$ , 因此也符合性质2’.

删除

删除是最为复杂的部分. 倘若叶子结点 $x.n>T_l$ , 那么我们直接删除记录即可. 否则, 删除后将会违反性质3. 此时, 我们分成两种情况:

如果其兄弟结点 $s$ 满足 $s.n>T_l$ , 那么我们借用其与 $x$ 相邻的记录 (对于左兄弟结点我们借用第 $s.n$ 个记录, 对于右兄弟结点我们借用第1个记录), 然后我们更新父亲结点来满足性质2’.
否则, 我们合并兄弟结点. 此时, 我们需要删除父亲结点中相应的记录.

首先讨论第1种情况. 我们以借用左兄弟结点为例. 借用右兄弟结点也是类似的, 这里不再讨论. 考虑如下子树

叶子结点借用

由于 $a_m<b_0$ , 因此借用后会违反性质2’. 因此, 我们需要更新 $\beta$ 使得 $a_{m-1}<\beta'\leqslant a_m$ . 显然我们可以将其取为 $a_m$ .

至于第2种情况, 我们合并 $\bf a$ 和 $\bf b$ . 根据性质2’, 合并后的结点显然可以作为 $\beta$ 左侧记录的右孩子和右侧记录的左孩子, 因此我们可以安全地删除 $\beta$ .

对于以上第2种情况, 在父亲结点删除一个关键字也可能违反性质3. 我们同样分成两种情况

如果其兄弟结点 $s$ 满足 $s.n>T_i$ , 那么我们做一次旋转.
否则, 我们合并兄弟结点. 此时, 我们需要将父亲结点中相应的记录插到两个结点中间.

另外, 我们需要注意, 在这两种情况下, 一个结点的孩子会移交到另一个结点, 因此我们需要更新孩子结点 $x$ 的 $x.p$ 属性.

首先讨论第1种情况. 同样的, 我们以借用左兄弟结点为例. 另一种情况是对称的, 这里不再赘述. 考虑如下子树

内部结点借用

如果我们只是简单地把 $\beta_m$ 交给右结点 (自然也包含它的右孩子 $\boldsymbol \beta^{(1)}_m$ ), 显然这会导致错误, 因为此时 $\boldsymbol \beta^{(1)}_m$ 变为了 $\beta_m$ 的左孩子.

为了解决这个问题, 我们将原先操作修正为旋转, 如下图所示

内部结点旋转

左侧结点的最右记录 $\beta_m$ 提升到父亲结点中, 并将原先父亲结点的记录 $\alpha$ 下降到右侧结点 (即做了一次右旋).

由性质2’, $\boldsymbol \beta^{(1)}_m$ 可以正确地作为 $\alpha$ 的左孩子. $\beta_m$ 提升为父亲结点也不会违反此性质, 因为 $\beta_{m-1} < \beta_m < \alpha$ . 因此, 旋转操作维持了性质2’.

第2种情况, 我们需要下移父亲记录是因为每个内部结点 $x$ 有着 $x.n+1$ 个孩子结点. 如果直接合并, 孩子结点个数变为 $x.n+y.n+2$ 个, 这将会违反性质3. 因此我们需要一个额外的关键字, 而两个兄弟结点的父亲记录显然是合适的. 考虑如下子树

内部结点合并

$\alpha$ 下降与左右孩子合并. 此时, $\alpha$ 的左孩子为 $\boldsymbol\beta^{(1)}_m$ , 右孩子为 $\boldsymbol \gamma^{(1)}_{-1}$ . 这显然维持了性质3和性质2’.

允许关键字重复的情况

我们可以看到, 如果关键字可以重复, 使用上文所述的方法将会出问题. 考虑结点 $x$ , 以及 $x$ 的前驱 $s$ . 有 $s.key_{s.n-1} \leqslant x.key_0$ . 接下来我们考虑 $s.key_{s.n-1} = x.key_0=k$ 的情况.

我们仍然借用上图进行说明. 将 $\boldsymbol \gamma^{(1)}_{-1}$ 看作 $x$ , 因此前驱 $s$ 就是 $\boldsymbol \beta^{(1)}_m$ . 此时 $x$ 和 $s$ 并非兄弟结点. 在内部结点分裂时显然我们有 $\alpha = x.key_0 = k = s.key_{s.n-1}$ , 因此在搜索 $k$ 时, 我们始终转向 $\alpha$ 的右子树, 从而无法访问前驱中关键字为 $k$ 的记录, 即便随后 $x$ 中的关键字为 $k$ 的记录全部被删除.

下面我们提出解决方案.

当 $x.key_0$ 改变时, 必须更新它与前驱的最低公共祖先 $\text {LCA}\{x,s\}$ (这是内部结点的一个记录), 使得在 $x.key_0>k$ 后, $k=s.key_{s.n-1}<\text{LCA}\{x,s\}\leqslant x.key_0$ , 从而能正确地转向左子树搜索. 很明显我们可以将 $\text{LCA}\{x,s\}$ 取为 $x.key_0$ .

而我们在上文所述的不允许关键字重复的B⁺树事实上始终严格满足 $s.key_{s.n-1}<\text{LCA}\{x,s\} \leqslant x.key_0$ , 因此无需更新 $\text{LCA}\{x,s\}$ .

参考文献

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. (2013, January). Introduction to Algorithms (3rd ed.). China Machine Press. ↩︎
Wikipedia contributors. (n.d.). B+ tree. Wikipedia. Retrieved June 26, 2024. B+ tree - Wikipedia ↩︎

前言
搜索
插入
删除
允许关键字重复的情况
参考文献