データベーススペシャリスト試験 2016年 午前2 問02

解説

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