第18章 B树

《算法导论》第3版

18.1 B树的定义

为简单起见，我们假定，就像二叉搜索树和红黑树中一样，任何和关键字相联系的“卫星数据”(satellite information)将与关键字一样存放在同一节点中。实际上，人们可能只是为每个关键字存放一个指针，这个指针指向存放该关键字的卫星数据的磁盘页。
一个常见的B树的变种，称为 B+树(B+ - Tree)，他把所有卫星数据都存储在叶节点中，内部节点只存放关键字和孩子指针，一次最大化了内部节点的分支因子。

一棵B树 T 是具有以下性质的有根树（根为 T.root）：

1. 每个节点 x 有下面的属性：
   　　a. x.n, 当前存储在节点 x 中的关键字个数。
   　　b. x.n 个关键字本身 x.key[1], x.key[2], ... , x.key[x.n] ，以非降序存放，使得 x.key[1] <= x.key[2] <= ... <= x.key[x.n] 。
   　　c. x.leaf，一个布尔值，如果 x 是叶节点，则为 TRUE；如果 x 为内部节点，则为 FALSE。
2. 每个内部节点 x 还包含 x.n + 1 个指向其孩子的指针 x.c[1], x.c[2], ... , x.c[x.n+1]。叶节点没有孩子，他们的 c[i] 属性没有定义。
3. 关键字 x.key[i] 对存储在各子树中的关键字范围加以分割：如果 k[i] 为任意一个存储在以 x.c[i] 为根的子树中的关键字，那么 ： k[1] <= x.key[1] <= k[2] <= x.key[2] <= ... <= x.key[x.n] <= k[x.n + 1] 。
4. 每个叶节点具有相同的深度，即树高 h 。(最底层的节点为叶子节点)
5. 每个节点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数（minimum degree）的固定整数 t >= 2 来表示这些界：
   　　a. 除了根节点以外的每个节点必须至少有 t - 1 个关键字。因此，除了根节点以外的每个内部节点至少有 t 个孩子。如果树非空，根节点至少一个关键字。
   　　b. 每个节点至多可包含 2t - 1 个关键字。因此，一个内部节点至多可以有 2t 个孩子。当一个节点恰好有 2t - 1 个关键字时，称该节点是满的(full)。(另一个常见的B树变种成为 B* 树，它要求每个内部节点至少是 2/3 满的，而不像B树要求的至少是半满的。)
   　　t = 2 时的树是最简单的。每个内部节点有2个、3个、或4个孩子，即一棵 2-3-4 树。然而在实际中，t的值越大，B树的高度就越小。

B树的高度

B树上大部分的操作所需的磁盘存取次数与B树的高度是成正比的。现在来分析B树最坏情况下的高度。

定理 18.1 如果 n >= 1，那么对任意一颗包含n个关键字、高度为和、最小度数t>=2的B树T，有： h <= logt (n+1/2) 。

18.2 B树上的基本操作

约定：B树的根节点始终在主存中；当根节点被改变后，需要对根节点做一次 DISK-WRITE 操作。任何被当作参数的节点在被传递之前，都要对他们先做一次 DISK-READ 操作。

搜索B树

B-TREE-SEARCH(x, k) :
    i = 1
    while i <= x.n and k > x.key[i] :
        i = i + 1
    if i <= x.n and k == x.key[i] : 
        return (x, i) // k 在 x 节点的 i 下标位置
    elif x.leaf : // x 是叶节点
        return NIL
    else :
        DISK-READ(x.c[i]) // 读取 x 节点 c[i] 孩子
        return B-TREE-SEARCH(x.c[i], k)

创建一棵空的B树

ALLOCATE-NODE 在 O(1) 时间内为一个新节点分配一个磁盘页。我们可以假定由 ALLOCATE-NODE 所创建的节点并不需要 DISK-READ ，因为磁盘上还没有关于该节点的有用信息。

B-TREE-CREATE(T) :
    x = ALLOCATE-NODE()  
    x.leaf = TRUE # 初始化的第一个节点是叶子节点
    x.n = 0
    DISK-WRITE(x)
    T.root = x

向 B树中插入一个关键字

