B+木インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対するB+木インデックスを格納するノードへのアクセス回数のオーダーはどれか。

選択肢

• ア√X
• イlog X
• ウX
• エX!

正解と解説

正解：イ log X

B+木は根から葉へ向かって多分岐でたどる平衡木で、木の高さはデータ件数の対数に比例する。検索は根から葉まで1経路をたどるだけなので、アクセス回数のオーダーは件数の対数になる。よってイが正しい。

選択肢ごとの解説

• ア平方根に比例する増え方は、ハッシュの衝突処理や一部の分割方式に見られるもので、B+木の高さの見積りではない。
• イ正解。木の高さが件数の対数に比例するため、たどるノード数も対数オーダーになる。
• ウ件数に比例するのは索引を使わない全件走査の場合である。
• エ階乗のオーダーは組合せの数え上げに現れるもので、木の探索とは無関係。

同じ分野の他の問題

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