情報処理安全確保支援士試験 情報処理安全確保支援士試験 平成30年度春期 午前Ⅰ 問8: 関係データベースのテーブルにレコードを1件追加したところ，インデックスとして使う，図のB⁺木のリーフノードCがノードC1とC2に分割された。ノード分割後のB⁺木

問題本文

関係データベースのテーブルにレコードを1件追加したところ，インデックスとして使う，図のB⁺木のリーフノードCがノードC1とC2に分割された。ノード分割後のB⁺木構造はどれか。ここで，矢印はノードへのポインタとする。また，中間ノードAには十分な空きがあるものとする。

選択肢

• ア.（図）中間ノードAから子ノードB，C1，C2，Dへポインタが伸び，リーフはB↔C1↔C2↔Dの順で双方向に連結されている。
• イ.（図）中間ノードAから子ノードB，C1，C2，Dへポインタが伸び，リーフはB↔C1↔C2↔Dの順で連結されているが，AからC2へのポインタの向きなどが異なる。
• ウ.（図）中間ノードAから子ノードB，C1，D，C2へポインタが伸び，リーフがB↔C1↔D↔C2の順に連結されている。
• エ.（図）中間ノードAから子ノードB，C1，Dへポインタが伸び，C2はC1の下にぶら下がる（C1↔C2が縦に連結された）構造。

正解

イ. （図）中間ノードAから子ノードB，C1，C2，Dへポインタが伸び，リーフはB↔C1↔C2↔Dの順で連結されているが，AからC2へのポインタの向きなどが異なる。

解説

B⁺木でリーフCが満杯になり新レコードで分割されると、CはC1とC2の2つのリーフになる。親の中間ノードAにはB・C1・C2・Dへのポインタが正しく張られ、リーフ層はB↔C1↔C2↔Dの順に双方向連結されて順次アクセスを保つ必要がある。この正しい結線を示すのがイで正解。B⁺木はDBインデックスの基礎で、分割後も整列と連結が保たれる点が要点。

選択肢ごとの解説

• ア.結線は近いが親ポインタの向きなどに不整合があり、正しい分割後構造になっておらず誤り。
• イ.AからB・C1・C2・Dへ正しくポインタが張られリーフもB↔C1↔C2↔Dに連結され正解。
• ウ.リーフがB↔C1↔D↔C2と並び順が崩れており、整列保持に反するため誤り。
• エ.C2をC1の下に縦にぶら下げる形はB⁺木のリーフ構造として不正で誤り。