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

選択肢

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

正解と解説

正解：イ logX

B+木は根から葉まで階層をたどる木構造で、1つのノードが多数の子を持つため木の高さはデータ件数の対数に比例します。候補キーで1件を検索する場合、根から葉までのノードをたどる回数がアクセス回数になるので、オーダは log X です。件数が増えても高さの伸びが緩やかなことが、大規模な表でも高速に検索できる理由です。

選択肢ごとの解説

• ア平方根に比例するのは木構造ではなく、別のデータ構造の性質です。
• イ正解。木の高さが件数の対数に比例するためです。
• ウ全件を走査する全表探索のオーダで、インデックスを使う意味がありません。
• エ階乗のオーダは組合せを列挙する処理などで現れる値です。

同じ分野の他の問題

• “売上”表への次の検索処理のうち、B木インデックスよりもハッシュインデックスを設定した方が適切なものはどれか。ここで、イ…2025年度 秋期 午前 問27
• SQL文に示す参照制約が存在する"商品"表と"受注"表とがある。"商品"表の行を削除したとき，削除した行の商品コードと同…2025年度 春期 午前 問27
• 関係を第2正規形から第3正規形に変換する手順はどれか。2025年度 春期 午前 問26
• UMLを用いて表した図のデータモデルを関係データベース上に実装する際の解釈のうち，適切なものはどれか。2025年度 春期 午前 問25
• 次のオブジェクト図（インスタンスを表す図）に対応する概念データモデルはどれか。ここで、オブジェクト図及び概念データモデル…2024年度 秋期 午前 問29