第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树

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

创建一棵空的B树

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

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

向 B树中插入一个关键字

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

分裂B树中的节点

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

  1. B-TREE-SPLIT-CHILD(x, i) : // 分裂 x 节点的 i 孩子， x.c[i] 包含 2t-1 个关键字
  2.     z = ALLOCATE-NODE() // 创建的新节点 z 存储 x.c[i] 右边的关键字，即 x.c[i].key[t+1..2t-1]
  3.     y = x.c[i]
  4.     z.leaf = y.leaf
  5.     z.n = t - 1
  6.     for j = 1 to t-1 :
  7.         z.key[j] = y.key[j+t]
  8.     if not y.leaf : // 分裂的 y 节点不是叶子
  9.         for j = 1 to t :
  10.             z.[j] = y.c[j+t]
  11.     y.n = t - 1
  12.     for j = x.n + 1 downto i + 1 : // 移动孩子节点 x.c[i+1 .. x.n+1]
  13.         x.c[j+1] = x.c[j]
  14.     x.c[i+1] = z
  15.     for j = x.n downto i : // 移动关键字 x.key[i .. x.n]
  16.         x.key[j+1] = x.key[j]
  17.     x.key[i] = y.key[t]
  18.     x.n = x.n + 1
  19.     DISK-WRITE(y)
  20.     DISK-WRITE(z)
  21.     DISK-WRITE(x)

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

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

  1. B-TREE-INSERT(T, k) :
  2.     r = T.root
  3.     if r.n == 2t - 1 : // 如果根节点是满的
  4.         s = ALLOCATE-NODE()
  5.         T.root = s
  6.         s.leaf = FALSE
  7.         s.n = 0
  8.         s.c[1] = r
  9.         B-TREE-SPLIT-CHILD(s, 1)
  10.         B-TREE-INSERT-NONFULL(s, k)
  11.     else :
  12.         B-TREE-INSERT-NONFULL(r, k)
  16. B-TREE-INSERT-NONFULL(x, k) :
  17.     i = x.n
  18.     if x.leaf :
  19.         while i >= 1 and k < x.key[i]
  20.             x.key[i+1] = x.key[i]
  21.             i = i - 1
  22.         x.key[i+1] = k
  23.         x.n = x.n + 1
  24.         DISK-WRITE(x)
  25.     else :
  26.         while i >= 1 and k < x.key[i] :
  27.             i = i - 1
  28.         i = i + 1
  29.         DISK-READ(x.c[i])
  30.         if x.c[i].n == 2t - 1 : // x.c[i] 是满的，有 2t-1 个关键字，需要分裂
  31.             B-TREE-SPLIT-CHILD(x, i)
  32.             if k > x.key[i] :
  33.                 i = i + 1
  34.         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 的一个关键字移动到新合并的节点，使之成为该节点的中间关键字。