　　由于不能将关键字插入一个满的叶节点，故引入一个操作，将一个满的节点 y (有2t-1个关键字）按其中间关键字(midian key) y.key[t] 分裂(split) 为两个各含 t-1 个关键字的节点。中间关键字被提升到 y 的父节点，以标识两棵新树的划分点。但是如果 y 的父节点也是满的，就必须在插入新的关键字之前将其分裂，最终满节点的分裂会沿着树向上传播。
　　我们不是等到找出插入过程中实际要分裂的满节点时才做分裂。相反，当沿着树往下查找新的关键字所属位置时，就分裂沿途遇到的每个满节点（包括叶节点本身）。因此，每当要分裂一个满节点 y 时，就能确保它的父节点不是满的。
　　

分裂B树中的节点

分裂是树长高的唯一途径。

B-TREE-SPLIT-CHILD(x, i) : // 分裂 x 节点的 i 孩子， x.c[i] 包含 2t-1 个关键字
    z = ALLOCATE-NODE() // 创建的新节点 z 存储 x.c[i] 右边的关键字，即 x.c[i].key[t+1..2t-1]
    y = x.c[i]
    z.leaf = y.leaf
    z.n = t - 1
    for j = 1 to t-1 :
        z.key[j] = y.key[j+t]
    if not y.leaf : // 分裂的 y 节点不是叶子
        for j = 1 to t :
            z.[j] = y.c[j+t]
    y.n = t - 1
    for j = x.n + 1 downto i + 1 : // 移动孩子节点 x.c[i+1 .. x.n+1]
        x.c[j+1] = x.c[j]
    x.c[i+1] = z
    for j = x.n downto i : // 移动关键字 x.key[i .. x.n]
        x.key[j+1] = x.key[j]
    x.key[i] = y.key[t]
    x.n = x.n + 1
    DISK-WRITE(y)
    DISK-WRITE(z)
    DISK-WRITE(x)

以沿着树单程下行的方式向B树插入关键字

在一棵高度为h的B树T中，以沿着树单程下行方式插入一个关键字k的操作需要O(h)次磁盘存取。所需要的CPU时间为O(th)=O(t logt n)。

B-TREE-INSERT(T, k) :
    r = T.root
    if r.n == 2t - 1 : // 如果根节点是满的
        s = ALLOCATE-NODE()
        T.root = s
        s.leaf = FALSE
        s.n = 0
        s.c[1] = r
        B-TREE-SPLIT-CHILD(s, 1)
        B-TREE-INSERT-NONFULL(s, k)
    else :
        B-TREE-INSERT-NONFULL(r, k)
    


B-TREE-INSERT-NONFULL(x, k) :
    i = x.n
    if x.leaf :
        while i >= 1 and k < x.key[i]
            x.key[i+1] = x.key[i]
            i = i - 1
        x.key[i+1] = k
        x.n = x.n + 1
        DISK-WRITE(x)
    else :
        while i >= 1 and k < x.key[i] :
            i = i - 1
        i = i + 1
        DISK-READ(x.c[i])
        if x.c[i].n == 2t - 1 : // x.c[i] 是满的，有 2t-1 个关键字，需要分裂
            B-TREE-SPLIT-CHILD(x, i)
            if k > x.key[i] :
                i = i + 1
        B-TREE-INSERT-NONFULL(x.c[i], k)

18.3 从B树中删除关键字

删除时要保证当前节点 x 至少包含 t 个关键字，这样从 x 中删除 k 时，剩余 t-1 个关键字还能保证B树的性质。为了保证 x 节点至少包含 t 个关键字，可能要从兄弟子树借来一个节点，或者合并两个相邻子树，来保证 x 节点有至少 t 个关键字。

删除时遇到的情况：

1. 如果关键字 k 在节点 x 中，并且 x 是叶节点，则从 x 中删除 k 。

2. 如果关键字 k 在节点 x 中，并且 x 是内部节点，(y中的关键字都小于 k ，或者是在k之前)，则做如下操作：
   　　a. 如果节点 x 中在 k 之前的孩子节点 y 有至少 t 个关键字，则在孩子节点 y 中找到 k 的前驱关键字 k' ，递归删除 k' ，然后在节点 x 中用 k' 替换 k 。（找到 k ' 并删除它可以在沿树下降的过程中完成）
   　　b. 如果 x 的孩子节点 y 拥有的关键字数量少于 t 个，即只有 t-1 个，那么，检查 x 节点中在关键字 k 之后的孩子节点 z ，如果 z 至少有 t 个关键字，则在 z 中找出 k 的后继 k' ，递归的删除 k' ，然后用 k' 替换掉 k 。（找到 k ' 并删除它可以在沿树下降的过程中完成）
   　　c. 如果孩子节点 y 和 z 都只有 t-1 个关键字，则将 k 和 z 的全部关键字和孩子节点连接合并进 y ，这样 x 就失去了 k 和 指向 z 的指针，此时的 y 包含 2t-1 个关键字。然后释放 z ，并递归地从 y 中删除 k 。

3. 如果关键字 k 不在节点 x 中，则要确定必包含 k 的子树的根 x.c[i] （如果k确实在树中）。如果 x.c[i] 只有 t-1 个关键字，必须执行步骤 3a 或 3b 来保证降至一个至少包含 t 个关键字的的节点。然后通过对 x 某个合适的子节点进行递归而结束。
   　　a. 如果 x.c[i] 只有 t-1 个关键字，但是它的一个相邻的兄弟至少包含 t 个关键字，则将 x 中的某个关键字降至 x.c[i] 中，将 x.c[i] 的相邻左兄弟或者右兄弟中的一个关键字升至 x ，将该兄弟中相应的孩子指针移动到 x.c[i] 中，这样就使得 x.c[i] 增加了一个额外的关键字。
   　　b. 如果 x.c[i] 和 x.c[i] 的所有相邻兄弟都只包含 t-1 个关键字，则将 x.c[i] 与一个兄弟合并，即将 x 的一个关键字移动到新合并的节点，使之成为该节点的中间关键字。

   B-TREE-DELETE(T, k) :
   r = T.root
   p = B-TREE-SEARCH(x, k)
   if p == NIL :
   return
   B-TREE-DELETE-NODE(r, k)

   B-TREE-GET-PREDECESSOR-KEY( y )
   while FALSE == y.leaf :
   y = y.c[y.n + 1]
   retrun y.key[y.n]

   B-TREE-GET-SUCCESSOR-KEY( y )
   while FALSE === y.leaf :
   y = y.c[1]
   return y.key[1]

   B-TREE-MERGE-CHILD(x, i) : # 将 x.key[i] 和 z 合并到 y 中，此时 y.n 和 z.n 应该都是 t-1，x.n至少是t
   y = x.c[i] # k 之前的 孩子节点
   z = x.c[i+1] # k 之后的孩子节点
   y.key[y.n+1] = x.key[i] #
   for j = 1 to z.n : # 复制 z 的数据到 y 中
   y.key[y.n+1+j] = z.key[j]
   y.c[y.n+1+j] = z.c[j]
   y.n = y.n + 1 + z.n
   y.c[y.n + 1] = z.c[z.n + 1]
   for j = i to x.n-1 :
   x.key[j] = x.key[j+1]
   x.c[j] = x.c[j+1]
   x.n = x.n - 1
   B-TREE-RELEASE(z) # 最后释放 z 节点

   B-TREE-DELETE-NODE(x, k) :
   i = 1
   while i <= x.n and x.key[i] < k :
   i = i + 1
   if i <= x.n and x.key[i] == k : # Case 1 & 2 : k 在节点 x 中
   if x.leaf : # Case 1: x 是叶子节点
   for j = i to (x.n - 1) :
   x.key[j] = x.key[j+1]
   x.n = x.n - 1
   return
   else : # Case 2 : x 是内节点
   y = x.c[i] # k 之前的孩子节点
   z = x.c[i+1] # k 之后的孩子节点
   if y.n >= t : # Case 2a : 节点 x 中在 k 之前的孩子节点 y 有至少 t 个关键字
   k2 = B-TREE-GET-PREDECESSOR-KEY( y )
   B-TREE-DELETE-NODE(y, k2)
   x.key[i] = k2
   return
   elif z.n >= t : # Case 2b : 节点 x 中在关键字 k 之后的孩子节点 z 至少有 t 个关键字
   k2 = B-TREE-GET-SUCCESSOR-KEY( z )
   B-TREE-DELETE-NODE(z, k2)
   x.key[i] = k2
   return
   else : # Case 2c :
   B-TREE-MERGE-CHILD(x, i)
   B-TREE-DELETE-NODE(y, k)
   return
   else : # Case 3 : k 不在 x 节点中
   c = x.c[i]
   if c.n < t : # Case 3 :
   left = i > 1 ? x.c[i-1] : NIL
   right = i <= x.n ? x.c[i+1] : NIL
   if left != NIL and left.n >= t : # Case 3a.1 x.c[i] 其中一个兄弟如果有
   for j = c.n downto 1 :
   c.key[j+1] = c.key[j]
   c.key[1] = x.key[i-1]
   # 如果 left 是叶子节点，可以不用复制孩子数组
   for j = c.n+1 downto 1 :
   c.c[j+1] = c.c[j]
   c.c[1] = left.c[left.n+1]
   c.n = c.n + 1
   x.key[i-1] = left.key[left.n]
   left.n = left.n - 1
   elif right != NIL and right.n >= t : # Case 3a.2 x.c[i] 其中一个兄弟如果有
   c.key[c.n+1] = x.key[i]
   c.n = c.n + 1
   x.key[i] = right.key[1]
   right.n = right.n - 1
   for j = 1 to right.n :
   right.key[j] = right.key[j+1]
   # 如果 right 是叶子节点，可以不用复制孩子数组
   c.c[c.n+1] = right.c[1]
   for j = 1 to right.n + 1 :
   right.c[j] = right.c[j+1]
   else : # Case 3b : 将 x.c[i] 与其中一个兄弟节点合并
   if left != NIL :
   B-TREE-MERGE-CHILD(x, i - 1)
   c = x.c[i-1]
   elif right != NIL :
   B-TREE-MERGE-CHILD(x, i)
   c = x.c[i]
   B-TREE-DELETE-NODE(c, k)

分析：尽管这个过程很复杂，但是一棵高度为 h 的B树，它只需要 O(h) 次磁盘操作，因为在递归调用该过程之间，仅需 O(1) 次对 DISK-READ 和 DISK-WRITE 的调用。所需的CPU时间为 O(t h) = O(t logt n)

.
.
.
.
End.