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

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

正解の根拠

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

1. 親ノード（中間ノードA）へのキーとポインタの追加
   分割された新しいノードC2を指し示すため、中間ノードAにC2の最小キー値とC2への ポインタ が追加されます。問題文で「中間ノードAには十分な空きがある」とされているため、中間ノードA自体の分割は発生せず、AからC1およびC2のそれぞれに対して下向きのポインタが張られる形になります。

2. リーフノード間のリンク（シークエンスセット）
   B⁺木の最大の特徴は、範囲検索を高速化するために すべてのリーフノードがポインタで順番に連結されている 点です。そのため、分割後もC1からC2へ向かう横方向のポインタ（リンク）が必ず維持されます。

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

各選択肢の解説

• アの解説
  リーフノード間の横方向のポインタ（B⇔C1⇔C2⇔D）はありますが、中間ノードAからC2へのポインタがありません。C2の最小キー値とポインタが親ノードAに追加されていないため、分割後の構造として誤りです。
• イの解説（正解）
  中間ノードAからC1およびC2へのポインタが正しく追加されており、かつリーフノードC1からC2へのポインタ（リンク）も保持されています。B⁺木の分割後の構造として適切な形です。
• ウの解説
  中間ノードAからリーフノードへのポインタの構造が誤っている、あるいはC2のポインタの繋がり先が不適切であるなど、B⁺木の正しい分割処理に反する構造です。
• エの解説
  中間ノードAからC2へのポインタがなく、C2はC1の下にC1とだけ連結されていて、リーフノードの横方向の連結（B⇔C1⇔D）にも入っていません。不適切なツリー構造を示しているため誤りです。