必要时,还可以有4级索引,5极索引, 这种多级索引结构形成一种m叉树。树中 每一个分支结点表示一个索引块,它最多存 放m个索引项,每个索引项分别给出各子树 结点(低一级索引块)的最大关键码和结点 地址。 树的叶结点中各索引项给出在数据表中存放 的对象的关键码和存放地址。这种m叉树用 来作为多级索引,就是m路搜索树。 am路搜索树可能是静态索引结构,即结构在 初始创建,数据装入时就已经定型,在整个 运行期间,树的结构不发生变化
m路搜索树还可能是动态索引结构,即在整 个系统运行期间,树的结构随数据的增删及 时调整,以保持最佳的搜索效率 四级索引 三级索引 二级索引 级索引 数据区 多级索引结构形成m路搜索树
动态搜索结构 动态的m路搜索树 现在我们所讨论的m路搜索树多为可以动 态调整的多路搜索树,它的一般定义为: 棵m路搜索树,它或者是一棵空树,或者 是满足如下性质的树: ◆根最多有m棵子树,并具有如下的结构: m,P0p(K1P1)(K2,P2)2…(KP) 其中,P是指向子树的指针,0≤i≤m<m;K 是关键码,1≤江≤m<m。K<K1≤i<
在子树P中所有的关键码都小于K1,且 大于胚,0<i<n ●在子树P中所有的关键码都大于Kn; ◆在子树P中的所有关键码都小于K1。 ◆子树P也是m路搜索树,0≤i≤n a20140 b1015c25304d4550 e35 棵3路搜索树的示例
35 a 20 40 b c d e 10 15 25 30 45 50
m路搜索树的类定义 template< class Type> class mtree{∥基类 public Triple<Type>& Search( const Type &) protected Node<Type> root int m AVL树是2路搜索树。如果已知m路搜索树的 度m和它的高度h则树中的最大结点数为 等比级数前b项求和)∑m=1,(mr-) i=0
template <class Type> class Mtree { //基类 public: Triple<Type> & Search ( const Type & ); protected: Mnode<Type> root; int m; } 1 1 1 1 0 h h i i m m (等比级数前 h 项求和) m