第10章索引与散列 ABC DG K MN PR ST Uw 插入E U ABCIIDEG IK MN ST U 插入H GIM PR 插入O,L ABCIDE GH MNOIPR ST 插入J ABCDE GH L MNO 10-12设有一棵B+树,其内部结点最多可存放100个子女,叶结点最多可存储15个记录 对于1,2,3,4,5层的B+树,最多能存储多少记录,最少能存储多少记录 【解答】 层B+树:根据B+树定义,一层B+树的结点只有一个,它既是根结点又是叶结点 最多可存储m1=15个记录,最少可存储「m1/21=8个记录。 二层B+树:第0层是根结点,它最多有m=100棵子树,最少有2个结点;第1层是 叶结点,它最多有m个结点,最多可存储m*m1=100*15=1500个记录,最少有2个结点, 最少可存储2*m1/21=16个记录 三层B+树:第2层是叶结点。它最多有m2个结点,最多可存储m2*m1=15000个记 录。最少有2*「m/21=100个结点,最少可存储2*「m/21*「m1/21=800个记录 四层B+树:第3层是叶结点。它最多有m3个结点,可存储m3*m1=15000000个记录 最少有2*「m/212=2*502=5000个结点,存储2*「m/212*「m121=4000个记录。 五层B+树:第4层是叶结点。它最多有m4个结点,可存储m4*m1=15000000个记第 10 章 索引与散列 6 插入 E 插入 H 插入 O, L 插入 J 10-12 设有一棵 B+树，其内部结点最多可存放 100 个子女，叶结点最多可存储 15 个记录。 对于 1, 2, 3, 4, 5 层的 B+树，最多能存储多少记录，最少能存储多少记录。 【解答】 一层 B+树：根据 B+树定义，一层 B+树的结点只有一个，它既是根结点又是叶结点， 最多可存储 m1 = 15 个记录，最少可存储 m1/2 = 8 个记录。 二层 B+树：第 0 层是根结点，它最多有 m = 100 棵子树，最少有 2 个结点；第 1 层是 叶结点，它最多有 m 个结点，最多可存储 m*m1 = 100*15 = 1500 个记录，最少有 2 个结点， 最少可存储 2* m1/2 = 16 个记录。 三层 B+树：第 2 层是叶结点。它最多有 m2 个结点，最多可存储 m2 * m1 = 150000 个记 录。最少有 2* m/2 = 100 个结点，最少可存储 2* m/2 * m1/2 = 800 个记录。 四层 B+树：第 3 层是叶结点。它最多有 m3 个结点，可存储 m3 * m1 = 15000000 个记录。 最少有 2* m/2 2 = 2 * 502 = 5000 个结点，存储 2* m/2 2 * m1/2 = 40000 个记录。 五层 B+树：第 4 层是叶结点。它最多有 m4 个结点，可存储 m4 * m1 = 1500000000 个记 A B C D I M D G M N S U I K P R S T U W A B C D I M D E G M N S U P I K P R S T U W A B C D G I M D E M N S U P G H I K P R S T U W D E M N O S U P G H P R S T A B C I K L U W D G I M D E M N O S U I P G H P R S T A B C I J K L D G U W K M