第18章 B 树

B树
一种平衡搜索树，
是为磁盘或其他直接存取的辅助存储设备而设计的。

许多数据库系统使用B树或者B树的衍生数据结构来存储信息。

B树和红黑树的比较

类似红黑树。
相似之处：

• 类似红黑树，每颗含有n个结点的B树的高度为O(lg n)；
• 但是因为B树的分支因子可能很大啊，B树的严格高度可能比红黑树的高度要小许多，也就是说O(lg n)的底数特别大。

B树和红黑树的不同之处：

• B树的结点可以有很多孩子；
• B树比红黑树在降低磁盘I/O操作数方面要更好一些

本章的目录安排

18.1节，介绍B树的精确定义
18.2节，介绍如何在B树中查找和插入一个关键字
18.3节，讨论删除操作

为什么对磁盘设计的数据结构和对随机访问的主存设计的数据结构不同？

理想的存储器，需要满足下面三个条件：

• 处理速度快；
• 容量大；
• 价格便宜；

但是，目前同时满足以上三个条件很难。
因此，计算机存储器部件，采用了不同层次结构来组织设计。

按功能分为：

1. 寄存器
2. 高速缓存
3. 主存
4. 磁盘缓存
5. 磁盘
6. 可移动存储介质

从下往上，存储介质的访问速度越来越快，价格越来越贵，相对存储容量也越来越小。
1，2，3，4，都属于操作系统管理范畴（也就是断电后存储信息不存在）
5，6，属于设备管理范畴（信息长期保存）

寄存器和主存，又称为可执行存储器。
对于可执行存储器，进程采用一条load或store指令进行访问，可以在很少的时钟周期中完成。
对于辅存的访问，进程需要通过I/O设备来实现。所耗费的时间也远高于对可执行存储器的访问。

考量的两个方面：

• 磁盘存取次数：使用需要读或写入磁盘的信息的页数来作为磁盘存取次数的近似值。
• CPU（计算）时间：B树算法的运行时间，主要由它所执行的DISK-READ和DISK-WRITE操作的次数决定。

18.1、B树的定义

B树的结点通常和一个完整磁盘页一样大，因此，磁盘页的大小，限制了B树结点的孩子个数，也就是分支因子。
存储在磁盘上的B树，通常其分支因子在50~2000之间，具体取决于关键字相对于一页的大小。

为简单起见，假定任何与关键字相关的“卫星数据”与关键字一样存放在同一节点中。当关键字从一个节点移到另一节点时，与其相关的“卫星数据”及其指针一起移动。
B+树，是B树的变种，它把所有的卫星数据都存储在叶节点中，内部节点只存放关键字和孩子指针，因此最大化了内部节点的分支因子。

B树T的性质：

1. 每个结点有以下属性：
   a. x.n，表示当前存储在节点x中的关键字个数为n个。
   b. x.n个关键字x.key1, x.key2, x.key3, ....，x.keyn,以非降序排列。满足x.key1 <= x.key2 <= x.key3 <= ... <= x.keyn。
   c. x.leaf ，一个布尔值，x是叶节点则为TRUE，为内部节点时，为FALSE。
2. 每个内部节点x包含x.n+1个指向其孩子的指针x.c1，x.c2，...，x.cn。叶节点没有孩子，所以它们的ci属性没有定义。
3. 关键字x.keyi，与存储在其子树中的关键字ki，的关系为：
   k1 <= x.key1 <= k2 <= x.key2<= .... <= x.keyn <= k()n+1)
4. 每个叶节点具有相同的深度，即树的高度h；
5. 每个结点包含的关键字个数有上界和下界，使用B树的最小度数t>=2来表示。
   a. 除根节点外，其余每个结点，必须至少包含t-1个关键字。因此，除了根节点以外的每个内部节点至少有t个孩子。如果树非空，根节点至少有一个关键字。（因为t-1个关键字可以划分为t个域，每个域代表一个子节点，因此说，每个除根节点以外的结点至少有1个关键字，而内部节点，至少有两个孩子。）
   b. 每个结点最多可包含2t-1个关键字，因此，一个内部节点至多可有2t个孩子，当一个节点恰好有2t-1个关键字时，该节点是满的。

B树的高度

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

18.2、B树上的基本操作

这里讨论B树的搜索、创建、插入操作的细节，我们采用两个约定：

• B树的根节点始终在主存中，因此无须对根节点做DISK-READ操作。但是，当根节点被改变后，需要对根节点做一次DISK-WRITE操作。
• 任何被当做参数的结点在被传递之前，都要对它们先做一次DISK-READ操作。

搜索B树

搜索B树，就是对每个内部节点x，做一个（x.n+1）路的分支选择。
输入的是一个指向某子树根节点x的指针，以及要在该子树中搜索的关键字k。
如果k在B树中，那么返回由该节点y和使得y.keyi= k的下标i组成的有序对（y，i）。否则返回nil。

B-TREE-SEARCH(x,k)
i =1;
while(i <= x.n and k > x.keyi)
    i = i+1;
if i <= x.n and k == x.keyi
    return(x,i);
