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