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

索引探索を考えるときの着眼点

索引を使う探索では、検索条件と索引の構成がどのように対応するかを整理し、対象データの範囲、比較の単位、読み取り方に影響する要素を順に確認します。用語の役割も区別しましょう。

この問題で問われていること

一つの検索条件に対して、索引のどの部分が探索対象になり得るかという対応関係に集中し、処理全体を細かな操作へ分解して、各段階の役割と前後関係を丁寧に考えてみましょう。

視点

検索条件、索引のキーの並び、値の比較単位、対象範囲の広がりを分けて整理します。個々の条件が探索対象をどう絞り得るかを確認し、実データの読み取りや追加条件との関係は別に捉えると、手順の説明を比較しやすくなります。

確認ポイント

• 検索条件と索引キーの対応関係を確認する
• 探索対象の範囲がどの条件で変わるかを確認する
• 索引の確認後に必要となる処理を区別して捉える

正解

イ

解説

B+木は各ノードで複数の候補へ分岐しながら探索範囲を狭めるため、1件検索で訪れるノード数は木の高さに対応します。総件数Xに対する高さは対数オーダーです。

理由

B+木の分岐数を b、データ総件数を X 件とすると、木の高さは h=O(log_b X) 段になります。したがって、根から該当する葉までのノードアクセス回数は O(log_b X) 回です。分岐数 bを定数として扱えば、オーダーは O(log X) 回となります。

比較

√X、X、X!は、B+木で階層をたどって候補範囲を絞り込む1件検索のアクセス回数を表すオーダーとは一致しません。設問で示された条件には、これらの増え方を生じさせる追加条件はありません。

選択肢ア

これは不正解だよ。√Xは、総件数が増えたときの探索ノード数を、B+木の階層構造から説明するオーダーではありません。1件検索のアクセス回数は、候補キーで絞り込む木の高さに対応し、この値とは一致しません。

選択肢イ（正解）

これは正解だよ。B+木では、各ノードから複数の子へ分岐して探索範囲を狭めるため、総件数Xに対する木の高さは対数オーダーになります。1件検索のノードアクセスは根から該当葉までの経路に沿うので、O(log X)です。

選択肢ウ

これは不正解だよ。Xはデータ総件数そのものの増加割合を表す値で、B+木の階層探索におけるノードアクセス回数のオーダーではありません。各段階で候補範囲を分岐して狭める条件を反映していないため、1件検索の値としては不適切です。

選択肢エ

これは不正解だよ。X!は総件数に対して階乗で増える値ですが、設問はB+木のノードを経路に沿ってアクセスする回数を問うています。設問には階乗的にアクセスが増える条件はなく、このオーダーを導けません。

学習のポイント

木構造の分岐と、検索時に通過する階層数の関係を理解する。