学步园

B树

B树是为硬盘等存储设备设计的一种平衡查找树，主要目的在于减少磁盘IO次数。

B树的结点可以有许多子女，每棵含n个结点的B 树的高度为O(logn)，但可能比一颗红黑树的高度小许多，因为他的分支多。

在一个典型的B树应用中，要处理的数据量很大，因此无法一次都装入主存。B树算法将所需的页选择出来复制到主存中去，而后将修改过的页再写回到磁盘上去。因为在任何时刻，B树算法在主存中都只需要一定量的页数，故主存的大小并不限制可被处理的B树的大小。

在大多数的系统中，B树算法的运行时间主要由它所执行的Disk-read 和 Disk-write操作的次数所决定，因而应该有效地使用这两种操作，由于这个原因，在B树中，一个结点的大小通常相当于一个完整的磁盘页。因此，一个B树结点可以拥有的子女数就由磁盘页的大小所决定。

完整定义如下：

注：此处使用“阶”定义B树，不同于算导上使用“度”定义。区别仅在于阶关注上界，而度关注下界。基本关系为：m = 2 * t  ， t = ceil(m / 2)

根结点一般常驻内存，然后根结点可以只有 2 个结点，即不需要去满足那个至少 ceil (m / 2)条件。

B树的高度

B树上大部分的操作所需的磁盘IO次数与B树的高度成正比。下边分析最坏情况高度。

若B树某一非叶子节点包含N个关键字，则此非叶子节点含有N+1个孩子结点（关键字数和孩子节点数强关联，+1关系），而所有的叶子结点都在第I层，我们可以得出：

当B树包含N个关键字时，B树的最大高度为l-1（因为计算B树高度时，叶结点所在层不计算在内），

即：l - 1 = log┌m/2┐((N+1)/2 )+1。

此处可以看出B树的威力，当阶数m较大时，log的底数很大，从而使得B树很矮。而矮即意味着硬盘IO次数的减少。

B树的基本操作

而对数据结构的操作，无非增、删、改查。

1）查 search

B-Tree-Search(root, val)
i = 1
while i <= root->n and val > root->key[i]   //在当前结点的关键字中找第一个大于等于插入值val的关键字 
	do i = i + 1
if i <= root->n and val = root->key[i]    //找到了要找的值，存在于B树中，返回位置信息（root， i）二元组
	then return (x, i)
if x->leaf == true
	then return NIL		//已经找至叶子结点，认为search失败
	else DISK-READ(root->child[i])
		return B-Tree-Search(root->child[i], val)    //递归去当前结点的儿子结点中去找 </span>

2）增 insert

插入操作一般是在search失败的基础上进行。
1.先不管不顾地将val值插入到它该在的位置，类似BST；
	if(插入的结点没有上溢出)            //上溢出即该结点的阶>m
		就这样
	else(插入的结点上溢出了)
		调整
2.如何调整
	把发生上溢出的结点中间的关键字提到上一层父节点处，然后以中间关键字“分裂”本结点。
	同时要看父结点是否因为这次调整导致上溢出，如果没有，就这样；上溢出了，继续调整父结点。最坏的情况显然是一路调整上去，直到根节点仍上溢出，那么整棵树长高一层（ps：insert 是唯一能导致B树长高的原因，同时说明B树长高发生在顶部、根部，不同于BST的长高发生在底部）</span>

对一棵高度为h的B树，B-Tree-Insert要做的磁盘存取次数为O（h）。

3）删 delete

首先，插入操作一般是在search成功的基础上进行。
其次，如果说insert主要关注的上溢出，那么delete主要关注的则是下溢出。即被删结点的阶< ceil (m / 2)
方法如下：
1.删除的关键码不在叶结点层，跟叶中前驱或者后继对换
2.删除的关键码在叶结点层
	1）删除后关键码个数不小于 ceil (m / 2) - 1，直接删除
	2）关键码个数小于 ceil (m / 2) - 1
		1>如果亲兄弟结点关键码个数不等于 ceil (m / 2) - 1，从兄弟结点移若干个关键码到该结点中来（父结点中的一个关键码要做相应变化）
		2>如果兄弟结点关键码个数等于 ceil (m / 2) - 1，合并</span>