問26応用情報技術者 平成30年度 春期

解説

正解は2。B⁺木では、すべてのデータがリーフノードにあり、リーフどうしはキーの順に横のポインタでつながっている。リーフCがC1とC2に分かれると、リーフの並びはB⇔C1⇔C2⇔Dとなり、親の中間ノードAにはC2を指すポインタ（とその境目のキー）が1つ追加される。Aには空きがあるので分割は上へ伝わらず、木の高さも変わらない。2の図がこの形である。

• 1は、リーフの順はよいが、中間ノードAからC2へのポインタがない。これではC2のデータを根からたどれない。
• 3は、リーフの順がB、C1、D、C2となっており、キーの順に並ぶというB⁺木の性質に反する。
• 4は、C2がC1の下にぶら下がっており、すべてのリーフが同じ深さにあるというB⁺木の性質に反する。

根拠：B⁺木の構造（リーフの連結リストと、ノード分割時の親ノードへのキー・ポインタの追加）。