root (23y)(49,1)(95, 0(151(23y③31)(4.y(4.(6os 02061115182329323841454952607795 head 必要时,还可以有4级索引,5极索引 9··· 这种多级索引结构形成一种m叉树。树中每 个分支结点表示一个索引块,每个索引项 给出各子树结点的最大关键码和结点地址
11 ◼ 必要时, 还可以有4级索引, 5极索引, …。 ◼ 这种多级索引结构形成一种m叉树。树中每 一个分支结点表示一个索引块, 每个索引项 给出各子树结点的最大关键码和结点地址。 02 06 11 15 18 23 29 32 38 41 45 49 52 60 77 95 (06, ) (15, ) (23, ) (32, ) (41, ) (49, ) (60, ) (95, ) (23, ) (49, ) (95, ) root head
树的叶结点中各索引项给出在数据表中存放 的对象的关键码和存放地址。这种m叉树用 来作为多级索引,就是m路搜索树。 。m路搜索树可能是静态索引结构,即结构在 初始创建,数据装入时就已经定型,在整个 运行期间,树的结构不发生变化。 m路搜索树还可能是动态索引结构,即在整 个系统运行期间,树的结构随数据的增删及 时调整,以保持最佳的搜索效率 12
12 ◼ 树的叶结点中各索引项给出在数据表中存放 的对象的关键码和存放地址。这种m叉树用 来作为多级索引，就是m路搜索树。 ◼ m路搜索树可能是静态索引结构，即结构在 初始创建，数据装入时就已经定型，在整个 运行期间，树的结构不发生变化。 ◼ m路搜索树还可能是动态索引结构, 即在整 个系统运行期间, 树的结构随数据的增删及 时调整, 以保持最佳的搜索效率
四级索引 三级索引 二级索引 0000000060-级索引 数据区 多级索引结构形成m路搜索树
13 多级索引结构形成 m 路搜索树 数据区 一级索引 二级索引 三级索引 四级索引
动态搜索结构 动态的m路搜索树 现在我们所讨论的m路搜索树多为可以动态 调整的多路搜索树,它的一般定义为 一棵m路搜索树,它或者是一棵空树,或者是 满足如下性质的树: 根最多有m棵子树,并具有如下的结构 n,P0,K1,P1,K2,P2 e·····9 Kn, P 其中,P是指向子树的指针,0≤i≤n<m;K 是关键码,1≤i≤n<mK1<K,1≤i<n
14 动态搜索结构 ◼ 现在我们所讨论的 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 C2530小a4550 e35 一棵3路搜索树的示例 15
15 ◆ 在子树 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