B树、B+树

---

一、B树

B树类似于红黑树，但它在降低磁盘I/O操作数方面要更好一些。许多数据库操作系统使用B树或者B树的变种来存储信息。

B树与红黑树不同之处在于B树的结点可以有很多孩子。所以，可以使用B树在时间O(lgn)内完成一些动态集合的操作。

若B树的一个内部结点x包含x.n个关键字，那么结点x就有x.n+1个孩子。结点x中的关键字就是分隔点。

1. B树的定义

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

• 每个结点x有下面属性：
  
  • x.n，当前存储在结点x中的关键字个数；
  • x.n个关键字本身x.key1,x.key2,⋯,x.keyx.n，以非降序存放，使得x.key1⩽x.key2⩽⋯⩽x.keyx.n;
  • x.leaf，一个布尔值，如果x是叶结点，则为TRUE；如果x为内部结点，则为FALSE。
• 每个内部结点x还包括x.n+1个指向其孩子的指针x.c1，x.c2,⋯,x.cn+1，叶结点没有孩子，所以它们的ci属性没有定义；
• 关键字x.keyi对存储在各子树中的关键字范围加以分割：如果ki为任意一个存储在以x.ci为根的子树中的关键字，那么
  
  k1⩽x.key1⩽k2⩽x.key2⩽⋯⩽x.keyx.n⩽kx.n+1
• 每个叶结点具有相同的深度，即树的高度h；
• 每个结点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数 的固定整数t⩾2来表示这些界：
  
  • 除了根结点以外的每个结点必须至少有t−1个关键字。因此，除了根结点以外的每个内部结点至少有t个孩子。如果树非空，跟结点至少有一个关键字；
  • 每个结点至多可包含2t-1个关键字。因此一个内部结点至多可有2t个孩子。当一个结点恰好有2t-1个关键字时，称该结点是满的。

B树的高度

如果n⩾1，那么对于任意一棵包含n个关键字、高度为h、最小度数t⩾2的B树T，有：

h⩽logtn+12

与红黑树对比，尽管二者的高度都以O(lgn)的速度增长，但是对于B树来说，对数的底数可以大很多倍。因此，对大多数树的操作来说，要检查的结点数在B树中要比在红黑树中少大约lgt 的银子。

2. B树上的基本操作

搜索B树

输入为一个指向某子树根结点x的指针，以及要在该子树中搜索的一个关键字k。

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)
    elseif x.leaf
        return NIL
    else Disk_read(x, c_{i})
        return B_Tree_search(x.c_{i}, k)

搜索图例：

由B_tree_search过程访问的磁盘页面数为O(h)=O(logtn)，其中h为B树的高，n为B树中所含关键字个数。由于x.n<2t，所以程序中，while循环在每个结点中话费的时间为O(t)，总的CPU时间为O(th)=O(tlogtn)。

创建一颗空的B树

B_Tree_create(T)
    x = allocte_node()
    x.leaf = TRUE
    x.n = 0
    Disk_write(x)
    T.root = x

B_tree_create需要O(1)次的磁盘操作和O(1)的CPU时间。

向B树中插入一个关键字

将新的关键字插入一个已经存在的叶结点上，由于不能将关键字插入一个满的叶结点，故引入一个操作，将一个满的结点y (有2t-1个关键字)按其中间关键字y.keyt分裂为两个各含t−1个关键字的结点。中间关键字被提升到y的父节点，以标识两棵新树的划分点。但是如果y的父结点也是满的，就必须在插入新的关键字之前将其分裂，最终满结点的分裂会沿着树向上传播。

分裂B树中的结点

输入：非满的内部结点x，使x.ci为x的满子结点的下标i。

要分裂一个满的根，首先要让根成为一个新的空根结点的孩子，这样才能使用B_tree_split_child，树的高度因此增加1；分裂是树长高的唯一途径。

B_Tree_split_child(x, i)
    z = allocate_node()
    y = x.c_{i}
    z.leaf = y.leaf
    z.n = t - 1
    for j = 1 to t-1
        z.key_{j} = y.key_{j+1}
    if not y.leaf
        for j = 1 to t
            z.c_{j} = y.c_{j+t}
    y.n = t - 1
    for j = x.n+1 downto i+1
        x.c_{j+1} = x.c_{j}
    x.c_{i+1} = z
    for j = x.n downto i
        x.key_{i+1} = x.key_{i}
    x.key_{i} = y.key_{t}
    x.n = x.n + 1
    Disk_write(y)
    Disk_write(z)
    Disk_write(x)

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

需要O(h)次磁盘存取；
需要O(tlogtn)的CPU时间。

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，要求假定在调用该过程时x是非满的。

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
            B_Tree_split_child(x, i)
            if k > x.key_{i}
                i = i + 1
        B_Tree_insert_nonfull(x.c_{i}, k)

3. 从B删除关键字

删除关键字的各种情况：

尽管在B树中的删除操作看起来很复杂，但是对一棵高度为h的树，它只需要O(h)次磁盘造作，因为在递归调用该过程之间，仅需O(1)次对Disk_read和Disk_weite的调用，所需要的CPU时间为O(th)=O(tlogtn).