B⁺木のリーフノードの分割
出典: 平成30年度 春期 応用情報技術者試験 午前 問26 (IPA)
関係データベースのテーブルにレコードを 1 件追加したところ，インデックスとして使う，図の B⁺木のリーフノード C がノード C1 と C2 に分割された。ノード分割後の B⁺木構造はどれか。ここで，矢印はノードへのポインタとする。また，中間ノード A には十分な空きがあるものとする。
- ア
- イ
- ウ
- エ
正解と解説を見る
正解: イ
- ア: 中間ノード A が C2 を指していません。分割でできたノードも A から指す必要があります。
- イ: 中間ノード A が B, C1, C2, D を指し、リーフも B ⇄ C1 ⇄ C2 ⇄ D の順につながっているので、正しい答えです。
- ウ: リーフの連結順が B, C1, D, C2 になっており、キーの順序と合いません。C2 は C1 と D の間にあるべきです。
- エ: C2 が C1 の下にぶら下がっており、中間ノード A から指されていません。B⁺木のリーフは同じ階層に並びます。
ポイント
B⁺木 の特徴は次のとおりです。
- データはリーフノードに置き、リーフ同士は ポインタで順番につながって います。
- リーフが分割されると、中間ノードに新しいリーフへのポインタが追加 されます。
- 元のリーフ C が C1 と C2 に分かれたので、中間ノード A は B, C1, C2, D の 4 つを指し、リーフの連結も B ⇄ C1 ⇄ C2 ⇄ D の順になります。