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

例如128路分支，则在仅仅寻找3个页块之后，就可以在100万个关键字的表中找出任何所希望的关键字。根页块一般常驻内存，因此只需对外存进行2次访问。但是，页块也不能任意大，页块一大，就需要在内存设置较大的缓冲区，并且读入一个页块也需要较多的时间。因此页块结点的大小要适中。一般m取值在200～500之间，实践中，应根据外部存储设备的特征，以及表中的记录的长度来确定m的取值。m路静态查找树一般属于静态索引结构，即结构在初始创建，数据装入时就已经生成，并在整个系统运行 例如插入与删除记录等 期间索引结构保持不变。只有当文件再组织时才允许改变其索引结构。多路树的叶结点存放数据记录，这些存放数据记录的外存空间称为数据基本区，而分支结点存放各子树结点中的最大 或最小 关键字，存放这些分支结点的外存空间称为索引区。在运行过程中，当要插入记录而数据基本区中应该存放此记录的块区已满时，就会发生溢出，此时把溢出的记录存放到另外开辟的溢出区中，而不改变索引的结构。把记录送入溢出区有两种方式：一种是要使数据基本区的记录和溢出区的记录仍保持有序性，即送入溢出区的记录是数据块区中的最后一个记录，不一定是入的记录。

如ISAM Indexed Sequential Access Methed 就是采用这种方式。另一种方式是不要求数据基本区的记录和溢出区的记录仍保持有序性，即发生溢出时直接把要插入的记录送入溢出区。对于存储在磁盘上的文件，若插入与删除不多时，通常建立三级索引的查找树是适当的。例如，若以磁道为基本存取单位，则建立的1、2、3级索引可以是主索引、柱面索引和磁道索引。二、动态的m路查找树下面给出可进行动态调整的m路查找树的定义：一棵m路查找树 m - way search tree 或者是一棵空树，或者是满足如下性质的树：⑴ 根结点最多有m棵子树，并具有如下的结构：（ j, p0, K1, p1, K2, p2, … , K j, p j ）其中，pi是指向子树的指针 0≤i≤j m ，Ki是记录的关键字 1≤i≤j m ，且每个关键字都相应有指向记录自身的指针。⑵ Ki Ki+1, 1≤i j。⑶ 在pi指向的子树中所有的关键字都大于Ki，但小于Ki+1，0 i j。⑷ 在p0指向的子树中所有的关键字都小于K1，而pj指向的子树中所有的关键字都大于Kj。⑸ pi指向的子树也是m路查找树，0≤i≤j。

例9.12 图9-23给出了一棵3路查找树，它有11个关键字。每个结点最多有3棵子树，因而最多有2个关键字，但最少有2棵子树，有1个关键字。结点a的格式为：（2, b, 50, c, 100, d）；结点b上所有记录的关键字均小于50；结点c上所有记录的关键字都介于50和100之间；结点e上所有记录的关键字都介于50和70之间；结点f上所有记录的关键字都介于90和100之间；结点g上所有记录的关键字都介于100和150之间；结点d上所有记录的关键字均大于100。对于图9-23所示的例子，如果想查找关键字为95的记录，需要从根开始查找。首先从磁盘中读入结点a，沿50与100之间的子树指针找到结点c；再读入结点c，沿90右侧子树指针找到结点f ；最后读入结点f ；在结点f中找到关键字为95的记录。显然，二叉排序树是2路查找树。一棵高度为h的m路查找树最少可以有h+1个关键字 每层一个结点，每个结点仅含一个关键字 ，最多可有mh+1 - 1个关键字 从0到h-1层的每个结点都含有m个子女，第h层的结点没有子女 不算外部结点 ，这样树的总结点数为 。由于每个结点都有m-1个关键字，所以关键字的总数为mh+1 -1 。

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