平成30年度春期 プロジェクトマネージャ 午前Ⅰ 問8

分割後の構造を追う視点

ノード分割の前後で、全体の配置や参照関係がどのように変わるかを、処理の順序に沿って整理しながら確認しましょう。

この問題で問われていること

一つのノードだけでなく、分割を起点として周囲の要素との関係がどう再構成されるかに注目し、変化の範囲を丁寧に追いましょう。

視点

局所的な変更と、それに伴って周辺へ波及する構造上の変化を分けて考え、各段階で何が維持され何が更新されるかを整理します。

確認ポイント

• 分割の直前と直後で、対象となる要素の数や位置関係を比較する
• 変更が対象部分だけで完結するか、周囲の関係にも及ぶかを確認する
• 処理の各段階で、全体のつながりがどのように保たれているかを追う

正解

イ

解説

B⁺木のリーフノードCをC1とC2に分割すると、親ノードAにはB、C1、C2、Dへのポインタが必要になる。また、リーフの順序を保つため、B、C1、C2、Dの間の双方向連結も維持される。したがって正しい構造はイです。

理由

Cはリーフノードなので、分割後のC1とC2はいずれも親ノードAから参照される必要がある。Aには十分な空きがあるため、親ノード自体の分割は起こらず、子ポインタはB、C1、C2、Dの順に並ぶ。

比較

B⁺木のリーフノードは、検索結果を順番にたどれるよう隣接リーフ同士を連結する。元のB、C、Dの連結関係を分割後も保つと、B、C1、C2、Dが順に連結されるため、この条件を満たすイが適切です。

選択肢ア

これは不正解だよ。CをC1とC2に分割した後は、親ノードAからC1とC2の両方を参照できなければならない。この構造ではAからC2へのポインタが適切に追加されておらず、C2を木の子ノードとして直接たどれないため、B⁺木の分割後の構造として不適切である。

選択肢イ（正解）

これは正解だよ。リーフノードCの分割後、親ノードAはB、C1、C2、Dの全てを順序どおりに参照する。また、リーフノードもB、C1、C2、Dの順に連結されている。Aには十分な空きがあるため親の分割も発生せず、分割後の条件を正しく満たしている。

選択肢ウ

これは不正解だよ。リーフノードの並びがB、C1、D、C2となっており、Cを分割して得られたC1とC2が隣接していない。B⁺木のリーフは検索キーの順序に従って連結されるため、分割前のCが占めていた位置にC1、C2を順に配置する必要がある。

選択肢エ

これは不正解だよ。C1の下にC2を配置しており、C2が通常のリーフ列の一部としてB、C1、C2、Dの順に連結されていない。また、リーフ分割によって生じた二つのノードを、親Aの子として同じ階層で参照するという条件にも合わない。

学習のポイント

B⁺木のリーフ分割では、親ポインタとリーフ連結の両方を確認する。