平成30年度 高度共通 午前I（PM試験） 問8

正解：イ

AI解説

B+木では、リーフノードが満杯になって分割されると、分割後の2つのノード(C1,C2)の区切りとなるキーが親の中間ノードに追加され、親からC1とC2の両方へポインタが張られる。また、B+木のリーフは順次アクセスのために隣接リーフ同士がリンクされ、全ての要素は左から昇順に並ぶ。この2条件を満たす図が正解となる。 ア: 分割後のC1・C2の一方しか親から指されていない、又はキーの昇順が崩れている構造であり、B+木の性質を満たさない。 イ: 正解。親ノードAに分割キーが追加され、AからC1とC2の双方へポインタが張られた正しいB+木構造である。 ウ: C1からC2へ中間ノードを介さず縦にぶら下がるなど、木の高さのバランス(全リーフが同じ深さ)が崩れた構造であり誤り。 エ: 分割キーが親に昇格していない、又はポインタの張り方がB木・二分木的な構造であり、B+木のノード分割規則に反する。 💡 B+木の挿入は「リーフ分割→中央キーを親へコピーして昇格→親から両ノードを指す」が基本動作。全リーフの深さが等しく、キーが左から昇順という不変条件で図を検証すると速い。