IPA公式正解：イ (2k+1)ⁿ-1
※ 正解はIPA公表の解答です。解説は当サイトが生成AIを用いて作成しています。誤りにお気づきの場合はお問い合わせください。
【解説】正解は選択肢【イ】です。各ノードが最大2k個のレコードをもつとき、ノードから分岐するポインタ数は最大2k+1となります。m段目のレコード数は最大2k×(2k+1)^(m-1)個となり、1段目からn段目までの合計は等比数列の和として (2k+1)^n - 1 と導出されます。
【詳細解説】■ 本問の核心・解法のポイント
B木における最大格納レコード数を等比数列の和から導く問題です。
各ノードのレコード数が最大となるのは、すべてのノードが上限である「2k個」のレコードをもつ場合です。ノード内にr個のレコードがあるとき、子ノードへのポインタ数は r+1 個となるため、各ノードからの分岐数は最大で「2k+1」となります。
・各段の最大レコード数：
- 1段目（ルート）：2k 個
- 2段目：ルートの(2k+1)個の子ノード × 2k = 2k(2k+1) 個
- m段目：2k(2k+1)^(m-1) 個
1段目からn段目までの合計レコード数 S は、初項 2k、公比 (2k+1)、項数 n の等比数列の和となります。
S = 2k × {(2k+1)^n - 1} / {(2k+1) - 1}
分母の (2k+1) - 1 は 2k ですので、分子の 2k と約分されます。
S = (2k+1)^n - 1
・各選択肢の徹底解説：
・ア：段数を n-1 と誤って計算した場合の式です。
・【選択肢イ★】：正しい導出結果です。(2k+1)^n - 1 となります。
・ウ：分岐数とノードあたりのレコード数の関係の誤りです。
・エ：分岐数を誤認した式です。
よって正解はイです。
