结构推理 似定一个文件约有1000000条记录,每条记录占200字节,其中关键码占50字节。一个页块有1000字节,页块指针为5字节。若用B+树组织索引,应该设计成几阶的B+树?并假定所有页块都尽可能装满,需要多少索引块?在上述文件组织中更新一个记录需要访问外存多少次?为什么?
【正确答案】每个页块的大小为1000个字节,可放5条记录。共有1000000条记录,故需200000个页块。每个索引项(包括关键码和页块指针)共55字节,故每个页块最多可放18个索引项(即可以设计为18阶的B+树)。
   200000个索引项需200000/18=11112个页块(题目没有说明所建立的是密集索引还是稀疏索引,这里按常用的稀疏索引计算);根据B+树的概念,所有的索引都应该在叶结点中出现。因此,B+树中叶结点的个数也是11112个。
   倒数第一层共有11112/18=618个结点:
   倒数第二层共有618/18=35个结点;
   倒数第三层共有35/18=2个结点:
   故总共需要1+2+35+618=656个非叶结点;从根结点到叶结点共5层,即需访问5次,第6次才能访问到文件记录。
【答案解析】