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

正解

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

正答率 56.2%（1,021人中 574人が正解）

問題の解説

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⁺木の構造に反するため誤り。