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