B树的原理

1，B树类似于红黑树，但它们在降低磁盘I/O操作数方面要更好一些，许多数据库系统使用B树或者B树的变种来存储信息。B树与红黑树的不同在于B树的节点可以有很多孩子，从数个到数千个。B树类似于红黑树，每个含有n个结点的B树的高度为O(lgn)。然而，一棵B树的严格高度可能比一棵红黑树的高度要小许多，这是因为它的分之因子，也就是说表示高度的对数的底数可以非常大。因此我们可以使用B树在时间O(lgn)内完成一些动态集合的操作。

2，B树的定义

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

1）每个结点x有下面属性：x.n当前存储在结点x中的关键字个数；x.n个关键字本身并以非降序存放；x.leaf，一个布尔值，如果x是叶节点，则为TRUE；如果x为内部结点，则为FALSE

2）每个内部结点x包含（x.n + 1）个指向其孩子的指针，叶节点没有孩子，所以它们没有这些指针。

3）如果k(i)为任意存储在以x.c(i)为根的子树中的关键字，那么有：k(1) <= x.key(1) <= k(2) <= x.key(2)…

4）每个叶结点具有相同的深度，即树的高度为h

5）每个节点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数的固定整数 t >= 2来表示这些界：

a：除了根节点以外每个结点必须至少有t - 1个关键字，如果树非空，根结点至少有一个关键字。

b：每个结点最多可包含2t-1个关键字，因此，一个内部结点至多有2t个孩子。当一个节点恰好只有2t-1个关键字时，该结点是满的(full)。

需要注意的是，t=2时的B树高度是最简单的，每个内部结点有2个、3个或4个孩子，即一棵2-3-4树。然而，在实际中，t的值越大，B树的高度就越小。

3，如果n >= 1，那么对任意一棵包含n个关键字、高度为h、最小度数t >= 2的B树T有，h <= log(t)((n + 1)/2)。相比红黑树来说，B树的底可以大很多倍，由于在一棵树中检查任意一个结点都需要一次磁盘访问，所以B树避免了大量的磁盘访问。

4，B树上的基本操作（增删查创）

1）搜索B树

搜索B树和搜索一棵二叉搜索树很相似，只是在每个结点所做的不是二叉或者“两路”分支选择，而是根据结点的孩子数做多路分支选择。访问磁盘的次数为O(h)，其中h为B树的高度。

2）创建B树

为构造一棵B树T，先用B-Tree-CREATE来创建一个空的根节点，然后调用B-Tree-Insert来添加新的关键字。这些过程都要用到一个辅助过程ALLOCATE-NODE，它在O(1)时间内为一个新结点分配一个磁盘页。

3）向B树中插入一个关键字

B树中插入关键字要比二叉搜索树中插入一个关键字复杂得多，想儿茶搜索树中一样，要查找插入关键字的叶节点的位置。我们是将新的关键字插入一个已存在的叶节点上，由于不能将关键字插入一个满的叶结点，故引入一个操作，将一个满的结点y按其中间关键字分裂为两个各含t-1个关键字的结点。中间关键字被提升到y的父结点，以标识两课新树的划分点。但是如果y的父结点也是满的，就必须在插入新的关键字之前将其分裂，最终满结点的分裂会沿着树向上传播。需要注意的是B树高的增长来自顶部，而搜索二叉树高度的增长来自底部。

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

4）从B树中删除关键字

B树可以从任意一个结点中删除一个关键字，而不仅仅是叶结点，而且当从一个内部结点删除一个关键字时，还要重新安排这个结点的孩子。必选保证一个结点不会因为在删除期间变得太小（根结点除外，因为允许它的关键字少于t - 1）。当要删除关键字的路径上结点有最少的关键字个数时，也可能需要向上回溯。删除的步骤如下：

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

2，如果关键字k在结点x中，并且x是内部结点，则做以下操作：

a，如果结点x中前于k的子节点y至少有t个关键字，则找出k在以y为根的子树中的前驱k0，递归删除k0，并在x中用k0代替k。

b，对称的，如果y有少于t个关键字，则检查结点x中后于k的子节点z。如果z至少有t个关键字，则找出k在以z为根的子树中的后继k1。递归删除k1，并在x中用k1代替k。

c，否则，如果y和z都只含有t - 1个关键字，则将k和z的全部合并进y，这样x就失去了k和指向z的指针，并且y现在包含2t - 1个关键字。然后释放z并递归地从y中删除k。

3，如果关键字k当前不在内部结点x中，则确定必包含k的子树的根x.ci(如果k确定在树中)。如果x.ci只有t - 1个关键字，必须执行步骤3a或3b来保证降至一个至少包含t个关键字的结点。然后，通过对x的某个合适的子结点进行递归而结束。

a，如果x.ci只含有t - 1个关键字，但是它的一个相邻的兄弟至少包含t个关键字，则将x中的某一个关键字降至x.ci中，将x.ci的相邻左兄弟或右兄弟的一个关键字升至x，将该兄弟中相应的孩子指针转移到x.ci中，这样就使得x.ci增加了一个额外的关键字

b，如果x.ci以及x.ci的所有相邻兄弟都只包含t - 1个关键字，则将x.ci与一个兄弟合并，即将x的一个关键字移至新合并的结点，使之成为该结点的中间关键字。