データベーススペシャリスト 2024年 午前2 問03

B+木リーフ分割【午前2解説】

正解の理由

解法ステップ

1. B+木の性質を確認：リーフは同一レベルにあり、隣接リーフ間は双方向の兄弟ポインタでつながれている。
2. リーフ分割の結果：元のリーフCはC1とC2に分かれる。分割後は両者とも同じレベルに存在する。
3. 親ノード処理：親Aに空きがあるなら、分割で生じた新しいリーフ(C2)へのポインタをAに挿入し、子ポインタの並びはキー順に並べる。
4. 正しい構成と図を照合：Aのポインタ数が増え、リーフの双方向リンクが整合している選択肢を選ぶ（これが イ）。

選択肢別の誤答解説

• ア：誤り。図示されたアでは親Aから出ているポインタが B、C1、C2 の3つしかない一方、葉レベルには B, C1, C2, D の4つのノードが存在します。つまりAがDを指していないため、子ポインタ数が不足しておりB+木の整合性を満たしません。葉の双方向リンクだけ整っていても、親が全ての葉を指していない構成は不正です。
• イ：正しい。AはB, C1, C2, Dの順で子ポインタを持ち、葉は B ⇔ C1 ⇔ C2 ⇔ D の双方向リンクで接続されています。Aに空きがある条件とも整合します。
• ウ：誤り。Aの子ポインタ順が B, C1, D, C2 となっており、葉順序と親のポインタ順が一致していません。B+木では内部ノードのポインタは葉の順序と一致させる必要があり、キー順を乱すこの配置は不正です。
• エ：誤り。C2がC1の下（下位の子）として描かれており、葉ノードが同一レベルにない構成になっています。B+木ではすべての葉が同一レベルであり、分割後の新しいリーフは親の隣接ポインタとして扱われるため、縦接続は誤りです。また親AはC2を直接指していないためポインタ不整合も発生します。

よくある誤解

• 親ノードは「古いCを指すポインタを更新すればよいだけ」と考える誤り：新しいリーフができたら親に新しい子ポインタを追加（または再配置）する必要があり、単に片方を上書きするだけでは子ポインタ数が合わなくなる場合がある。
• リーフのつながり（兄弟ポインタ）と親の子ポインタを混同する誤解：葉の双方向リンクは範囲検索のためのもので、親のポインタ並びはキー順序に一致していなければならない。両者は別の仕組みで保持される。
• 分割後の新しいノードを「親の子ではなく子の子にする」誤り：リーフ分割で生成されるノードは同じレベルのリーフであり、親の直接の子になる。

補足コラム

• 分割時のキー昇格：リーフを分割すると、通常は右側ノードの最小キーを親に挿入して区切りにします。内部ノードは区切りキーのみを保持し、データ本体はリーフに残ります。
• 内部ノードのポインタ数とキー数の関係：内部ノードが持つキー数を $k$ とすると、ポインタ数は $k+1$ です。分割により葉が1つ増えれば親のポインタ数も1増えます。
• 親が満杯だった場合：親に空きがないときは親自体を分割し、分割で上位ノードへキーを昇格させる処理が再帰的に発生します。最終的に根が分割されると木の高さが1増えます。

FAQ