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

正解と解説

正解：イ (2k+1)^n-1

各ノードは最大2k個のレコードをもち、その場合の枝数は最大2k+1本になる。よって1段目は1ノード、2段目は2k+1ノード、m段目は(2k+1)^(m-1)ノードで、レコード数は各段のノード数に2kを掛けた等比数列の和になる。2k×{(2k+1)^n−1}/{(2k+1)−1}を計算すると(2k+1)^n−1が得られる。

選択肢ごとの解説

• ア指数がn−1では最下段のノード数までしか数えておらず、n段全体の合計にならない。
• イ正しい。2k×(等比数列の和)を整理すると、公比2k+1が分母の2kと約分されてこの式になる。
• ウ枝数は最大2k+1本であり、k+1を底にするのは誤り。
• エ底がk+1である点が誤りで、枝数の見積りが合っていない。

同じ分野の他の問題

• RDBMSのクラスタ化インデックスに関する記述のうち、適切なものはどれか。2025年度 秋期 午前II 問13
• 転置インデックスに関する記述として、適切なものはどれか。2024年度 秋期 午前II 問4
• 関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、B+木のリーフノードCがノードC1とC…2024年度 秋期 午前II 問3
• "部品"表のメーカーコード列に対し、B+木インデックスを作成した。これによって、"部品"表の検索の性能改善が最も期待でき…2023年度 秋期 午前II 問13
• B+木インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデック…2023年度 秋期 午前II 問4