第10章索引与散列 [c0 10-10对于一棵有199999关键码的199阶B树,试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点) 【解答】 设B树的阶数m=199,则m/21=100。若不包括失败结点层,则其最大层数为 Llogrm/(N+1)2)+1=lg0010000001=4 若使得每一层关键码数达到最大,可使其层数达到最小。第0层最多有(m-1)个关键码,第 1层最多有(m-1)2个关键码,…,第h1层最多有(m-1)个关键码。层数为h的B树最多有 (m-1)+(m-1)2+…+(m-1)1=(m-1)(m-1)-1)/(m-2)个关键码。反之,若有n个关键 码,n≤(m-1)((m-1)-1)/(m-2),则h≥ log(m-)(n(m-2)/(m-1)+1),所以,有199999 个关键码的199阶B树的最小层数为 「 log (m-1)(n(m-2)(m-1)+1)1=「log198(199197/198+1)1=Iog1819898991 10-11给定一组记录,其关键码为字符。记录的插入顺序为{C,S,D,T,AMP,L,B,W,N,G, U,R,K,E,HO,LJ},给出插入这些记录后的4阶B+树。假定叶结点最多可存放3个记录 【解答】 插入C,S,D插入T 插入A 插入M CDS ST A C 插入P 插入I DMS DMP ST A C I AP ST 插入B,WN,G 插入U IDMS ABCIDGIMNPI IST ABCIDGI ANPIST UW 插入R PR 插入K第 10 章 索引与散列 5 10-10 对于一棵有 1999999 个关键码的 199 阶 B 树，试估计其最大层数(不包括失败结点) 及最小层数(不包括失败结点)。 【解答】 设 B 树的阶数 m = 199，则m/2 = 100。若不包括失败结点层，则其最大层数为 logm/2 ((N+1)/2) + 1 = log100 1000000 +1 = 4 若使得每一层关键码数达到最大，可使其层数达到最小。第 0 层最多有(m-1)个关键码，第 1 层最多有(m-1)2 个关键码，，第 h-1 层最多有(m-1)h 个关键码。层数为 h 的 B 树最多有 (m-1) + (m-1)2 + … + (m-1)h-1 = (m-1) ( (m-1)h – 1 ) / (m-2)个关键码。反之，若有 n 个关键 码，n ≤ (m-1) ( (m-1)h – 1 ) / (m-2)，则 h ≥ log (m-1) (n(m-2)/(m-1)+1)，所以，有 1999999 个关键码的 199 阶 B 树的最小层数为 log (m-1) (n*(m-2)/(m-1)+1) = log198 (1999999*197 / 198 +1) = log 198 1989899 10-11 给定一组记录，其关键码为字符。记录的插入顺序为 { C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J }，给出插入这些记录后的 4 阶 B+树。假定叶结点最多可存放 3 个记录。 【解答】 插入 C, S, D 插入 T 插入 A 插入 M 插入 P 插入 I 插入 B, W, N, G 插入 U 插入 R 插入 K 55 80 20 30 60 70 95 C D S C D S T S A C D S T S A C D S D M S T A C D S D M P S T A C D M S D I M P S T A B C D M S D G I M N P S T W A B C D M S U D G I M N P S T U W A B C D M D G I M N P R S T U W S U P P