b-tree - ノードが分割されると、B ツリー ノードのキーは複製されますか?

Question

B ツリーのノードが分割されると、元のノードのキーが新しいノードに複製されますか? これを行う目的は何ですか？これって非効率じゃないですか？

Answer 1

いいえ、それはすべてポインターで行われます。ポインターの半分が新しいノードに移動されます。

もちろん、「B ツリー」などというものはありません。無数の異なる実装があります。キーが int であるツリーなど、キーが実際にノードに格納されているものを想像できます。ただし、それらは「複製」されず、データがコピーされるだけです。

あなたのビーフが分割されるノードに残されたストレージである場合、それは、解放してより小さく再割り当てするかどうかの別の最適化の選択肢です. そのノードのキー空間の 1/2 に入る追加の挿入が到着する可能性があるため、おそらくそうではありません。

Answer 2

あなたはB +ツリーを意味していると思います。

私が書いた B+ ツリーでは、分割中に親ノードのキー値を複製しました。親の key[pos] は、左側のノードの最低値に設定され、左側のノードを指していました。右側のノードの最低値は、親の key[pos+1] になりました。