B*木のノード分割

B*木(B-star tree)は、B+木においてノードの利用効率を高めるために、ノードが満杯になった際に直ちに分割せず、隣接する兄弟ノードへキーを再配分(シフト)する方式です。両方の兄弟ノードが満杯になった場合にのみ、2つのノードを3つのノード(2/3分割)に分割します。本問ではリーフノードCへの追加により、中間ノードAには十分な空きがある状態で、リーフノードCがC1とC2に2分割されています。分割後のB*木では、C1とC2が中間ノードAの子ポインタにそれぞれ追加され、かつリーフノード同士はシーケンシャルアクセスのための双方向(または単方向)チェーンで結ばれます。図イでは、中間ノードAからノードB、C1、C2への3本のポインタが正しく張り直され、リーフ層でB → C1 → C2の連結関係が保たれています。 中間ノードAからのポインタがC1しか指しておらず、C2がリーフチェーンから中間ノードの検索経路に組み込まれていません。 C2がC1の子ノードのように配置されており、平衡木(バランス木)の深さ(高さ)が崩れてしまっています。 中間ノードAが不用意に分割されており、中間ノードAに十分な空きがあるという前提条件に反しています。

関係データベースのテーブルにレコードを1件追加したところ,インデックスとして使う,B*木のリーフノードCがノードC1とC2に分割された。ノード分割後のB*木構造はどれか。ここで,矢印はノードへのポインタとする。また,中間ノードAには十分な空きがあるものとする。

q3-figure-1
出典令和6年度 秋期 データベーススペシャリスト試験 午前Ⅱ 問3
ア
選択肢アの画像
イ
選択肢イの画像
ウ
選択肢ウの画像
エ
選択肢エの画像