私はthis siteからBツリーを学んでいます。サイトにあるように、Bツリーにデータを挿入するトピックでは、このデータを使用してバイナリツリーを構築しました：5 9 3 7 1 2 8 6 0 4。アップステップ9まで私は挿入プロセスを理解することができますが、ステップ10ではなぜ通常の方法で4を挿入できませんか？Bツリーを形成するためのアルゴリズムにはまっていますが、正確なアルゴリズムは何ですか？
それは、さらに挿入を確認する必要があります。だから、どのようにして、さらなる挿入が完全に機能するかを保証する。これのための正確なアルゴリズムは何ですか？
ステップ10の説明では、「3で4をスティックするのは良いことですが、Bツリーアルゴリズムではフルルートを分割する必要があります。これはもちろんナンセンスです。
Bツリーアルゴリズムではこのようなことは必要ありませんが、ページの作成者が使用するような単純化されたアルゴリズムでは、不必要な分割やマージを実行して完全な部分実装Bツリーアルゴリズム。
特に、下位レベルのノードが分割されている場合、ツリー内で分割が上位になる可能性があります。これは、分割ごとにセパレータキーが上に移動するためです。極端な場合には、分割ノード上のすべての数字がレベルまで分割することもできます（ルートを含む）。
これを効率的に処理することは、ロックに影響し、ルートから挿入/分割が発生するノードへの最初の降下中に取られたパスを覚えておく必要があります。
これは、通常、コールスタックを上向きに歩くことができないため、単純な再帰関数呼び出しが機能しなくなることを意味します。また、ルートから挿入対象ノードまでの全経路は、（単純な実装の場合）同時の状況、または少なくともターゲットノードに分割される可能性の最も低い親からのサブパスにロックする必要があることを意味します。
シンプルなコップアウトは、ツリー内のさらに下への変更が確実に行われるように、追加の再構成を実行することで機能します。は、をバブルアップできません。これらの再構築は、Bツリーの観点からは不要ですが、単純化された戦略の完全性のために必要です。
の埋め込み opの降下中に、途中で発生したすべてのノードが分割される必要があります。 opを削除する場合、少なくとも1つのキーを提供できないすべてのノードをマージする必要があります。そして、はい、これは挿入と削除の特定のシーケンスが、Bツリー・スキーム（構造管理コストの償却）の主な利点を無効にし、それぞれの操作ごとにツリーの重い不必要な再構築を引き起こす可能性があることを意味します。