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

正解：イ

AI解説

B+木では，リーフノードが満杯になって分割されると，分割後の2つのノード(C1,C2)を親ノードから参照できるように，分割位置のキー値を親(中間ノードA)に追加し，AからC1とC2の両方へのポインタを張る。本問ではAに十分な空きがあるため，Aの分割は起こらず，Aの子が1つ増えるだけの構造(イ)になる。 ア: 誤り。分割後の一方のノードだけが親から参照される構造は，もう一方のノードに親からたどり着けなくなるため不適切である。 イ: 正解。中間ノードAに分割キーが追加され，AからC1とC2の両方にポインタが張られた構造であり，B+木のノード分割の結果として正しい。 ウ: 誤り。C1の子としてC2をぶら下げるなど木の高さが部分的に変わる構造は，全リーフの深さが等しいというB+木(平衡木)の性質に反する。 エ: 誤り。親ノードを経由しない不正なポインタ構成であり，キー値による探索経路が成立しない。 💡 B+木は「全てのリーフが同じ深さ」「データはリーフに置き，中間ノードは探索用のキーとポインタのみ」が原則。リーフ分割時は分割キーを親にコピーして子ポインタを1本増やす，親も満杯なら親も分割して再帰的に上へ伝播する，と覚える。