B＋木の挿入について

Question

↑の初期状態のB＋木に[23 B]と[31 C]を挿入↓

その後、[24 D]と[25 E]を挿入↓

その後、[29 F]を挿入↓

という問題があって、
①上記のように解いたのですがあっておりますでしょうか？
学校の教材やインターネットでB＋木について調べても正誤判定が自分ではできないです。
また、②２番目の画像の中間ノードには31の隣に34を入れたほうがよろしいでしょうか？
③最後の画像の右側の中間ノードに34を入れたうえで根ノードには右側に34を入れるべきでしょうか？
ご回答ご回答宜しくお願い致します。

Answer 1

結論から言いますと、正しくないようです。

参考：B+Tree Insertions

B+木は、索引部とデータ部が分かれているデータ構造で、データは末端ノードで管理されます。初期状態の図が課題の図だとすると、四角で表されているのがノードで、丸四角で表されているのがデータと思います。ここで、末端ノードと索引ノードの区別が必要と思います。

今回は、同じ構造を末端ノードと索引ノードとして使用しているようです。この四角の構造を見てみると、インデクス値を格納できる場所が2つ、ポインタを格納できる場所が3つの構造になっています。この構造の使われ方は、末端ノードと索引ノードで違っています。

末端ノードとして使うときは左から順に

• 未使用、または1つ目のデータへのポインタ
• 1つ目のデータのインデクス値
• 未使用、または2つ目のデータへのポインタ
• 2つ目のデータのインデクス値
• 未使用、または次の末端ノードへのポインタ

索引ノードとして使うときは左から順に

• 未使用、または1つ目の子ノードのインデクス値よりも小さい子ノードへのポインタ
• 1つ目の子ノードの最小インデクス値
• 未使用、または1つ目の子ノードへのポインタ
• 2つ目の子ノードの最小インデクス値
• 未使用、または2つ目の子ノードへのポインタ

おそらく、回答は以下のような形だろうと思います。たたし、分割時のロジックはいろいろ流派があるようです。ここではYouTubeの例のようにシンブルに1/2に分け、二つ目ノードのインデクス値で親ノードを作る方法にしました。
初期状態

[34,]

[23 B]を挿入（部屋が空いてるのでそのまま格納）

[23, 34]

[31 C]を挿入（オーバーしたので分割し、親ノードを生成）

   [31,]
[23,][31, 34]

[24 D]を挿入（部屋が空いてるのでそのまま格納）

    [31,]
[23,24][31, 34]

[25 E]を挿入（オーバーしたので分割し、親ノードにインデクス追加）

     [24,31]
[23,][24, 25][31, 34]

[29 F]を挿入（配置換えによるインデクス更新）

       [25,31]
[23,24][25, 29][31, 34]

Comments

[hositaka]

難しいですね。ご回答ありがとうございました。