结构推理
根据多分树、B树或B+树的定义,假设外存页块的大小为4096字节,每个关键码和每个指针都占2字节,试计算它们各自的阶数,并且计算高度为5时它们能存储的索引项数的最大和最小值。
【正确答案】(1)计算它们各自的阶数
1)计算多分树的阶数
根据多分树的结构,多分树的一个结点最大不应该超过外存的一个页块。假设多分树为m分树,它的一个结点中最多有m个关键码和对应记录的地址。每个关键码和指针的长度都为2个字节,所以:
2×m×2≤4096
计算结果为多分树的阶数最大为1024。
2)计算B树的阶数
根据B树的概念,B树的一个结点最大不应该超过外存的一个页块。假设B树为m阶,一个B树的结点中最多存放m-1个关键码和指向相应记录的指针,另外还包括m个子树的根结点的位置。每个关键码和指针的长度都为2个字节,所以:
(2×(m-1)+m)×2≤4096
计算结果为B树的阶数最大为683。
3)计算B+树的阶树
根据B+树的概念,B+树的一个结点最大不应该超过外存的一个页块。假设B+树为m阶,一个B+树的结点中最多存放m个关键码和指向相应记录的指针。每个关键码和指针的长度都为2个字节,所以:
2×m×2≤4096
计算结果为B+树的最大阶数为1024。
(2)计算高度为5时它们能存储的索引项数的最大和最小值
1)1024分树
最大索引项数目 最小索引项数目
0层 1024 1
1层 10242 —
2层 10243 —
3层 10244 —
4层 10245 —
5层 10246 —
最大索引项数目为10246,最小索引项数目为1。
2)683阶B树
最大索引项数目 最小索引项数目
0层 683 1
1层 6832 2×341
2层 6833 2×342×341
3层 6834 2×342×342×341
4层 6835 2×342×342×342×341
5层 6836 2×342×342×342×342×341
高度为5的B树索引项最多为6836,最少为1+2×341×(1-3425)/(1-342)。
3)1024阶B+树
最大索引项数目 最小索引项数目
0层 1024 1
1层 10242 1024
2层 10243 1024×512
3层 10244 1024×5122
4层 10245 1024×5123
5层 10246 1024×5124
高度为5的B树索引项最多为10246,最少为1024×5124。
【答案解析】