情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成28年度秋期 午前Ⅰ 問9: B+木インデックスが定義されている候補キーを利用して，1 件のデータを検索するとき，データ総件数 X に対する B+木インデックスを格納するノードへのアクセス回

問題本文

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

選択肢

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

正解

イ. logX

解説

B+木インデックスによる1件検索のアクセス回数のオーダを問う問題。B+木は多分木（高さが低く保たれる平衡木）で，候補キー検索では根から葉までの段数だけノードをたどればよい。段数はデータ総件数Xの対数に比例するため，アクセス回数のオーダはlog X。よってイが正解。DBの索引がO(log X)で高速に絞り込める根拠であり，全件走査O(X)との差を理解しておくことが性能設計の基本。

選択肢ごとの解説

• ア.√Xはハッシュやグリッド系の見積りで，木の段数で決まるB+木探索には当てはまらない。
• イ.B+木の高さはデータ件数の対数に比例し，根から葉までlog Xのアクセスとなるため正しい。
• ウ.Xは全件を順に走査する場合のオーダで，索引で絞り込むB+木検索には過大で誤り。
• エ.X!は組合せ爆発のオーダで，検索のアクセス回数とは無関係であり明らかに誤り。