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不在树中时才能到达的结点
B-树 一棵m阶B-树是一棵m路查找树,它或者是空树,或 者是满足下列性质的树: 0树中每个结点至多有m棵子树; 根结点至少有2棵子树; 操结点以外的所有非终端结点至少有m2棵 所有非终端结点中包含下列信息数据(l,A,k1 尝:包1:期简字语点斜 针, 为关键学的个 数 0所有的叶子结点(失败结点)都位于同一层。 事实上,每个结点中还应包含指向每个关键字的记 录的指针
B-树 一棵 m 阶B-树是一棵 m 路查找树，它或者是空树，或 者是满足下列性质的树： 树中每个结点至多有m棵子树； 根结点至少有 2 棵子树； 除根结点以外的所有非终端结点至少有 m/2 棵 子树； 所有非终端结点中包含下列信息数据 ( n, A0 , K1 , A1 , K2 , A2 , … , Kn , An )，其中： Ki (i=1,…,n)为关键 字，且Ki < Ki+1 , Ai (i=0,…,n)为指向子树根结点的指 针, n为关键字的个数 所有的叶子结点（失败结点）都位于同一层。 事实上，每个结点中还应包含指向每个关键字的记 录的指针
4 15125301450 35 1015 25135 非B-树 B-树
非B-树 B-树
B-树的查找算法 B树的查找过程是一个顺指针查找结点和在结 点的关键字进行查找交又进行的过程。因此 B-树的查找时间与B-树的阶数m和B-树的高度h 直接有关,必须加以权衡。 在B-树上进行查找,查找成功所需的时间取决 于关键码所在的层次,查找不成功所需的时间 取决于树的高度。如果我们定义B树的高度h为 失败结点所在的层次,需要了解树的高度h与树 中的关键码个数N之间的关系
B-树的查找算法 B-树的查找过程是一个顺指针查找结点和在结 点的关键字进行查找交叉进行的过程。因此， B-树的查找时间与B-树的阶数m和B-树的高度h 直接有关，必须加以权衡。 在B-树上进行查找，查找成功所需的时间取决 于关键码所在的层次，查找不成功所需的时间 取决于树的高度。如果我们定义B-树的高度h 为 失败结点所在的层次，需要了解树的高度h 与树 中的关键码个数 N 之间的关系
高度h与关键码个数N之间的关系 0设在m阶B-树中,失败结点位于第h+层。 在这棵B-树中关键码个数N最小能达到多少? 从B-树的定义知, 1层1个结点 2层至少2个结点 3层至少2「m/21个结点 4层至少2「m/212个结点 0如此类推, nh层至少有2「m/2142个结点。所有这些结 点都不是失败结点
设在 m 阶B-树中，失败结点位于第h +1层。 在这棵B-树中关键码个数N 最小能达到多少？ 从B-树的定义知, 1层 1 个结点 2层 至少 2 个结点 3层 至少 2 m / 2 个结点 4层 至少 2 m / 2 2 个结点 如此类推， h 层 至少有2 m / 2 h-2个结点。所有这些结 点都不是失败结点。 高度h与关键码个数 N 之间的关系
若树中关键码有N个,则失败结点数为N+1 这是因为失败一般发生在K;<x<K1,0≤i≤N 设K0=-00,KN+1=+∞。因此,有 N+1=失败结点数= 位于第h+层的结点数≥2m/2141 N≥2「m/214-1-1 反之,如果在一棵m阶B-树中有N个关键码 则所有的非失败结点所在层次都小于h,则 h-1≤ log m/2(+1)/2) 示例:若B-树的阶数m=199,关键码总数N 199999则B树的高度h不超过 log1001000000+1=4
若树中关键码有 N 个, 则失败结点数为 N +1。 这是因为失败一般发生在 Ki < x < Ki+1, 0 i N， 设K0 = -，KN+1 = +。因此，有 N +1 = 失败结点数 = = 位于第 h+1 层的结点数 2 m / 2 h-1 N 2 m / 2 h-1-1 反之，如果在一棵 m 阶B-树中有 N 个关键码， 则所有的非失败结点所在层次都小于h，则 h-1 log m / 2 ( (N +1) / 2 ) 示例：若B-树的阶数 m = 199，关键码总数N = 1999999，则B-树的高度 h 不超过 log100 1000000 +1= 4