二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(14)

由于高度为h的m路查找树中关键字的个数在h +1到mh+1 -1之间，所以一棵n个关键字的m路查找树的高度应在logm n+1 -1和n-1之间。例如，一棵高度为4的200路查找树，关键字个数最多为2005 - 1 32*1010 - 1，最少为5。同样，一棵有32*1010 - 1个关键字的200路查找树的高度可能是4，也可能是32*1010-2。对于给定的n个关键字，提高查找树的路数m，显然可以提高树的查找性能；但路数m确定之后，进一步改善查找性能的办法就是使树的高度h的值尽量地接近于logm n+1 - 1，才能使m路查找树的查找性能接近最佳。下面将讨论的B－树m路查找树。三、B－树⒈ B－树的定义一棵m阶 order B－树是一棵平衡的m路查找树，它满足如下性质：⑴ 根结点至少有两个子女；⑵ 除根结点之外的所有内部结点至少有 m/2 个子女。⑶ 所有外部结点 失败结点 都位于同一层上。例9.13 图9-24给出了两棵3路查找树，其中 a 是3阶B－树，它的所有外部结点都位于同一层上。而 b 则不是B－树。在图9-2 a 所示的B－树中查找关键字为95的记录，首先通过根指针找到根结点a，并进行关键字的比较：95 100，因此沿100的左侧指针找到下一层结点b；在结点b中进行关键字比较：95 90，沿的侧指针找到下一层结点在结点f中95 95，故查找成功，报告结点地址及关键字在结点中的序号。

98的记录，前面的过程与查找关键字为95的记录一样，然后在结点f中进行关键字比较：98 95，因此沿95的右侧指针进入到下一层的外部结点 失败结点 ，故查找失败。外部结点也称为失败结点 即查找失败时到达的结点 。把外部结点包括进来是为了便于分析和考虑问题。在实际实现中并不需要专门描述外部结点，只需用空指针来表示它。⒉ B－树的高度从上述的过程可见，B－树的查找过程是一个在结点内查找和沿某一条路经向下一层查找交替进行的过程。因此，在B－树上的查找时间与B－树的阶数m和B－树的高度h直接有关，必须加以权衡。在B－树上进行查找时，对于成功的查找所需的时间取决于关键字所在的层数；对于失败的查找所需的时间取决于树的高度。若定义B－树的高度h为外部结点 失败结点 的层数，那么下面的定理反映了高度h与B－树中的关键字个数n及B－树的阶数m三者之间存在的数量关系。定理 设一棵m阶B－树 包括外部结点 的高度为h，⑴ 2 m/2 h-1 - 1 ≤ n ≤ mh - 1⑵ logm n+1 ≤ h ≤ log m/2 n+1 /2 + 1证明 ⑴ 由于B－树是一棵m路查找，因此n的上限值在前面已经证明过了。

对于下限，根据B－树的定义，第0,1,2,…,h层的结点最小数目是1,2,2 m/2 ,2 m/2 , …, 2 m/2 h-2, 2 m/2 h-1，而相应的扩充的B－树的外部结点都在第h层上，因此B－树中外部结点个数的最小值为2 m/2 h-1。又由于外部结点的个数比关键字的个数多1个，所以有n +1 外部结点数 位于第h层的结点数 ≥ 2 m/2 h-1即 n ≥ 2 m/2 h-1 - 1⑵ 也是由于B－树为一棵m路查找树，因此h的下限值在前面也已经证明过了。对于上限，可由 ⑴ 直接推得。由以上定理⑴，由给定h与m, 可推出n的最小值。例如，一棵高度 h 为3的200 m 阶B－树中至少有19,999个关键字 n ；反之，由定理 ⑵，由给定n与m, 也可以推出h的最大值。从此定理还可以知道，只要B－树的阶数取得适当大 如m 200 ，即使树中的关键字数量再多，树的高度也是很小的。实际上，B－树的阶取决于磁盘页块 一次访外的容量 的大小和单个记录的大小。在内存容量允许的前提下，结点的大小应与磁盘页块的大小相当为宜。⒊ B－树的插入B－树的是从空树开始，逐个插入关键字而生成的。插入关键字的方法是：首先在树中查找K，若找到则查找成功，不用插入；否则查找操作必失败于某个叶结点 即最底层的内部结点 。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-14.html