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

正解

イ. logX

問題の解説

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

選択肢ごとの解説

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