elseif x.leaf
    return nil;
else
    DISK-READ(x,ci);
    return B-TREE-SEARCH(x.ci,k);      //继续在其孩子中递归搜索

B-TREE-SEARCH 过程访问的磁盘页面数为O(h) = O(log n)，h为B树的高，n为B树中关键字的个数。
由于x.n < 2t，所以总的CPU运行时间为O(th) = O( t log n)

创建一棵空的B树

1. 先用B-TREE-CREATE来创建一个空的根节点；

2. 再调用B-TREE-INSERT来添加新的关键字。
   说明：该过程会用到一个辅助过程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;

说明：

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

向B树中插入一个关键字

1. 将新的关键字插入已存在的叶节点上（每个叶节点还有多个关键字）。
2. 但是不能将关键字插入一个满的叶节点上，因此，需要将满的（已有2t-1个关键字的）结点y，按照其中间关键字y.keyi分裂为两个各含有t-1个关键字的结点。而中间关键字被提升到y的父节点。而y的父节点也可能是满的，就必须在插入y之前将其分裂。依次向上传播。
3. 为了方便起见，当沿着树往下查找新的关键字所属位置时，就分裂沿途遇到的每个满结点，因此，每当要分裂一个满结点时，就能确保其父节点不是满的。

分裂B树中的结点

B-TREE-SPLIT-CHILD的输入为（x，i）。x为一个非满的内部节点；i为x的满子节点x.ci的下标i。
这个过程把这个满子节点分裂成两个，并调整x，使其包含满节点中多出来的孩子。
分裂是树长高的唯一途径。
对根分裂是增加B树高度的唯一途径。

B-TREE-SPLIT-CHILD（x,i）
z = AALLOCATEE-NODE()
y = x.c(i)
z.leaf = y.leaf
z.n = t-1
//for循环是将y的最大的t-1个关键字赋值给z
for j = 1 to t-1
    z.key(j) = y.key(j+t)
if not y.leaf
    //for循环是将y的最大的t个孩子赋值给z
    for j = 1 to t
        z.c(j) = y.c(j+t)
//调整y的关键字个数，由原来的2t-1调整为t-1，因为移出去了最大的t-1个，并且还要把中间的关键字移到父节点中去
y.n = t-1   
//for循环是调整x的孩子节点依次向后移一位，并在第i+1个孩子节点的位置插入z这个新孩子节点   
for j = x.n + 1 downto i + 1
    x.c(j+1) = x.c(j)
x.c(i+1) = z;
//调整x中的关键字，并将最大的n-i个关键字后移，并在i个关键字的位置插入新增的关键字（来自其孩子节点的中间关键字）
for j = x.n downto i
    x.key(j+1) = x.key(j)
x.key(i) = y.key(t)
x.n = x.n + 1     //对x的关键字个数加1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)

说明;

• B-TREE-SPLIT-CHILD 占用CPU时间为O(t)，t为常量，执行磁盘操作O(1)次。

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

下面来看一下以沿树单程下行方式向B树插入关键字：
向一棵树高为h的B树T中，以沿树单程下行方式插入一个关键字k的操作需要O(h)次磁盘操作。
所需的CPU时间为O(th) = O(t log n)
过程中用到了B-TREE-SPLIT-CHILD来保证递归不会降至一个满节点上。

B-TREE-INSERT(T,k)
    r = T.root
    if r.n == 2t - 1
        //这种情况是在处理根节点为满的情况，原根节点被分裂，新节点s成为根
        s = ALLOCATE-NONE()
        T.root = s;
        s.leaf = false;
        s.n = 0;
        s.c1 = r
        B-TREE-SPLIT-CHILD(s,1)
        B-TREE-INSERT-NONFULL(s,k)
    else
        B-TREE-INSERT-NONFULL(r,k)

给非满的节点x中插入关键字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
            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中删除关键字k的过程中，保证无论何时，节点x递归调用自身时，其关键字个数至少为最小度数t（关键字个数的下界是t-1，上界是2t-1）。这个加强的条件允许在一趟下降过程中，可以将一个关键字从树中删除。而无需向上回溯。
从B树中删除关键字的各种情况：

1. 如果关键字k在节点x中，且x是叶节点，则从x中删除k；
2. 如果关键字k在节点x中，且x是内部节点，则做以下操作；
   a. 如果节点x中k前面的子节点y至少包含t个关键字，那么就在y中找到k的前驱k'，删除k'，并用k‘代替k。
   b. 而如果y中少于t个关键字，则检查k的后面的子节点z。如果z的关键字个数至少为t个，那么就在z中找到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确实在树中，那么就确定包含k的子树的根x.c(i)。如果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中的兄弟指向x.c(i)，这样x.c(i)中就增加了一个关键字，变成t个关键字了。
   b. 如果x.c(i)以及x.c(i)的所有相邻兄弟都只包含t-1个关键字，那么久将x.c(i)与其一个兄弟合并，并使x的这两兄弟间的关键字成为其中间关键字，一起合并。

所需的CPU时间为O(th) = O(t log n)。