応用情報技術者 2016年 秋期 午前2 問27
問題文
インデックスが定義されている候補キーを利用して、1件のデータを検索するとき、データ総件数Xに対する木インデックスを格納するノードへのアクセス回数のオーダを表す式はどれか。
選択肢
ア：
イ：（正解）
ウ：
エ：
B⁺木インデックスの検索回数のオーダー【午前2 解説】
要点まとめ
- 結論：B⁺木インデックスを使った1件検索のアクセス回数はデータ件数に対してのオーダーである。
- 根拠：B⁺木は平衡木構造であり、木の高さがに比例するため、検索時のノードアクセス回数もとなる。
- 差がつくポイント：線形探索や単純な配列検索と異なり、B⁺木は階層的に絞り込むため大規模データでも高速に検索可能である点を理解すること。
正解の理由
B⁺木は多分岐の平衡木であり、各ノードが複数のキーを持つため木の高さが低く抑えられます。
そのため、件のデータを格納していても、検索時にアクセスするノード数は木の高さに相当し、これはのオーダーとなります。
よって、選択肢の中で唯一を示すイが正解です。
そのため、件のデータを格納していても、検索時にアクセスするノード数は木の高さに相当し、これはのオーダーとなります。
よって、選択肢の中で唯一を示すイが正解です。
よくある誤解
B⁺木の検索回数を単純な線形探索のようにやと誤解しやすいですが、B⁺木は階層構造で高速に絞り込むためアクセス回数は対数オーダーです。
解法ステップ
- B⁺木の構造を理解する（多分岐の平衡木であること）。
- 木の高さがデータ件数に対してであることを確認する。
- 1件の検索は木の高さ分のノードアクセスが必要であると認識する。
- 選択肢の中からを示すものを選ぶ。
選択肢別の誤答解説
- ア:
→ B⁺木の高さはではなく、もっと低いのオーダーです。 - イ:
→ 正解。B⁺木の高さに比例し、効率的な検索が可能です。 - ウ:
→ 線形探索のオーダーであり、B⁺木の高速検索特性を無視しています。 - エ:
→ 計算量として非現実的であり、木構造のアクセス回数とは無関係です。
補足コラム
B⁺木はデータベースやファイルシステムで広く使われるインデックス構造です。
ノード内に複数のキーを持つことで木の高さを抑え、ディスクI/O回数を減らす設計が特徴です。
また、葉ノードは連結リストでつながっており範囲検索も効率的に行えます。
ノード内に複数のキーを持つことで木の高さを抑え、ディスクI/O回数を減らす設計が特徴です。
また、葉ノードは連結リストでつながっており範囲検索も効率的に行えます。
FAQ
Q: なぜB⁺木はのオーダーになるのですか？
A: B⁺木は多分岐の平衡木で、各ノードが複数の子を持つため木の高さがに抑えられ、検索時のノードアクセス回数もそれに比例します。
A: B⁺木は多分岐の平衡木で、各ノードが複数の子を持つため木の高さがに抑えられ、検索時のノードアクセス回数もそれに比例します。
Q: B木とB⁺木の違いは何ですか？
A: B⁺木はすべてのデータが葉ノードに格納され、葉ノードが連結リストでつながっている点が特徴で、範囲検索に優れています。
A: B⁺木はすべてのデータが葉ノードに格納され、葉ノードが連結リストでつながっている点が特徴で、範囲検索に優れています。
関連キーワード: B⁺木、インデックス、検索アルゴリズム、平衡木、データベース
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！