0

表の例:

CREATE TABLE adj_list_model (
    id INT NOT NULL AUTO INCREMENT,
    parent_id INT,
    my_string varchar(255),//some random information
    PRIMARY KEY (id)
)

私が作成しているツリーには、同じテーブルに複数の「ルート」ユーザーが含まれます (parent_id = NULL の場合)。これらの「ルート」ユーザーは、ある時点で「リーフ」ユーザー (配下に誰もいないユーザー) から parent_id を取得する場合があります。私が持っている疑問は、次のような「ループ」を作成しないようにする方法です。

ツリー設計の例:

  • a
    • b
    • c
      • d
        • e
        • へ
          • g

ユーザー「a」がユーザー「g」を親として取得した場合、作成されるループは次のようになります。

a -> c -> d -> f -> g -> a -> c... and so on forever

質問:ユーザー「a」がツリー内のユーザー「g」の下に移動したいときに、ユーザー「g」がユーザー「a」の下にあるかどうかを確認する良い方法は何ですか? （これらの特定のケースでアクションを防ぐことができるように）

考慮すべき重要なポイント: 2 つのツリーが 1 つにマージされることは、非常に頻繁に発生します。ツリーのレベル数が仮想的に 80 の場合、ループを防ぐためのチェックにかなりの時間がかかる可能性があるため、効率的な方法を探しています。

編集済み： 私が持っていた現在のオプションは（私は懐疑的ですが）次のとおりです。

  1. テーブル内の各ユーザーの現在の「ルート」ユーザーを示す追加の列を作成します。そのような場合、「ルート」ユーザーが親を取得するたびに、その下にいるすべてのユーザーが新しい「ルート」ユーザーで更新される必要があり、私が心配しているのは、これがサーバーにどれほどの負担をかけるかということです。多くのユーザーと、「ルート」ユーザーが親を取得する頻度が高い場合。

  2. 彼に親を与える前に、「ルート」ユーザーのパスを確認します。上記のケースで、ユーザー「g」が、g を超える各ユーザーを 1 つずつループしてパスをチェックし (ルートに到達するまで、親が何であるかを何度も確認します)、ルートがユーザー「a」であることがわかった場合。 、はい、アクションを防ぐことができますが、これがサーバーにどれほど負担をかけるかはわかりません. 誰かがアイデアを持っているなら、私に知らせてください！

4

1 に答える 1

1

追加のroot_id列を含むオプションの場合、MySql 構文:

CREATE PROCEDURE change_root() 
BEGIN

  # this is the leaf node id, which will be the new parent of a root user
  SET @new_parent = x;
  # this is the old root user id, which will be the new child of the former leaf node
  SET @old_root = y;
  # get the leaf's root
  SET @new_root = SELECT root_id FROM adj_list_model WHERE id=x;

  # updating the dataset is possible as long as the leaf is not a child of the root user
  IF @new_root <> y THEN

    # link the former leaf to its new child
    UPDATE adj_list_model SET parent_id=x WHERE id=y;

    # @old_root is no longer a root, so update all occurences to the new root
    UPDATE adj_list_model SET root_id=@new_root WHERE root_id=@old_root;

  END IF;

END;

これは実際にはそれほど複雑ではなく、再帰的なソリューションよりもはるかに高速です。ただし、最終的には、ワークロードとニーズによって異なります。

于 2016-04-19T21:23:30.250 に答える