応用情報技術者試験 応用情報技術者試験 平成30年度春期 午前 問26: 関係データベースのテーブルにレコードを 1 件追加したところ，インデックスとして使う，図の B⁺木のリーフノード C がノード C1 と C2 に分割された。ノ

問題本文

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

選択肢

• ア.（選択肢アの B⁺木構造図）
• イ.（選択肢イの B⁺木構造図）
• ウ.（選択肢ウの B⁺木構造図）
• エ.（選択肢エの B⁺木構造図）

正解

イ. （選択肢イの B⁺木構造図）

解説

B⁺木は、データ(キー)をすべて最下層のリーフノードに格納し、リーフ同士を順序どおりに横方向のポインタで連結する構造をもつ。リーフCが満杯になってC1とC2に分割されると、(1)親である中間ノードAは分割後の両方のリーフを指す必要があるため、AからはB・C1・C2・Dの4つすべてへポインタが張られ(Aには空きがあるので分割は親に波及しない)、(2)リーフ間の連結はキーの昇順を保ったまま B⇔C1⇔C2⇔D とつなぎ直される。この両方を満たすのがイであり、正解。

選択肢ごとの解説

• ア.リーフの連結順は正しいが、中間ノードAからC2へのポインタが張られておらず、分割後のリーフ全てを親が指すというB⁺木の条件を満たさないため誤り。
• イ.中間ノードAがB・C1・C2・Dの全リーフを指し、リーフ連結も B⇔C1⇔C2⇔D と昇順で正しくつなぎ直されており、正しい。
• ウ.リーフの並びが B・C1・D・C2 となっておりキーの昇順が崩れている。分割で生じたC2はC1の隣に入るべきで、誤り。
• エ.C2をC1の子のようにぶら下げており、全データを同一レベルのリーフに置きリーフを横に連結するB⁺木の構造に反するため誤り。