令和5年度 秋期 データベーススペシャリスト試験 午前II 問4

B⁺木インデックスは、データを効率よく検索・更新・削除するためにデータベースなどで広く用いられている木構造（平衡多分木）です。

各ノードは複数のキーと子ノードへのポインタを持ち、常に木の高さが均等になるようバランスが保たれています。データ総件数を $X$ としたとき、1ノードあたりの分岐数を $N$ とすると、木の高さはおおよそ $\log_N X$ となります。ルートノードからリーフノードに向かって階層をたどりながら検索を行うため、ノードへのアクセス回数（探索の計算量）は木の高さに比例し、オーダーとしては $\log X$ となります。

各選択肢の解説

• ア：$\sqrt{X}$
  誤りです。平方分割などの手法を用いた場合の検索オーダーですが、B⁺木インデックスのオーダーではありません。

• イ：$\log X$
  正解です。 B⁺木を含む平衡二分探索木や多分木の検索にかかる計算量のオーダーです。

• ウ：$X$
  誤りです。インデックスを利用せずにデータを先頭から順番に比較していく線形探索（フルテーブルスキャン）を行った場合のオーダーです。

• エ：$X!$
  誤りです。巡回セールスマン問題における単純な全探索など、組み合わせ爆発を起こす非常に計算量の大きいアルゴリズムのオーダーです。