《算法导论》-- B树

1 概述

B树是为磁盘或其它直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树，但它在降低磁盘I/O操作方面要更好一些。许多数据库系统使用B树或者B树的变种来存储信息（比如MYSQL的B+tree）。

如图，当B树的一个内部结点x包含x.n个关键字，那么结点x就有x.n+1个孩子。结点x中的关键字就是分隔点，它把节点x中所处理的关键字的属性分隔为x.n+1个子域。当一课B树中查找一个关键字时，基于对存储在x中的x.n个关键字的比较，做出一个(x.n+1)路的选择。叶结点的结构和内部结点的结构不同，后面讨论。

image.png

2 辅存上的数据结构

磁盘结构：

image.png

磁盘有两个机械运动的部分：盘片旋转和磁臂移动，这是一次I/O耗费时间的原因所在。磁盘每次存取多个数据项。由于大多数系统中，一个B树算法的运行时间主要由它所执行的DISK-READ和DISK-WRITE操作的次数决定，所以我们希望这些操作能够读或写尽可能的信息。因此，一个B树结点通常和一个完整磁盘叶一样大，并且一个磁盘页的大小限制了一个B树结点可以含有的孩子个数。

3 B树的定义

任何和关键字相关联的数据将于关键字一样存放在同一个结点，实际上可能只是存放一个指针，这个指针存放该关键字对应的数据的磁盘页。B+树把所有的数据存在叶子结点，内部结点只存放关键字和孩子指针，因此最大化了内部节点的分支因子。

一棵B树是具有以下性质的有跟树：

• 1.每个结点x有以下属性：a. 有x.n个关键字；b. 关键字以非降序顺序排列；c. x.leaf一个布尔值，true表示是叶结点；
• 2. 结点x包含x.n+1个孩子指针；
• 3. 关键字用于对子树关键字范围加以分割；
• 4. 每个叶结点具有相同的高度；
• 5. 每个结点所包含的关键字个数有上界和下界，用一个成为b树的最小度数的固定整数t>=2 来表示这些界，t越大树高度越小：
     a. 除根节点以外的每个结点x至少有t-1个关键字，至少t个孩子；
     b. 每个结点至多有2t-1个关键字，至多2t个孩子。

4 B树的高度

h <= log(t) (n+1)/2 (t为对数的底)

5 B树的基本操作

5.1 搜索

伪代码如下

B-TREE-SEARCH(x, k)  //x为节点，k为插入关键字
i = 1  //
while i <= x.n and k > x.key(i) //搜索k所在的节点位置
    i = i + 1
 if i <= x.n and k == x.key(i)
    return (x, i)
elseif x.leaf  //当前是子节点，返回NIL
    return NIL
else  DISK-READ(x, c(i)) //查找子节点
    return B-TREE-SEARCH(x.c(i), k) 

5.2 插入

创建一棵空的B树

为构造一棵B树T，先用B-TREE-CREATE来创建一个空的根结点，然后调用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

分裂

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

与一个二叉搜索树一样，可以在从树根到叶子这个单程向下过程中将一个新的关键字插入B树中，为了做到这一点，我们并不是等到找出插入过程中实际要分裂的满结点时才做分裂。相反，当沿着树往下查找新的关键字所属位置时，就分裂沿途遇到的每个满结点（包括叶结点本身）。因此，每当要分裂一个满结点y时，就能确保它的父结点不是满的。

分裂B树中的结点

image.png

B-TREE-SPLIT-CHILD(x, i) //x是结点，i为x的满子节点的下标
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 //上层增加一个子节点，关键字和孩子结点要向前推进1
    x.c(j + 1) = x.c(j)
x.c(i + 1) = z
for j = x.n downto i 
    x.key(j + 1) = x.key(j)
x.key(i) = y.key(i)
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(tlog(t)n)。过程B-TREE-INSERT利用B-TREE-SPLIT-CHILD来保证递归始终不会降至一个满结点上。

//把关键字k插入T树中
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.c1= r
    B-TREE-SPLIT-CHILD(s, 1) 
    B-TREE-INSERT-NONFULL(s, k)
else 
    B-TREE-INSERT-NONFULL(s, 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)

image.png

5.3 删除

必须防止删除操作而导致树的结构违反B树的性质。下面简要介绍删除操作如何工作：

• 1 如果关键字k在结点x中，并且x是叶结点，则从x中删除k；

• 2 如果关键字k在结点x中，并且x是内部结点，则有下面的情况：

  • a 如果结点x中前于k的子结点y至少包含t个关键字，则找出k在以y为根的子树中的前驱k'。递归地删除k'，并且在x中用k'代替k。（找到k'并删除它可在沿树下降的单过程中完成）。
  • b 对称地，如果y有少于t个关键字，则坚持结点x中后于k的子结点z。如果z至少有t个关键字，则找出k在以z为根的子树中的后继k'。递归地删除k'，并在x中用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的一个关键字移至新合并的结点，使之成为该结点的中间关键字。

    
    a.png