情報処理安全確保支援士試験の公開問題
2016 秋 午前I 問09
このページはIPA Advancedが運営する非公式の学習用ページです。IPAとの提携・公認を示すものではありません。
問題文
B+木インデックスが定義されている候補キーを利用して，1件のデータを検索するとき，データ総件数 X に対する B+木インデックスを格納するノードへのアクセス回数のオーダを表す式はどれか。
選択肢
- ア: √X
- イ: log X
- ウ: X
- エ: X!
解説の要点
添付の公式解答PDF画像では，午前Ⅰ試験の問9の正解は「イ」と記載されている。B+木は葉の深さがそろった平衡木であり，候補キーによる検索では，根からキーに対応する葉へ進む。各階層で進む枝を選び，おおむね木の高さに相当する回数だけノードへアクセスする。分岐数を一定と考えると，木の高さはデータ総件数 X に対して対数的に増えるので，アクセス回数のオーダは log X となる。対数の底の違いは定数倍の違いであり，オーダには影響しない。
データ件数とアクセス回数の関係を考える前に、何を1回と数え、増え方をどう表すか調べてみましょう。
関連する問題一覧
公式出典
訂正・編集方針
解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。