応用情報技術者試験平成30年春午前問26 解説付き過去問

問題

関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図のB⁺木のリーフノードCがノードC1とC2に分割された。
ノード分割後のB⁺木構造はどれか。
ここで、矢印はノードへのポインタとする。
また、中間ノードAには十分な空きがあるものとする。

この問題は、関係データベースにおけるB⁺木インデックス構造において、リーフノードの分割後の構成が正しく維持されているかを問うものです。B⁺木の構造的特性と、ノード分割時の挙動を正しく理解することが求められます。

B⁺木の基本構造
B⁺木は、平衡木（バランス木）の一種で、検索効率を高めるために使用されるインデックス構造です。主な特徴は以下の通りです。
・データ（レコード）はリーフノードにのみ格納される
・中間ノード（非リーフノード）はキーと子ノードへのポインタのみを持つ
・全てのリーフノードは横方向に連結されており、全てのパスの長さ（根からリーフまでの距離）は同一である
ノード分割時の挙動
リーフノードCがレコードの追加により収容できなくなった場合、ノードCは2つのノードC1とC2に分割されます。このとき、分割されたノードのうち、上位側（C2）の先頭キーが中間ノードAに昇格され、Aのキー群の中に追加されます。Aには十分な空きがある前提のため、ノードの再分割は不要です。
また、リーフノードの分割後も、横方向のポインタは順序通りに接続されていなければなりません（B→C1→C2→Dのように昇順で連結）。
正しい構造の判定
このように、ノードAが昇格キーを追加してC1とC2へのポインタを正しく持ち、リーフノードが昇順で連結されている構成が正しいB⁺木です。