ホーム > データベーススペシャリスト試験 > 2024年
データベーススペシャリスト試験 2024年 午前2 問03
関係データベースのテーブルにレコードを1件追加したところ, インデックスとして使う木のリーフノードCがノードC1とC2に分割された。ノード分割後のB+木構造はどれか。ここで, 矢印はノードへのポインタとする。また, 中間ノードAには十分な空きがあるものとする。
ア：A→B→C→Dの構造である。
イ：A→B→C1→C2→Dの構造である。（正解）
ウ：A→B→C1→D→C2の構造である。
エ：A→B→C1→D→C2の構造である。
解説
解説：B+木のノード分割後の構造について
関係データベースのインデックスとして使われる木は、データの挿入や削除によってノードが満杯になると「ノード分割（スプリット）」という操作を行い、木の高さを調整しつつデータの検索効率を保ちます。
問題の状況整理
- あるリーフノードCにレコードを1件追加した結果、ノードCが2つのノードに分割された：
- ノードC1
- ノードC2
- 中間ノードAは空きがあり、そこに分割されたノードの情報を取り込むことが可能。
- 矢印は「ノードへのポインタ」を示している。
B+木のノード分割の基本
-
リーフノードの分割
- リーフノードCが満杯になったため、分割して新しいリーフノードC2を作ります。
- データは均等に分割される（例えば、キーの小さい方をC1、大きい方をC2に）。
- 新しく分割されたリーフノードC2へのポインタ（リーフノードの最小キー）が親ノード（中間ノード）に挿入されます。
-
親ノードへの影響
- 分割したリーフノードを指す新しいポインタ（キー）が親ノードBに挿入されます。
- 親ノードBに空きがあれば、そのまま挿入されます。
- この問題では、さらに中間ノードAに空きがあるため、影響はBからAに伝わる可能性があります。
問題の選択肢の確認
- ア: (A \to B \to C \to D) — ノード分割前の状態に見える。分割によりCは２つに分かれたため不適切。
- イ: (A \to B \to C1 \to C2 \to D) — 分割されたリーフノードC1とC2が連続しており自然な構造。
- ウ: (A \to B \to C1 \to D \to C2) — 途中にDが入り、順序が崩れているため不自然。
- エ: (A \to B \to C1 \to D \to C2) — ウと同じ理由で不適切。
正解の理由（イが正しい）
- リーフノード分割後は、CはC1とC2という並列のリーフノードになります。
- B+木では、リーフノードは横方向に「連結リスト」のようにつながっており、C1の次はC2、C2の次はDという形で順序を保ちます。
- 親ノードは、分割により追加されたC2の最小キーのポインタを持つため、祖先ノードからは(A \to B \to C1 \to C2 \to D)という枝分かれのない順序になります。
まとめ
B+木のリーフノードが分割されると、分割された2つのリーフノードは横に並んで連結され、その親ノードには新たなポインタ（キー）が挿入される。よって、ノードCがノードC1とC2に分割されると、木の構造は
となり、選択肢の中でイが正解となります。
参考文献
- 『データベースシステム概論』（著：原顕三郎）
- 『アルゴリズムとデータ構造』（著：小暮俊弘）
以上の理由で正解は イ となります。