3

B+ ツリーを実装する必要があります。

そして、次のメソッドを作成する必要があります。

  1. 挿入 (x) - 0 (log_t(x))。
  2. 検索 - 検索成功 - O(log_t(x))。検索の失敗 - O(1) {可能性が高いフード}

そこで、Insert(x) の実装から始めました。葉がいっぱいになるたびに、それを 2 つの別々の葉に分割したいと考えています。中央値キー以下のキーを持つ 1 つのリーフには、中央値よりも高い値を持つキーが含まれます。

実行時間を損なうことなく、この中央値を見つけるにはどうすればよいですか?

私は考えました：

  1. 内部ノードと葉のそれぞれをより小さな B+ ツリーとして表しますが、中央値は、ツリーが完全にバランスが取れている場合にのみルート (またはルート内の要素の 1 つ) になります。
  2. 内部ノードと葉のそれぞれを二重にリンクされたリストとして表します。入力が挿入されている間に中央値キーを取得しようとしていますが、それで動作しない入力があります。
  3. 配列として表すと中間になるかもしれませんが、それを分割すると、キーを新しい配列に挿入するには少なくとも O(n/2) が必要です。

私に何ができる？

検索については、アイデア的には、成功した検索と失敗した検索の違いは、葉の検索に関するものですが、キーがツリーにあるかどうかを判断するために、ツリーのさまざまなキーを「実行」する必要があります。では、どうすれば O(1) になるのでしょうか?

4

3 に答える 3

4

B+ ツリーでは、すべての値がリーフに格納されます。

各リーフから次のリーフへのポインターを追加できることに注意してください。標準の B+ ツリーに加えて、すべての要素を含む順序付けられたリンク リストが取得されます。

ここで、このリンクされたリストの現在の中央値が何であるかを知っていると仮定すると、挿入/削除時に新しい中央値を安価に計算できることに注意してください(同じノード、次のノード、または前のノードであり、他の選択肢はありません)。
このポインターO(1)の変更は (挿入/削除自体はO(logn).

その知識があれば、中央値要素へのポインタをキャッシュし、削除/挿入時にそれを維持することができます。中央値を要求するときは、キャッシュから中央値を取得するだけO(1)です。

に関して-これはブルームフィルターUnsuccessful search - O(1) {With a high likely-hood}を叫びます。これは、偽陰性を持たない確率的なセットの実装です（セット中に何かがセットされていないとは決して言いません）が、いくつかの偽陽性があります（実際にはキャッシュにあるのに何かがキャッシュにあると言います） 't)。

于 2013-05-11T16:40:45.470 に答える
2

B+ ツリーの中央値は必要ありません。分割するノードに中央値キーが必要です。各ノードにN/2 <= n <= Nキーがあるという条件を満たすには、その中央値で分割する必要があります。ノード内の中央値キーは、ちょうど真ん中のn/2にあるキーです。ここで、nはノード内の実際のキーの数です。ここでノードを分割します。O(1) であるコンピューティング: ランタイムに悪影響を与えることはありません。

別のデータ構造を重ね合わせることなく、B+ ツリーから O(1) 検索失敗時間を取得することはできません。

于 2013-05-12T00:45:51.247 に答える