9

フラットなテーブル (SQL など) 内にツリーを格納するための修正された事前注文ツリー トラバーサルアルゴリズムについて考えてきました。

標準的なアプローチで私が気に入らない点の 1 つは、ノードを挿入するには、(平均して) N/2 のノード (挿入ポイントより左または右が高いすべて) に触れなければならないことです。

私が見た実装は、順番に番号が付けられた値に依存しています。これにより、更新の余地がなくなります。

これは、並行性とスケーリングにとって悪いようです。大規模なシステムのすべてのアカウントのユーザー グループを含む世界に根ざしたツリーがあるとします。これは非常に大きく、ツリーのサブセットを別のサーバーに保存する必要があります。ツリーの一番下にノードを追加するために、すべてのノードの半分に触れるのは良くありません。

そこで考えた案がこちら。基本的に、キースペースを分割し、各レベルで分割することにより、挿入の余地を残します。

N max = 64の例を次に示します (これは通常、DB の MAX_INT になります)

                     0:64
              ________|________
             /                 \
         1:31                   32:63
        /    \                 /     \
    2:14    15-30         33:47       48:62

ここでは、ツリーの左半分にノードが追加されます。

                     0:64  
              ________|________
             /                 \
         1:31                  32:63
      /   |   \               /     \
  2:11  11:20  21:30     33:47       48:62

サブツリーの左/右のインデックスに再帰的に番号を付け直すには、挿入および削除プロセスのアルゴリズムを拡張する必要があります。ノードの直下の子のクエリは複雑なので、親 ID もテーブルに格納するのが理にかなっていると思います。次に、アルゴリズムはサブツリーを選択し (left > p.left && right < p.right を使用)、node.id と node.parent を使用してリストを処理し、インデックスを分割します。

これは、単にすべてのインデックスをインクリメントして挿入用のスペースを作る (または削除用にデクリメントする) よりも複雑ですが、はるかに少ないノード (挿入/削除されたノードの親の子孫のみ) に影響を与える可能性があります。

私の質問は基本的に次のとおりです。

  1. このアイデアは形式化または実装されていますか?

  2. これはネストされた間隔と同じですか?

4

3 に答える 3

5

同じ理由で、以前にこれを行っている人の話を聞いたことがあります。

これを行うと、アルゴリズムのいくつかの小さな利点が失われることに注意してください。

  • 通常、ノードの子孫の数は ((right - left + 1) div 2) でわかります。これは、ツリービューにカウントを表示する場合などに役立つ場合があります。これには、ツリーのさらに下にある子の数が含まれている必要があります。
  • 上記から、すべてのリーフ ノードを簡単に選択できます -- WHERE (右 = 左 + 1)。

これらはかなりマイナーな利点であり、いずれにせよ役に立たないかもしれませんが、使用パターンによっては明らかに便利です。

とはいえ、上記で提案したように、具体化されたパスの方が便利なように思えます。

于 2009-06-28T21:01:00.743 に答える
1

テーブルを 2 つに分割できます。1 つ目は (ノード ID、ノード値)、2 つ目 (ノード ID、子 ID) はツリーのすべてのエッジを格納します。挿入と削除は O(tree depth) になります (要素に移動し、その下にあるものを修正する必要があります)。

あなたが提案するソリューションはB-tree のように見えます。ツリー内のノードの総数を見積もることができる場合は、事前にツリーの深さを選択できます。

于 2009-06-26T15:53:50.610 に答える