B + Treeの挿入 - 理論的な質問

Question

私はB + Treeがどのように動作しているかを知り、その例を解決しようとしています。 4.

として与えられている - そのような文書で

は、ノードごとに検索キー値の「N」数がB +ツリー構造を記述するページ8上に与えられた実施例1において、here上場しましたすべては3番目のステップまでのルールに従いますが、突然4番目のステップでは、ルートノードが分割され、他の分割が表示されます。私はなぜノード17,19,21が分割されているのか理解しています（これは明らかに本文には表示されていません）。しかし、私は根が分割されている理由に驚いています。誰かがこれを私に明確にしたり、より独特で段階的なアプローチで、かなり複雑な良い例を提案することができます。

Answer 1

これは、Bツリーが動作する方法です。リーフノードがいっぱいになり、オーバーフローすると分割され、1つのkeyvalueが送信されます。上記のノードは、根まですべて分割することもできます。

この例は少し弱いですが、通常、ルート以外のすべてのノードは少なくとも半分いっぱいです。しかし、3の半分は1なので、これはあまり明らかではありません。