データベーススペシャリスト 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の構造である。
関係データベースのテーブルにレコードを1件追加した際のB+木ノード分割問題【午前2 解説】
要点まとめ
- 結論：ノード分割後は親ノードAのポインタが増え、分割したリーフノードCはC1とC2に分かれ、Aからそれぞれ指される構造になる。
- 根拠：B+木のリーフノード分割時は分割したノードの最小キーが親ノードに昇格し、親ノードのポインタ数が増えるため。
- 差がつくポイント：親ノードのポインタ数増加とリーフノード間の双方向リンクの正しい配置を理解しているかが重要。
正解の理由
正解はイです。B+木のリーフノードCが分割されてC1とC2になると、親ノードAは新たにC2へのポインタを持ちます。したがって、AからはB、C1、C2、Dの4つの子ノードへのポインタが存在します。また、リーフノードは双方向リストで連結されているため、B⇔C1、C1⇔C2、C2⇔Dの双方向リンクが正しく配置されています。これがB+木のノード分割後の標準的な構造です。
よくある誤解
リーフノード分割後も親ノードのポインタ数が変わらないと誤解しやすいです。また、リーフノード間の双方向リンクの順序や接続が変わることはありません。
解法ステップ
- B+木のリーフノード分割の基本動作を理解する。
- 分割されたリーフノードの最小キーが親ノードに昇格し、親ノードのポインタ数が増えることを確認。
- 親ノードAのポインタ数が増え、分割されたノードC1とC2の両方を指す構造になることを把握。
- リーフノード間は双方向リストで連結されているため、分割後も隣接ノード間の双方向リンクが正しく配置されているか確認。
- 選択肢の図と説明を照合し、正しいポインタ数とリンク構造を持つものを選択。
選択肢別の誤答解説
- ア：親ノードAからC1とC2の両方にポインタが出ているが、C1とC2の間に親ノードのポインタがないため、ポインタ数が不足。
- イ：正解。親ノードAからB、C1、C2、Dの4つの子ノードへのポインタがあり、リーフノード間の双方向リンクも正しい。
- ウ：親ノードAのポインタ順序が不自然で、C2がDの右側にあるためリーフノードの順序が崩れている。
- エ：親ノードAのポインタ数が3つのままで、分割されたC2が親ノードの子ではなくC1の下にぶら下がっている誤りがある。
補足コラム
B+木はデータベースのインデックス構造として広く使われています。リーフノードはデータの実体を持ち、双方向リストで連結されているため範囲検索が高速です。ノード分割時は親ノードに新しいキーとポインタが追加され、木の高さが変わることもありますが、今回は親ノードに十分な空きがあるため高さは変わりません。
FAQ
Q: なぜリーフノードの分割で親ノードのポインタ数が増えるのですか？
A: 分割したリーフノードの最小キーが親ノードに昇格し、新たな子ノードとしてポインタが追加されるためです。
A: 分割したリーフノードの最小キーが親ノードに昇格し、新たな子ノードとしてポインタが追加されるためです。
Q: リーフノード間の双方向リンクはなぜ必要ですか？
A: 範囲検索や順次アクセスを効率化するため、リーフノードは双方向リストで連結されています。
A: 範囲検索や順次アクセスを効率化するため、リーフノードは双方向リストで連結されています。
Q: 親ノードに空きがない場合はどうなりますか？
A: 親ノードも分割され、さらに上位ノードにキーが昇格することで木の高さが増加します。
A: 親ノードも分割され、さらに上位ノードにキーが昇格することで木の高さが増加します。
関連キーワード: B+木、ノード分割、インデックス構造、リーフノード、双方向リスト、親ノードポインタ増加
\ せっかくなら /
データベーススペシャリストを
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！