B⁺木インデックスの検索のオーダ
出典: 平成28年度 秋期 応用情報技術者試験 午前 問27 (IPA)
B⁺木インデックスが定義されている候補キーを利用して，1 件のデータを検索するとき，データ総件数 X に対する B⁺木インデックスを格納するノードへのアクセス回数のオーダを表す式はどれか。
- ア √X
- イ log X
- ウ X
- エ X!
正解と解説を見る
正解: イ
- ア: √X は、データを √X 個ずつのグループに分けて探すような方法のオーダです。
- イ: B⁺木は根から葉までの段数分だけノードにアクセスするので、log X のオーダです。正しい答えです。
- ウ: X は、データを先頭から順に全部調べる線形探索のオーダです。
- エ: X! は、全ての並べ方を調べるような、非常に効率の悪い処理のオーダです。
ポイント
- B⁺木 は、1 つのノードからたくさんの枝が出る、バランスの取れた木構造です。
- 根から葉までの段数は、データの件数 X が増えても log X に比例 する程度しか増えません。1 件を探すときにアクセスするノードの数は、この段数分なので log X のオーダです。