B-树

1 .B-树定义

B-树是一种平衡的多路查找树，它在文件系统中很有用。

定义：一棵m 阶的B-树，或者为空树，或为满足下列特性的m 叉树：
⑴树中每个结点至多有m 棵子树；
⑵若根结点不是叶子结点，则至少有两棵子树；

⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树；
⑷所有的非终端结点中包含以下信息数据：

????? （n，A0，K1，A1，K2，…，Kn，An）
其中：Ki（i=1,2,…,n）为关键码，且Ki<Ki+1，

? ? ? ? ? ?Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.

? ? ? ? ? ?n ? 为关键码的个数。
⑸所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

?? 即所有叶节点具有相同的深度，等于树高度。

?如一棵四阶B-树，其深度为4.

? ? ? ? ??

?

B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。

在上图的B-树上查找关键字47的过程如下：

1）首先从更开始，根据根节点指针找到 *节点，因为 *a 节点中只有一个关键字，且给定值47 > 关键字35，则若存在必在指针A1所指的子树内。

2）顺指针找到 *c节点，该节点有两个关键字（43和 78），而43 < 47 < 78,若存在比在指针A1所指的子树中。

3）同样，顺指针找到 *g节点，在该节点找到关键字47,查找成功。

2. 查找算法

1. typedef?int?KeyType?;??
2. #define?m?5?????????????????/*B?树的阶，暂设为5*/??
3. typedef?struct?Node{??
4. ????int?keynum;?????????????/*?结点中关键码的个数，即结点的大小*/??
5. ????struct?Node?*parent;????/*指向双亲结点*/???
6. ????KeyType?key[m+1];???????/*关键码向量，0?