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

索引探索を整理する一つの視点

索引を使う問題では、いきなり答えを選ばず、検索条件とデータの並び方、参照が進む順序の関係を切り分けて考えます。まず処理の目的を言い換え、各段階で何を確認するかを整理しましょう。

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

確認する観点は、検索条件が索引のどの情報と結び付くかです。条件の表し方、対象範囲、参照後に必要となる処理を順に見て、説明同士の前提が揃っているかを比べます。

視点

索引探索は、条件、索引内の配置、候補の絞り込み、元データとの対応という要素に分けて眺めると整理しやすくなります。特定の方式名だけで判断せず、処理の目的と前提を対応させて確認します。

確認ポイント

• 検索条件が、索引で扱う情報とどのように対応しているかを確認する
• 候補を絞り込む段階と、対象データを参照する段階を分けて整理する
• 説明に含まれる前提と処理の順序が、互いに矛盾していないかを確認する

正解

イ

解説

B+木のリーフノードが分割された場合、新しく分かれたリーフは同じリーフ層に並び、親である中間ノードからそれぞれ参照される。中間ノードAには十分な空きがあるため、必要なポインタを追加できる。したがって、リーフの順序と親からの参照が保たれているイが適切です。

理由

B+木では、リーフノードCがC1とC2に分割されると、C1とC2は元のリーフ層に置かれる。また、リーフ同士の順序関係を保ちながら、上位の中間ノードAから分割後の各ノードへ到達できる構造にする必要がある。Aには十分な空きがあるため、ポインタの追加を妨げる条件もない。

比較

イは、C1とC2を同じリーフ層に配置し、リーフの並びを保ち、Aから両方のノードを参照している。アはAからC2への参照が不足している。ウはリーフの順序が崩れている。エはC2をC1の下位に置いており、リーフ分割後の同一階層という条件に合わない。

選択肢ア

これは不正解だよ。図ではC1とC2がリーフ層に並んでいるものの、Aから直接参照されるポインタの配置が分割後の構造を十分に表していない。リーフ同士の連結だけでなく、親の中間ノードから分割された各リーフへ到達できることが必要である。

選択肢イ（正解）

これは正解だよ。CがC1とC2に分割された後、両ノードは同じリーフ層に置かれ、元のリーフ順序を保っている。さらに、空きのある中間ノードAが分割後の各リーフを参照しており、B+木の親子関係とリーフ連結の条件を満たしている。

選択肢ウ

これは不正解だよ。C1とC2を分割後のノードとして配置しているが、図ではリーフの並びが元の順序と一致しない。B+木のリーフ分割では、検索順序を維持したまま隣接関係を保つ必要があるため、この配置は不適切である。

選択肢エ

これは不正解だよ。C2をC1の下位に置いているため、分割された二つのノードが同じリーフ層に並ぶ構造になっていない。B+木ではリーフノードを階層の最下層にそろえる必要があり、この親子配置は条件に合わない。

学習のポイント

B+木のリーフ分割時における親ノードのポインタ更新とリーフ連結の理解。