問題プレビューID: 8491f8a9応用情報技術者試験 2016年(平成28年度)秋期 午前

問 27
応用情報技術者試験 2016年(平成28年度)秋期 午前

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

解説

正解は「イ」です。

B+木インデックスは,データを木構造で管理するインデックスです。1 件のデータを検索する際は,根から葉までノードをたどっていくため,ノードへのアクセス回数は木の高さに比例します。データ総件数 X に対する木の高さは O(log X) となるので,アクセス回数のオーダは logX です。

  • ア(√X): ハッシュなどの方式の目安で,B+木の検索オーダではありません。
  • ウ(X): 全件を順に調べる線形探索の場合のオーダです。
  • エ(X!): 階乗であり,検索のオーダではありません。

関連問題

本文が同じ・似ている問題を表示しています