查找——B- 树

B-树

什么是 B-树？

B-树是一种平衡的多路排序查找树。

满足条件：

一棵 m 阶的非空 B-树，应当满足下面几个条件:

(1)树中每个结点最多有 m 棵子树。

(2)如果，根结点不是叶子，那么至少有两棵子树;

(3)除根以外的所有非终端结点至少有[m/2 棵子树；

(4)所有非终端结点中包含下列信息数据

(n，Ao，K1，A1，K2，A2，..，Kn，An)

其中:n([m/2]-1≤n≤m-1)为结点中关键字的个数;Ki(i=1，23，…，n)为关键字，且 Ki<Ki+1(i=1，2，3，...，n-1) ；A(i=0，1，2，…，n)为指向子树根结点的指针;且指针 Ai 所指子树中所有结点的关键字均小于 Ki(i=1，2，3，..，n)。 An 子树上所有结点的关键字均大于 Kn。

(5)所有的叶子结点都出现在同一层上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。

B-树的查找过程

(1)将给定值与根结点关键字相比较， 如果相等，那么查找成功。

(2)如果小于 Ki，那么下次从以 Ai-1 为根的子树中查找。否则下次从以 Ai+1 为根的子树中查找。

(3)如果查找到叶子结点，那么查找失败。

B-树的插入

(1)从根结点开始按照查找的过程确定给定值应插入的结点位置 P。

(2)如果该结点上的关键字个数少于 m-1 个，贝到将给定值直接插到该结点上。

(3)如果应插入的结点上，已有 m-1 个关键字， 那么，必须把该结点分裂成两

个结点;(P、P')。

例：在图中插入 65 后的 3 阶 B-树

B-树的删除

(1)被删除结点上关键字个数不少于 [m/2]，那么只需从该结点上删除该关键字 Ki 和相应的指针 Ai。

(2)如果被删除结点上关键字个数等于 m/2-1，而与其相邻的右兄弟结点(或左兄弟结点)中关键字的个数大于 m/2 -1,则需将其兄弟结点总数最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于),且紧靠该上移关键字的关键字移至被删关键字所在结点中。下图为删除 50 前、后的 3 阶 B-树。

(3)被删除关键字所在结点和其相邻的右兄弟结点(或左兄弟)结点中关键字的个数均等于[m/2]-1，假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针 Ai 所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字 Ki 一起，合并到 AI 所指兄弟结点中(若没有右兄弟，则合并到左兄弟结点中)。