平成28年度 春期 データベーススペシャリスト試験 午前Ⅱ 問2
テクノロジ／データベースk次のB木構造において，ルートノードはi個（1≦i≦2k）のレコードをもち，ルート以外のノードはj個（k≦j≦2k）のレコードをもつものとする。ルートノードを1段目とした場合，B木は1段目からn段目までに最大何レコードを格納することができるか。ここで，k，nは自然数とし，n≧2とする。
出典：平成28年度 春期 データベーススペシャリスト試験 午前Ⅱ 問2
- ア(2k＋1)ⁿ⁻¹－1
- イ(2k＋1)ⁿ－1
- ウ2(k＋1)ⁿ⁻¹－1
- エ2(k＋1)ⁿ－1
正解：イ
解説
ルートノードは最大i＝2k個，ルート以外のノードも最大j＝2k個のレコードをもち，レコード数がmのノードは子ノードをm＋1個もつため，各ノードの子ノード数は最大で2k＋1個になります。したがって，m段目に存在する最大ノード数は，1段目（ルートのみ）が1個，2段目が(2k＋1)個，m段目が(2k＋1)^(m-1)個となり，各ノードが最大2k個のレコードをもつことから，1段目からn段目までに格納できる最大レコード数は，2k×{1＋(2k＋1)＋(2k＋1)²＋…＋(2k＋1)^(n-1)}＝2k×{(2k＋1)ⁿ－1}／(2k)＝(2k＋1)ⁿ－1 となります。
選択肢ごとの解説
- ア誤り。指数がn－1になっており，1段目からn－1段目までの最大レコード数に相当する式であるため，1段目からn段目までを求める本問の答えとしては段数が一つ不足しています。
- イ正しい。ルートを含む各ノードが最大2k個のレコードをもち，各ノードの最大子ノード数が2k＋1であることから，1段目からn段目までの最大レコード数は(2k＋1)ⁿ－1になります。
- ウ誤り。底が(k＋1)になっており，各ノードの最大子ノード数が2k＋1であるという条件を反映していないため，誤った式です。
- エ誤り。ウと同様に底が(k＋1)になっている上，指数もnのままであり，B木の分岐数や各ノードの最大レコード数の条件と整合しません。