B +ツリーを挿入する場合、なぜツリーを下に移動してから上に戻って親を分割するのでしょうか。
ウィキペディアは、この挿入方法を提案しています。
検索を実行して、新しいレコードをどのバケットに入れるかを決定します。
- バケットがいっぱいでない場合（挿入後、最大でb-1エントリ）、レコードを追加します。
- それ以外の場合は、バケットを分割します。
- 新しいリーフを割り当て、バケットの要素の半分を新しいバケットに移動します。
- 新しいリーフの最小のキーとアドレスを親に挿入します。
- 親がいっぱいの場合は、それも分割します。
- 親ノードに真ん中のキーを追加します。
- 分割する必要のない親が見つかるまで繰り返します。
ルートが分割された場合は、1つのキーと2つのポインターを持つ新しいルートを作成します。
なぜ、ツリーを下に移動してから、分割を実行して上に戻るのですか？途中でノードに遭遇したら、ノードを分割してみませんか？
私にとって、提案された方法は2倍の作業を実行し、より多くの簿記も必要とします。
途中で分割するのではなく、これが挿入に適した方法である理由と、トラバーサル中に挿入することの欠点を説明できる人はいますか？