结构推理
求B树存储的最大记录数:
(1)高度为3的5阶B树;
(2)高度为5的5阶B树;
(3)高度为h的5阶B树。
【正确答案】要使5阶B树存储记录数达到最大,必须使每个结点都有5棵子树。
(1)0层为根结点,有5棵子树,因此这一层能存储4条记录;1层有5个结点,每个结点5棵子树,因此这一层存储5×4=20条记录;2层有5×5=25个结点,每个结点5棵子树,因此这一层存储25×4=100条记录;3层有5×5×5=125个结点,每个结点5棵子树,因此这一层存储125×4=500条记录;故最大能存储624条记录。
(2)同理,最多能存储15624条记录。
(3)h=0,能存储4条;
h>0,最多能存储4+20+100+…+4×5h=5h+1-1条记录。
【答案解析】