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

この問題は2024(R6)秋データベーススペシャリスト午前IIに出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

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

ア.

イ.

ウ.

エ.

解答・解説を読む

正解: 選択肢イ

関係データベースのインデックスとして広く利用される B⁺木（B-plus tree） の構造と、データ追加時のノード分割の振る舞いに関する問題です。

B⁺木のリーフノード（葉ノード）にレコードが追加され、容量の上限を超えるとノードの分割が発生します。リーフノードCが C1 と C2 に分割された場合、以下の2つの処理が行われます。

親ノード（中間ノードA）へのキーとポインタの追加
分割された新しいノードC2を指し示すため、中間ノードAにC2の最小キー値とC2への ポインタ が追加されます。問題文で「中間ノードAには十分な空きがある」とされているため、中間ノードA自体の分割は発生せず、AからC1およびC2のそれぞれに対して下向きのポインタが張られる形になります。
リーフノード間のリンク（シークエンスセット）
B⁺木の最大の特徴は、範囲検索を高速化するために すべてのリーフノードがポインタで順番に連結されている 点です。そのため、分割後もC1からC2へ向かう横方向のポインタ（リンク）が必ず維持されます。

これらの条件（AからC1・C2へのポインタが存在し、かつC1からC2へのポインタが存在する）を満たす構造が正解（イ）となります。

アの解説
リーフノード間のリンク（横方向のポインタ）が欠落していると考えられます。B⁺木においてリーフノード同士の連結がない構造は誤りです（通常のB木の構造に相当します）。
イの解説（正解）
中間ノードAからC1およびC2へのポインタが正しく追加されており、かつリーフノードC1からC2へのポインタ（リンク）も保持されています。B⁺木の分割後の構造として適切な形です。
ウの解説
中間ノードAからリーフノードへのポインタの構造が誤っている、あるいはC2のポインタの繋がり先が不適切であるなど、B⁺木の正しい分割処理に反する構造です。
エの解説
問題文で「中間ノードAには十分な空きがある」と指定されているにもかかわらず中間ノードが分割されている、またはポインタの参照関係が崩れているなど、不適切なツリー構造を示しているため誤りです。