B +ツリーでのバルク削除

Question

B +ツリーから単一の要素を削除するのは問題ありません。 しかし、少なくともO（nlogn）時間よりも少ない時間にツリーの要素の大部分を削除する方法があるかどうかを知りたかったのです。

ツリーのバルク要素がリンクリストで連続していると同時に削除することはできますか？

Answer 1

一般に、場合によっては、はい。

非常に特にあなたが時間O(n)に設定データをソートからサイズnのB +ツリーを構築することができます。さらに、大量のデータセットを使用すると、ストリーミング操作を使ってディスクをソートすることができます。さらに、ランダムなシークをたくさん行うことができます。

結果は、大量のバルクロードに関する古いデータベースのアドバイスです。 "インデックスを削除する、データをロードする、インデックスを再構築する"または、削除するデータがソートされている場合は、必要なデータのソートされたリストを作成し、そこから新しいB +ツリーを構築することができます。

この変形は、古いデータがしばらく削除されたときに記録するB +ツリーを持つことです。その後、ツリーを歩き、削除されたものをすばやくマークすることで、一括削除を実行できます。そして時には全体を歩いてすべてを書き直すことによって時折木を圧縮するだけです。

一般に、データ構造を一度に1つずつ操作することをお勧めします。私が冗談を言っているように、のlog（n）は定数です。 Googleの場合は少し大きめの定数です。