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

問題本文

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

選択肢

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

正解

イ. logX

解説

B+木インデックスを使った検索の計算量(オーダ)を問う問題。B+木は1つのノードから複数の枝を出す多分木で、根から葉まで木の高さ(段数)分だけノードをたどれば目的のキーに到達する。データ件数Xが増えても木は横に広がるため高さの増加は緩やかで、高さはおおむねXの対数に比例する。したがって1件検索に必要なノードへのアクセス回数のオーダは O(log X) となり、正解はイである。これは2分探索と同様に「件数が増えてもアクセス回数の増え方が非常に緩やか」という対数オーダの性質に基づく。

選択肢ごとの解説

• ア.√X(平方根オーダ)は件数の平方根に比例する増加で、B+木の高さ(対数)よりはるかに速く増えるため、B+木検索のオーダとしては誤り。
• イ.B+木は高さが件数Xの対数に比例し、根から葉まで O(log X) 回のノードアクセスで検索できるため、正しい。
• ウ.X(線形オーダ)は全件を順に調べる線形探索のオーダであり、インデックスを使わない場合の計算量。B+木検索には当てはまらず誤り。
• エ.X!(階乗オーダ)は組合せ爆発を起こす極めて大きな増加であり、検索のアクセス回数を表すものではなく誤り。