首页 > 代码库 > [CLRS][CH 18]B树
[CLRS][CH 18]B树
B树的简介
B树的性质：
一棵B树T是具有一下性质的有根树：
1. 每个结点 x 具有如下属性：
a. x.n 存储当前节点 x 中关键字的个数；
b. x.n 个关键字本身 x.key1, x.key2, ..., x.keyx.n 以非降序存放，使得 x.key1 ≤ x.key2 ≤ ... ≤ x.keyx.n；
c. x.isLeaf 是一个bool值，表示 x 是否为叶节点，或者是内部结点。
2. 每个内结点 x 还包含 x.n+1 个指针，指向其孩子 x.c1, x.c2, ..., x.cx.n+1。叶节点没有孩子。
3. 关键字 x.keyi 对存储在各子树中的关键字范围加以分割。
4. 叶节点具有相同的深度，即树的高度 h。
5. 每个节点包含的关键字个数有上下界，用固定整数 t≥2，即B树的最小度数表示：
a. 除了根节点以外的每个结点必须至少有 t-1 个关键字，因此除了根节点每个节点至少有 t 个子节点。如果树非空，根节点至少有一个关键字；
b. 每个节点至多可包含 2t-1 个关键字，因此一个内部结点至多有 2t 个子节点。当一个节点恰好有 2t-1 个关键字时，称之为满结点。
当 t= 2 时，这就是一棵 2-3-4 树。因为每个结点有 t-1=1 ~ 2t-1=3 个关键字，有 t=2 ~ 2t=4 个子节点。
B树的高度：
定理：如果 n≥1，那么对于任意一棵包含了 n 个关键字，高度为h，最小度数 t≥2 的B树T，有h ≤ logt[(n+1)/2]。高度为 h = logtn。
跟普通BST一样，B树上大部分操作（所需的磁盘读写次数）过程跟高度成正比。B树的相对于红黑树的优势在于，深度非常浅，因为检查人一个节点都要访问一次磁盘，所以B树大大减少了磁盘访问的次数。如图，B树根至少包含一个关键字，其他内结点包含至少 t-1 个关键字。因此高度为 h 的B树在深度1至少包含2个结点，深度2至少包含2t个结点，深度h至少包含 2th-1个结点。
B树上的基本操作:
始终保持如下约定：
B树根节点始终保存在主存中，这样就无需读盘。修改根节点时需要写入磁盘；
任何被当做参数的节点在被传递之前，需要读盘。
所有操作都是单程算法，从树根向下，但不向上返回。
搜索B树
跟BST搜索过程很像，但是对于每一个内部结点x，做一个 (x.n + 1) 路的分支选择。
该过程访问磁盘页面数为 O(h) = O(logtn)。所用CPU时间为 O(th) = O(tlogtn)。
下面代码中，x为指向根节点的指针，key为要搜索的关键字，如果 key 在树中，则返回结点 y 和使得 y.keyi == key 的下标 i 组成的序对(y, i)，否则返回NULL。
B-Tree-Search(Node *x, int key) {i = 1;while (i <= x.n && k > x.key[i]) // 找出最小下标i，使得 key ≤ x.key[i]，若找不，则令 i = x.n + 1 i++;if (i <= x.n and k == x.key[i]) // 如果找到，就返回该关键字结点 return (x, i);else if (x.isLeaf == True) // 如果没找到，并且是叶节点，则返回失败结果NULL return NULL;else DISK-READ(x, c[i]) // 如果没找到，并且不是叶节点，就继续向下查找。这里需要读一次盘 return B-Tree-Search(x.c[i], k);}
创建一棵空的B树
为了构造一棵空的B树，先用B-Tree-Create创建一个空根节点，再调用B-Tree-Insert插入操作。这邪恶过程都需要调用辅助过程Allocate-Node，它在O(1)时间内为新节点分配磁盘页。
该过程需要O(1)次磁盘操作和O(1)的CPU时间。
B-Tree-Create(Node *newtree) {newtree = Allocate-Node();newtree.isLeaf = True;newtree.n = 0;Disk-Write(newtree);}
向B树中插入一个关键字
B树的插入过程跟 2-3-4 树插入过程一样（因为 2-3-4 树就是B树的一种）。当我们从树根向下插入过程中，分裂沿途遇到的所有满节点，因此每当分裂结点时，可确保其父节点不是满节点。另外，在B树中插入关键字，必须插入到已存在的叶节点上。
分裂B树中的结点
分裂过程 B-Tree-Split-Child 的参数为 x 和 i，其中 x 为被分裂结点的父节点，i 为被分裂结点在其父节点 x 中的下标，即被分裂的节点为x.ci。该过程把 x.ci 分裂成两个结点，并将 x.ci 的的中间关键字上浮之 x 中。如果被分裂的结点为根，树的高度增加1，分裂根是令B树高度增加的唯一操作。
B-Tree-Split-Child(Node *x, int i) { y = x.c[i] // 设置 y 为被分裂结点 x.c[i] z = Allocate-Node() // 新建结点 z 为分裂后多出来的新结点 z.isLeaf = y.isLeaf // 设置结点 z 的 isLeaf 属性 z.n = t-1 // 设置结点 z 的关键字数量 for j = (1 to t-1) // 设置结点 z 的关键字 z.key[j] = y.key[j+t] // 结点 z 的关键字为结点 y 的关键字的后半部分 if (y.isLeaf == False) // 如果被分裂结点不是叶节点的话，还要进一步设置结点 z 的子节点 for j = (1 to t) z.c[j] = y.c[j+t] y.n = t-1 // 重置结点 y 的关键字数量 for j = (x.n+1 downto i+1) // 将分裂结点 y 的父节点部分子节点后移一位，以便插入新结点 x.c[j+1] = x.c[j] x.c[i+1] = z // 将结点 z 插入父节点 for j = (x.n downto i) // 将分裂结点 y 的父节点部分关键字后移一位，以便插入新关键字 x.key[j+1] = x.key[j] x.key[i] = y.key[t] // 将分裂结点 y 的中间关键字上浮插入至父节点 x.n++ // 重置结点 x 的关键字数量 Disk-Write(y) // 将被调整关键字写入磁盘 Disk-Write(z) Disk-Write(x)}
如图是一个B树分裂示意图，分裂一个 t=4 的结点。结点 y=x.ci 分为两个节点 y 和 z，y的中间关键字 S 被升到其父节点 x 中。
以沿树单程下行的方式向B树插入关键字
过程 B-Tree-Insert 通过调用 B-Tree-Split-Child 来保证递归始终不会降到一个满节点上。
B-Tree-Insert(Node *root, int key) { r = root; if (r.n == 2t-1) // 如果根节点为满节点，则需要分裂根，通过设置空节点 s 作为根节点的父节点，进行分裂 s = Allocate-Node() root = s s.isLeaf = False s.n = 0 s.c[1] = r B-Tree-Split-Child(s, 1) B-Tree-Insert-NonFull(s, key) // 分裂完成后，调用 B-Tree-Insert-NonFull(s,k)进行插入 else B-Tree-Insert-NonFull(r, key) // 如果根节点不为满节点，则直接插入}
辅助过程 B-Tree-Insert-NonFull 将关键字 k 插入结点 x，调用该过程时应该保证结点 x 不是满节点，这一点可以通过 B-Tree-Insert 和 B-Tree-Insert-NonFull 递归调用得以保证。
B-Tree-Insert-NonFull(Node *x, int key) { i = x.n if (x.isLeaf == True) // 如果 x 是叶节点则直接进行插入 while (i >= 1 && key < x.key[i]) // 寻找合适的插入 key 的位置 x.key[i+1] = x.key[i] i-- x.key[i+1] = key // 插入key x.n++ // 重置结点 x 的节点数量 Disk-Write(x) // 写入磁盘 else // 如果结点 x 不是叶节点，则需要向下寻找适合插入 key 的一个子节点 while (i >= 1 && k < key[i]) // 寻找合适的 key 的位置 i-- i++ Disk-Read(x, c[i]) // 读取要进行写入的子节点 if (x.c[i] == 2t-1) // 如果被写入子节点为满节点，则需要分裂 B-Tree-Split-Child(x, i) if (key > x.key[i]) // 确定插入位置 i++ B-Tree-Insert-NonFull(x.c[i], key) // 插入 key 至新的结点 x.c[i] 中}
从B树中删除关键字
[CLRS][CH 18]B树