解説

k次のB木構造における最大レコード数の計算【午前2 解説】

要点まとめ

• 結論：B木の最大レコード数はルートを含む全段のノード数の合計で決まり、答えは $(2k + 1)^n - 1$ です。
• 根拠：ルートノードは最大 $2k$ 個のレコードを持ち、子ノード数は最大 $2k+1$ 個。各段でノード数が $(2k+1)$ 倍に増えるため、全段の合計は等比数列の和となります。
• 差がつくポイント：ルートノードのレコード数の範囲と子ノード数の関係を正確に理解し、段数ごとのノード数の増加を正しく計算できるかが重要です。

正解の理由

• ルートノードは最大 $2k$ 個のレコードを持ち、子ノード数は最大 $2k+1$ 個です。
• ルート以外のノードは最大 $2k$ 個のレコードを持ちます。
  1段目（ルート）は1ノードで最大 $2k$ レコード、2段目は最大 $(2k+1)$ ノード、3段目は $(2k+1)^2$ ノード…と増加します。
  したがって、$n$ 段目までの最大ノード数は
  $1 + (2k+1) + (2k+1)^2 + \cdots + (2k+1)^{n-1} = \frac{(2k+1)^n - 1}{(2k+1) - 1} = \frac{(2k+1)^n - 1}{2k}$
  各ノードが最大 $2k$ 個のレコードを持つため、最大レコード数は
  $2k \times \frac{(2k+1)^n - 1}{2k} = (2k+1)^n - 1$
  よって、選択肢イが正解です。

よくある誤解

解法ステップ

1. ルートノードの最大レコード数と子ノード数を確認する（$2k$ と $2k+1$）。
2. 各段のノード数が $(2k+1)$ 倍で増えることを理解する。
3. $n$ 段目までのノード数の合計を等比数列の和で計算する。
4. 各ノードの最大レコード数 $2k$ を掛けて最大レコード数を求める。
5. 計算結果を選択肢と照合し、正解を選ぶ。

選択肢別の誤答解説

• ア: $(2k + 1)^{n - 1} - 1$
  → ノード数の合計を1段目から数えず、段数を1つ少なく計算している。
• イ: $(2k + 1)^n - 1$
  → 正解。全段のノード数合計に最大レコード数を正しく掛けた結果。
• ウ: $2(2k + 1)^{n - 1} - 1$
  → ルートノードのレコード数を2と誤認し、段数の指数もずれている。
• エ: $2(2k + 1)^n - 1$
  → ルートノードのレコード数を2と誤認し、指数は正しいが掛け算が誤り。

補足コラム

FAQ