問題プレビューID: b6c77314基本情報技術者試験 午前免除試験 2017年12月10日

問 27
基本情報技術者試験 午前免除試験 2017年12月10日

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

解説

正解は「イ」です。

B+木は,各ノードが複数のキーと子へのポインタをもち,木の高さが釣り合うように構成された平衡多分木です。1 件のデータを検索するときは,根から葉までをたどるだけなので,アクセスするノード数は木の高さに相当します。データ総件数を XX とすると,木の高さは O(log⁡X)O(\log X) となるため,ノードへのアクセス回数のオーダは log⁡X\log X です。

  • ア: ハッシュインデックスなどで理想的な場合の探索を想起させる値ですが,B+木の探索順序とは異なります。
  • ウ: 全件を線形に走査する場合のオーダです。
  • エ: 順列の総数を表す階乗であり,探索回数のオーダではありません。

関連問題

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