B对 B树
B树
动态查找结构 动态的m路查找树 现在我们所讨论的m路查找树多为可以动态调 整的多路查找树,它的一般定义为 一棵mn路查找树,它或者是一棵空树,或者是满 足如下性质的树 根最多有m棵子树,并具有如下的结构: n,A0,(K1A1),(K2,A2),………,(Kn,An) 其中,A是指向子树的指针,0≤i≤n<m; K是关键码,1≤i≤n<m。K1<K,1≤i<n
动态查找结构 现在我们所讨论的m路查找树多为可以动态调 整的多路查找树，它的一般定义为： 一棵m路查找树, 它或者是一棵空树, 或者是满 足如下性质的树： 根最多有 m 棵子树, 并具有如下的结构： n, A0 , ( K1 , A1 ), ( K2 , A2 ), ……, ( Kn , An ) 其中，Ai 是指向子树的指针，0 i n < m； Ki 是关键码，1 i n < m。 Ki < Ki+1 , 1 i < n。 动态的m路查找树
0在子树A1中所有的关键码都小于K1,且大于 K;,0<i<n 0在子树An中所有的关键码都大于Kn 在子树A中的所有关键码都小于K1 子树A1是m路查找树,0≤i≤m 20.40 d 1015 2530 4550 35 一棵3路查找树的示例
在子树 Ai 中所有的关键码都小于 Ki+1，且大于 Ki，0 < i < n。 在子树 An 中所有的关键码都大于Kn； 在子树 A0 中的所有关键码都小于 K1。 子树 Ai 也是 m 路查找树，0 i n。 一棵3路查找树的示例
A树是2路查找树。如果已知m查找树的度m 和它的高度h,则树中的最大结点数为 (等比级数前h项求和)∑m (m1-1) 每个结点中最多有m-1个关键码,在一棵高 度为h的m路查找树中关键码的最大个数为 nr+1-1。 对于高度h=2的二叉树,关键码最大个数为 7 对于高度h=3的3路查找树,关键码最大个 数为3-1=80
AVL树是2路查找树。如果已知m路查找树的度m 和它的高度 h, 则树中的最大结点数为 ( 1) 1 1 1 0 − − = + = h h i i m m (等比级数前 h 项求和) m 每个结点中最多有 m-1 个关键码，在一棵高 度为 h 的 m 路查找树中关键码的最大个数为 mh+1-1。 对于高度 h=2 的二叉树，关键码最大个数为 7； 对于高度 h=3 的3路查找树，关键码最大个 数为 3 4-1 = 80
提高查找树的路数m,可以改善树的查找性能 对于给定的关键码数n,如果查找树是平衡的 可以使m路查找树的性能接近最佳。下面我们 将讨论一种称之为B-树的平衡的m路查找树。 在B树中我们引入“失败”结点。一个失败结 点是当查找值不在树中时才能到达的结点
提高查找树的路数 m，可以改善树的查找性能。 对于给定的关键码数 n，如果查找树是平衡的， 可以使 m 路查找树的性能接近最佳。下面我们 将讨论一种称之为B-树的平衡的 m 路查找树。 在B-树中我们引入“失败”结点。一个失败结 点是当查找值x不在树中时才能到达的结点