k次のB木構造において、ルートノードはi個(1≤i≤2k)のレコードをもち、ルート以外のノードはj個(k≤j≤2k)のレコードをもつものとする。
ルートノードを1段目とした場合、B木は1段目からn段目までに最大何レコードを格納することができるか。
ここで、k、nは自然数とし、n≥2とする。
ア | (2k + 1)n - 1 - 1 |
イ | (2k + 1)n - 1 |
ウ | 2(k + 1)n - 1 - 1 |
エ | 2(k + 1)n - 1 |
答え イ
【解説】
1段目のルートノードは最大で2k個で、2段目は2k個のルートノードがそれぞれ最大で2k個のレコードにつながるので、これからB木の全レコード数を求める計算式は
(2k + 1)n - 1
(イ)になる。
【キーワード】
・B木