代码如下：

  1. B-TREE-DELETE(T, k) :
  2.     r = T.root
  3.     p = B-TREE-SEARCH(x, k)
  4.     if p == NIL :
  5.         return
  6.     B-TREE-DELETE-NODE(r, k)
  8. B-TREE-GET-PREDECESSOR-KEY( y )
  9.     while FALSE == y.leaf :
  10.         y = y.c[y.n + 1]
  11.     retrun y.key[y.n]
  13. B-TREE-GET-SUCCESSOR-KEY( y )
  14.     while FALSE === y.leaf :
  15.         y = y.c[1]
  16.     return y.key[1]
  18. B-TREE-MERGE-CHILD(x, i) : # 将 x.key[i] 和 z 合并到 y 中，此时 y.n 和 z.n 应该都是 t-1，x.n至少是t
  19.     y = x.c[i] # k 之前的 孩子节点
  20.     z = x.c[i+1] # k 之后的孩子节点
  21.     y.key[y.n+1] = x.key[i] #
  22.     for j = 1 to z.n : # 复制 z 的数据到 y 中
  23.         y.key[y.n+1+j] = z.key[j]
  24.         y.c[y.n+1+j] = z.c[j]
  25.     y.n = y.n + 1 + z.n
  26.     y.c[y.n + 1] = z.c[z.n + 1]
  27.     for j = i to x.n-1 :
  28.         x.key[j] = x.key[j+1]
  29.         x.c[j] = x.c[j+1]
  30.     x.n = x.n - 1
  31.     B-TREE-RELEASE(z) # 最后释放 z 节点
  33. B-TREE-DELETE-NODE(x, k) :
  34.     i = 1
  35.     while i <= x.n and x.key[i] < k :
  36.         i = i + 1
  37.     if i <= x.n and x.key[i] == k : # Case 1 & 2 : k 在节点 x 中
  38.         if x.leaf :                 # Case 1: x 是叶子节点
  39.             for j = i to (x.n - 1) :
  40.                 x.key[j] = x.key[j+1]
  41.             x.n = x.n - 1
  42.             return
  43.         else :                      # Case 2 : x 是内节点
  44.             y = x.c[i] # k 之前的孩子节点
  45.             z = x.c[i+1] # k 之后的孩子节点
  46.             if y.n >= t :           # Case 2a : 节点 x 中在 k 之前的孩子节点 y 有至少 t 个关键字
  47.                 k2 = B-TREE-GET-PREDECESSOR-KEY( y )
  48.                 B-TREE-DELETE-NODE(y, k2)
  49.                 x.key[i] = k2
  50.                 return
  51.             elif z.n >= t :         # Case 2b : 节点 x 中在关键字 k 之后的孩子节点 z 至少有 t 个关键字
  52.                 k2 = B-TREE-GET-SUCCESSOR-KEY( z )
  53.                 B-TREE-DELETE-NODE(z, k2)
  54.                 x.key[i] = k2
  55.                 return
  56.             else :                  # Case 2c : 
  57.                 B-TREE-MERGE-CHILD(x, i)
  58.                 B-TREE-DELETE-NODE(y, k)
  59.                 return
  60.     else :                          # Case 3 : k 不在 x 节点中
  61.         c = x.c[i]
  62.         if c.n < t :                # Case 3 : 
  63.             left = i > 1 ? x.c[i-1] : NIL
  64.             right = i <= x.n ? x.c[i+1] : NIL
  65.             if left != NIL and left.n >= t :      # Case 3a.1 x.c[i] 其中一个兄弟如果有
  66.                 for j = c.n downto 1 :
  67.                     c.key[j+1] = c.key[j]
  68.                 c.key[1] = x.key[i-1]
  69.                 # 如果 left 是叶子节点，可以不用复制孩子数组
  70.                 for j = c.n+1 downto 1 : 
  71.                     c.c[j+1] = c.c[j]
  72.                 c.c[1] = left.c[left.n+1]
  73.                 c.n = c.n + 1
  74.                 x.key[i-1] = left.key[left.n]
  75.                 left.n = left.n - 1
  76.             elif right != NIL and right.n >= t :  # Case 3a.2 x.c[i] 其中一个兄弟如果有
  77.                 c.key[c.n+1] = x.key[i]
  78.                 c.n = c.n + 1
  79.                 x.key[i] = right.key[1]
  80.                 right.n = right.n - 1
  81.                 for j = 1 to right.n :
  82.                     right.key[j] = right.key[j+1]
  83.                 # 如果 right 是叶子节点，可以不用复制孩子数组
  84.                 c.c[c.n+1] = right.c[1]
  85.                 for j = 1 to right.n + 1 :  
  86.                     right.c[j] = right.c[j+1]
  87.             else :                  # Case 3b : 将 x.c[i] 与其中一个兄弟节点合并
  88.                 if left != NIL :
  89.                     B-TREE-MERGE-CHILD(x, i - 1)
  90.                     c = x.c[i-1]
  91.                 elif right != NIL :
  92.                     B-TREE-MERGE-CHILD(x, i)
  93.                     c = x.c[i]
  94.         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.