データベーススペシャリスト 2023年 午前2 問04

B+木インデックスの検索アクセス回数のオーダー【午前2 解説】

要点まとめ

• 結論：B+木インデックスを使った1件検索のアクセス回数はデータ件数$X$に対して$\log X$のオーダーです。
• 根拠：B+木は平衡木の一種であり、木の高さが$\log X$に比例するため、検索時のノードアクセス回数も$\log X$となります。
• 差がつくポイント：B+木の構造理解と、単純な線形探索や階乗オーダーとの違いを明確に把握することが重要です。

正解の理由

よくある誤解

解法ステップ

1. B+木の構造を理解する（平衡木であること、葉ノードにデータがあること）。
2. 木の高さがデータ件数$X$に対してどのように変化するかを考える。
3. 木の高さは$\log X$に比例するため、検索時のノードアクセス回数も$\log X$となる。
4. 選択肢の中から$\log X$を選ぶ。

選択肢別の誤答解説

• ア: $\sqrt{X}$
  → B+木の高さは平方根オーダーではなく、平衡木の特性から$\log X$です。
• イ: $\log X$
  → 正解。B+木の高さに比例し、効率的な検索が可能です。
• ウ: $X$
  → 線形探索のオーダーであり、B+木の高速検索の特徴を無視しています。
• エ: $X!$
  → 階乗は計算量として非現実的であり、木構造の検索とは無関係です。

補足コラム

FAQ