问答题 利用B树作文件索引时,若假设磁盘页块的大小是4000字节(实际应是2的n次幂,题目为了计算方便,假定是4000字节),指示磁盘地址的指针需要5个字节。现在有20000000个记录构成的文件,每个记录为200字节,其中包括关键字5个字节。
试问在此采用B树作索引的文件中,B树的阶数应为多少?假定文件数据部分未按关键字有序排列,则索引部分需要占用多少磁盘页块?
【正确答案】
【答案解析】根据B树的概念,一个索引结点应适应操作系统一次读写的物理记录大小,其大小应取不超过但最接近一个磁盘页块的大小。假设B树为m阶,一个B树结点最多存放m-1个关键字(5个字节)和对应的记录地址(5个字节),外加m个子树指针(5个字节)和1个指示结点中实际关键字个数的整数(2个字节)。根据假设,每个关键字和指针都占用5个字节,则有:
[2×(m-1)+n]×5+2≤4000
计算结果,m≤267。
一个索引结点最多可以存放m-1=266个索引项,最少可以存放[m/2]-1=133个索引项。全部有n=20000000个记录,每个记录占用空间200个字节,每个页块可以存放4000/200=20个记录,则全部记录分别在20000000/20=1000000个页块中,则最多需要占用1000000/133=7519个磁盘页块作为B树索引,最少需要占用1000000/266=3759个磁盘页块作为B树索引。(注意B树与B+树的不同。B树所有对数据记录的索引项分别在各个层次的结点中,B+树所有对数据记录的索引项都在叶结点中)