データベーススペシャリスト試験 令和6年度 秋期 午前II 問3

【正解】イ

B⁺木では、実データ又は実データへのポインタをもつリーフノードが同じ階層に並び、キーの順序に従って相互に連結されます。分割前の図では、AがリーフノードB、C、Dを指し、リーフはB、C、Dの順に双方向で連結されています。CがC1とC2に分割された後は、C1とC2を隣接させ、リーフの順序をB、C1、C2、Dとする必要があります。また、親Aには空きがあるので、C2を指すポインタと境界となるキーをAに追加でき、A自体を分割する必要はありません。これらを満たす構造はイです。

アの構造は誤りです。リーフの並びはB、C1、C2、Dですが、AからC2へのポインタがありません。リーフ分割時には、新しくできたリーフを指すエントリを親ノードにも追加します。

ウの構造は誤りです。C2がDの後ろに配置され、リーフがB、C1、D、C2の順になっています。Cから分割されたC1とC2はキー範囲が連続するため、元のCの位置で隣接し、その後ろにDが続きます。

エの構造は誤りです。C2がC1の下位ノードのように配置されており、リーフの階層がそろっていません。B⁺木は全てのリーフが同じ深さにある平衡木です。

【ポイント】 リーフ分割では、キーを二つのリーフへ分配し、新しい右側リーフへのポインタを親に追加します。 リーフ同士の連結順序も更新するため、範囲検索をキー順に継続できます。 親に空きがなければ親の分割が連鎖しますが、本問ではAに空きがあるので連鎖しません。