応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問27: B+木インデックスが定義されている候補キーを利用して，1 件のデータを検索するとき，データ総件数 X に対する B+木インデックスを格納するノードへのアクセス回

正解

イ. logX

正答率 62.2%（526人中 327人が正解）

問題の解説

B+ 木は、各節点が多数の枝を持つ平衡木で、根から全ての葉までの深さが等しい。データ総件数 X に対して木の高さは対数で増える (底は節点の枝数) ので、1 件を検索するときにたどる節点の数は のオーダになる。

選択肢ごとの解説

• ア√X のオーダは、データを平方根程度の区画に分けて探すような方式の計算量で、B+ 木の検索には当てはまらない。
• イ正しい。B+ 木は平衡木で、高さが件数の対数に比例するため、根から葉までたどる節点へのアクセス回数は log X のオーダになる。
• ウX のオーダは、先頭から順に全件を調べる線形探索の計算量である。インデックスを使う B+ 木では、もっと少ない回数で済む。
• エX! (階乗) のオーダは、組合せを総当たりで調べるような場合の計算量であり、検索の回数としては大きすぎる。