结构推理 根据多分树、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
【答案解析】