応用情報技術者 2018年春期午前2 問26

問題文

関係データベースのテーブルにレコードを1件追加したところ、インデックスとして使う、図の

B^{+}

木のリーフノードCがノード C1とC2に分割された。ノード分割後の

B^{+}

木構造はどれか。ここで、矢印はノードへのポインタとする。また、中間ノードAには十分な空きがあるものとする。

選択肢

ア：

イ：（正解）

ウ：

エ：

関係データベースの $B^{+}$ 木ノード分割問題【午前2 解説】

要点まとめ

結論：ノード分割後は親ノードAが分割したノードCを2つの子ノードC1、C2に分けて4本のポインタを持つ構造になるため、選択肢イが正解です。
根拠： $B^{+}$ 木のノード分割では、分割したノードの中間キーが親ノードに昇格し、親ノードのポインタ数が増加します。親ノードAに空きがあるため、分割後のノードをすべて指せます。
差がつくポイント：親ノードのポインタ数の変化と、リーフノード間の双方向リンクの正確な配置を理解しているかが合否を分けます。

正解の理由

B^{+}

木のリーフノードCが分割されると、元のノードCはC1とC2に分かれます。このとき、分割したノードの中間キーが親ノードAに昇格し、Aは元の3本のポインタから4本に増えます。選択肢イは、AからB、C1、C2、Dの4本の矢印が伸びており、リーフノード間の双方向リンクも正しくB–C1、C1–C2、C2–Dと連結されています。これが

B^{+}

木のノード分割後の正しい構造です。

よくある誤解

親ノードのポインタ数は変わらないと誤解しがちですが、ノード分割時は増加します。
リーフノードの双方向リンクを更新しないと、検索効率が低下します。

解法ステップ

$B^{+}$ 木のリーフノードCが分割されることを理解する。
分割により新たにC1とC2の2つのリーフノードができる。
分割したノードの中間キーを親ノードAに昇格させる。
親ノードAのポインタ数が3本から4本に増えることを確認。
リーフノード間の双方向リンクをB–C1、C1–C2、C2–Dに正しく設定する。
選択肢の図と照合し、これらの条件を満たすものを選ぶ。

選択肢別の誤答解説

ア：AからC2へのポインタがなく、分割後の親ノードのポインタ数が不足しているため誤り。
イ：親ノードAが4本のポインタを持ち、リーフノード間の双方向リンクも正しいため正解。
ウ：C2がDの右側に配置されており、リーフノードの順序が不自然で誤り。
エ：C2がC1の下に配置されており、 $B^{+}$ 木のリーフノードの水平リンク構造に反しているため誤り。

補足コラム

B^{+}

木はデータベースのインデックス構造として広く使われています。リーフノードはすべて同じ深さにあり、リーフノード間は双方向リストで連結されているため、範囲検索が高速に行えます。ノード分割時には親ノードに中間キーを昇格させ、木の高さを抑えつつバランスを保ちます。

FAQ

Q: なぜ親ノードに中間キーを昇格させるのですか？
A: ノード分割でキーが増えたため、親ノードに中間キーを昇格させて木の構造を保ち、検索効率を維持します。

Q: リーフノード間の双方向リンクはなぜ必要ですか？
A: 範囲検索や連続したデータの取得を高速化するため、リーフノードは双方向リストで連結されています。

応用情報技術者 2018年 春期 午前2 問26

問題文

選択肢

関係データベースのB+木ノード分割問題【午前2 解説】