令和6年度 秋期 午前Ⅱ 問3
トランザクション処理
ノード分割後のB^+木構造
関係データベースのテーブルにレコードを1件追加したところ，インデックスとして使う，B^+木のリーフノードCがノードC1とC2に分割された。ノード分割後のB^+木構造はどれか。ここで，矢印はノードへのポインタとする。また，中間ノードAには十分な空きがあるものとする。
分割前のB^+木（原典は図。ノードとポインタ（矢印）を書き写した。⇄は両方向の矢印）:
（外部）→ A A → B，A → C，A → D リーフの並び: B ⇄ C ⇄ D
選択肢は原典では図（ノードとポインタ）。
- ア（原典は図。A → B，A → C1，A → D。リーフの並び: B ⇄ C1 ⇄ C2 ⇄ D）
- イ（原典は図。A → B，A → C1，A → C2，A → D。リーフの並び: B ⇄ C1 ⇄ C2 ⇄ D）
- ウ（原典は図。A → B，A → C1，A → D，A → C2。リーフの並び: B ⇄ C1 ⇄ D ⇄ C2）
- エ（原典は図。A → B，A → C1，A → D。リーフの並び: B ⇄ C1 ⇄ D，C1 ⇄ C2（C2はC1の下に置かれている））
答えと解説を見る
✓ これが正解イ（原典は図。A → B，A → C1，A → C2，A → D。リーフの並び: B ⇄ C1 ⇄ C2 ⇄ D）
解説
分割後は親Aが C1 と C2 を指し、葉は B、C1、C2、D の順です。
B+木では、すべてのデータが葉ノードに置かれ、葉ノードはキーの順に横方向のポインタでつながっています。葉ノードCがあふれて C1 と C2 に分割されると、C の内容がキーの順に前半と後半へ分かれます。分割で生まれた新しい葉にも根から到達できるように、親である中間ノードAに、C2 を指すポインタと境目のキーを追加します。Aには十分な空きがあるので、Aが分割されることはありません。葉同士のつながりも、B、C1、C2、D とキーの順に張り直されます。見分ける軸は、親から新しい葉へのポインタがあるか、葉のつながりがキーの順か、葉がすべて同じ深さにあるかの三点です。
ほかの選択肢はなぜ違うのか
- ア（原典は図。A → B，A → C1，A…：葉のつながりはキーの順になっていますが、中間ノードAから C2 へのポインタがありません。根からたどって C2 に到達できないので、C2 に移ったキーを検索するときに目的の葉を直接見つけられなくなります。
- ウ（原典は図。A → B，A → C1，A…：中間ノードAから C2 へのポインタはありますが、葉のつながりが B、C1、D、C2 の順になっています。C2 には元の C の後半のキーが入るので、D より後ろに置くとキーの順序が崩れ、範囲検索を正しく行えません。
- エ（原典は図。A → B，A → C1，A…：C2 を C1 の下にぶら下げると、C1 は葉ではなく中間ノードの役割を持ち、C2 だけが一段深い位置に置かれます。葉がすべて同じ深さにそろうという、平衡木としての B+木の形が崩れてしまいます。
この問題の用語
- 関係データベースデータを表の形で持ち、表どうしを結びつけて扱う、最も広く使われているデータベース。データの定義や操作にはSQLを使います。
出典：令和6年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問3
同じ用語が出る問題
- 令和7年度 秋期 午前Ⅱ 問11：参照制約に関する問題（関係データベース）
- 令和6年度 秋期 午前Ⅱ 問5：主キーに関する問題（関係データベース）
- 令和3年度 秋期 午前Ⅱ 問15：入れ子ループ法に関する問題（関係データベース）
- 令和3年度 秋期 午前Ⅱ 問2：UMLに関する問題（関係データベース）
- 令和2年度 10月 午前Ⅱ 問6：主キーに関する問題（関係データベース）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）