问答题 设有一棵B+树,其结点最多可存放100个索引项。对于高度为1、2、3、4的B+树,最多能存储多少索引项?最少能存储多少索引项?
【正确答案】
【答案解析】能存储多少索引项,主要看叶结点。非叶结点是对下层最多关键字的复写。
对于高度为1的B+树:根据B+树定义,根结点又是叶结点,最多可存储m=100个索引项,最少可存放1个索引项。
对于高度为2的B+树:最多可存储m×m=100 2 个索引项,最少可存储101个索引项。因为当根结点关键字个数n达到101,发生结点分裂,其高度才会变为2。
对于高度为3的B+树:最多可存储m×m×m=100 3 个索引项,最少可存储2×101=202个索引项。因为当第1层的关键字个数达到101做结点分裂,叶结点才会落到第2层,第2层2个结点,每个结点的关键字个数达到101引发结点分裂,叶结点落到第3层。此时,叶结点有51+50+51+50=202个索引项。
对于高度为4的B+树:第4层是叶结点。最多可存储m 4 =100 4 个索引项,最少可存储4×101=404个索引项。叶结点有51+50+51+50+51+50+51+50=404个索引项。