扫码获取更多资源

●B_树、B十树和键树

B_树是一种平衡的多路查找树，它适合在磁盘等直接存取设备上组织动态的查找表, 在文件系统中非常有用。一棵m阶的B—树，或为空树，或为满足下列特性的m叉树：

（1）树中每个结点至多有m棵子树。

（2）如果根不是叶结点，则至少有两棵子树。

（3）除根之外的所有非终端结点至少有「m/2〕棵子树。

在实用中，与每个关键字存储在一起的不是相关的辅助信息域，而是一个指向另一磁盘 页的指针，称为记录指针。磁盘页中包含该关键字所代表的记录，而相关的辅助信息正是存 储在此记录中。

有的B_树(如后面介绍的B十树)是将所有辅助信息都存于叶结点中，而内部结点(不 妨将根亦看作是内部结点)中只存放关键字和指向孩子结点的指针，无须存储指向辅助信息 的指针，这样使内部结点的度数尽可能最大化。

在大多数系统中，B_树上的算法执行时间主要由读、写磁盘的次数来决定，每次读写尽 可能多的信息可以提高算法的执行速度。B_树有以下几个特点：

(1)B_树中的结点的规模一般是一个磁盘页，而结点中所包含的关键字及孩子的数目 取决于磁盘页的大小。

(2)对于磁盘上一棵较大的B_树，通常每个结点所拥有的孩子数目(即结点度数)m为 50至2000不等。

(3)选取较大的结点度数可以降低树的深度，减少查找任意关键字所需要的磁盘访问 次数。

(4)通常根可以始终置于主存中，因此在这棵B_树中查找任一关键字至多只需要二次 访问外存。

B_树的查找规律

(1)如果其左子树不空，则左子树上所有结点的值均小于根结点的值；

(2)如果其右子树不空，则右子树上所有结点的值均大于根结点的值；

(3)其左右子树也都是二叉排序树。

从上述定义可以看岀，二叉排序树是记录之间满足一定次序关系的二叉树，中序遍历二 叉排序树可以得到一个按关键字有序的序列。例如前面讨论的折半查找判定树就是一棵二 叉排序树。

二叉排序树的査找

由B一树的定义可知.在B_树上进行查找的过程和二叉排序树的查找类似。

(1) 查找成功。 例如，在图8-20所示的B_树上给定查找关键字42：从根开始，根据根结点指针t找到 a结点；因为42>32,则顺指针找到c结点；因为40V42V64,则顺时针找到g结点；在该 结点中顺序查找找到关键字42,查找成功。

(2) 查找不成功。 例如，在图8-20所示的B_树上给定查找关键字23：从根开始，根据根结点指针t找到

a结点；因为23V32,则顺指针找到b结点；因为b结点中只有一个关键字16,且23>16, 则顺指针找到e结点；因为23V28,则顺指针往下找；此时因为指针所指为叶结点，说明此 棵B_树中不存在关键字23,查找失败。 由此可见，在B_树上进行查找的过程是一个顺指针查找结点与在结点的关键字中查 找交叉进行的过程。

多重链表表示

如果以树的多重链表表示键树，则树的每个结点中应包含d个（d为关键字符的基，例 如字符集由英文大写字母构成时，d = 26 + l = 27）指针域，此时的键树又称为Trie树。Trie 树中有两种结点：分支结点，含有d个指针域，整数n记录非空指针域的个数（可选）；叶子 结点，含有关键字域（完整的关键字，可选）、附加数据域名（可选）。

实际实现的时候，一般都只包含d个指针域。在标准Trie树的基础上，可以压缩，如果 从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则可将该路径上的所有 结点压缩成一个叶子结点。

如果以树的孩子兄弟表示，则每个结点包含三个域：symbol域，存储关键字的一个字 符；son域，存储指向第一棵子树的根的指针，叶子结点的son域指向该关键字记录的指针； brother域，存储指向右兄弟的指针。这时的键树又称为双链树。

联系我们：