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

解説

B+木インデックスは平衡木であり，木の高さはデータ件数Xに対して対数（log）オーダで増加します。したがって，候補キーを用いて1件のデータを検索する際にたどるノードへのアクセス回数のオーダはlogXになります。

選択肢ごとの解説

• ア誤り。√Xは平方根オーダであり，平衡木であるB+木の探索計算量とは一致しません。
• イ正しい。B+木は平衡木なので，木の高さ（アクセス回数）はデータ件数Xに対してlogXのオーダになります。
• ウ誤り。Xは全件を線形に走査する場合のオーダであり，索引を使わない場合に相当します。
• エ誤り。X!（階乗）は現実的な検索アルゴリズムのオーダとしてはあり得ない値です。