58

答えはノーだと思いますが、SQL（MySQL）でツリー構造を任意の深さまでクロールする方法について誰かが洞察を持っていることを望んでいますが、単一のクエリで

より具体的には、ツリー構造のテーブル (id、data、data、parent_id)、およびテーブル内の 1 つの行が与えられた場合、すべての子孫 (子/孫/など)、またはすべての祖先 (親/祖父母)を取得することは可能ですか? /etc) 単一のクエリを使用して、どこまで下がるか上がるかを知らずに?

または、新しい結果がなくなるまで、より深いクエリを続ける、ある種の再帰が必要ですか?

具体的には、私は Ruby と Rails を使用していますが、それはあまり関連性がないと推測しています。

4

9 に答える 9

37

はい、これは可能です。ここで最もよく説明されているように、修正されたプレオーダー ツリー トラバーサルと呼ばれます。

Joe Celko の Trees and Hierarchies in SQL for Smarties

実際の例 (PHP) がここに提供されています

http://www.sitepoint.com/article/hierarchical-data-database/2/

于 2008-10-04T06:55:15.197 に答える
23

以下にいくつかのリソースを示します。

基本的に、ストアド プロシージャまたはクエリである種のカーソルを実行するか、隣接テーブルを作成する必要があります。db の外での再帰は避けたいと思います: ツリーの深さによっては、非常に遅くなったり大ざっぱになったりする可能性があります。

于 2008-10-04T05:55:05.803 に答える
3

Daniel Beardsley の答えは、主な質問が「私のすべての子供とは何か」と「私の両親とは何か」である場合、それほど悪い解決策ではありません。

アレックス・ワインスタインの回答によると、この方法は実際には、Celko 手法よりも親の動きのノードへの更新が少なくなります。Celko の手法では、左端のレベル 2 ノードが右端のレベル 1 ノードの下に移動した場合、ノードの子だけでなく、ツリー内のほぼすべてのノードを更新する必要があります。

ただし、ダニエルはルートに戻るパスを間違った方法で保存している可能性があります。

クエリが次のようになるようにそれらを保存します

SELECT FROM table WHERE ancestors LIKE "1,2,6%"

これは、mysql が 'ancestors' 列のインデックスを使用できることを意味しますが、先頭に % を使用することはできません。

于 2012-03-05T15:07:14.083 に答える
2

Celko の手法 (ネストされたセット) はかなり優れています。また、フィールド「祖先」、「子孫」、「距離」を持つ隣接テーブルを使用しました (たとえば、直接の子/親の距離は 1、孫/祖父母の距離は 2 など)。

これは維持する必要がありますが、挿入の場合はかなり簡単です。トランザクションを使用し、直接リンク (親、子、距離 = 1) をテーブルに配置し、距離を追加して既存の親と子の SELECTion を INSERT IGNORE (機会があれば SQL を引き出すことができます)。パフォーマンスのために 3 つのフィールドのそれぞれにインデックスが必要です。このアプローチが醜いのは削除の場合です...基本的に、影響を受けたすべてのアイテムをマークしてから再構築する必要があります。しかし、これの利点は、任意の非巡回グラフを処理できることです。一方、ネストされたセット モデルは直線的な階層しか処理できません (たとえば、ルートを除く各アイテムには 1 つの親しかありません)。

于 2008-12-08T19:43:21.063 に答える
2

私は以前にこの問題に遭遇し、1 つの奇抜なアイデアを思いつきました。直接の祖先の IDをルートまで連結した文字列である各レコードにフィールドを格納できます。

このようなレコードがあると想像してください (インデントは階層を意味し、数字は ID、祖先.

  • 1、「1」
    • 2、「2,1」
      • 5、「5,2,1」
      • 6、「6,2,1」
        • 7、「7,6,2,1」
        • 11、「11,6,2,1」
    • 3、「3,1」
      • 8、「8,3,1」
      • 9、「9,3,1」
      • 10、「10,3,1」

次に、 id:6 の子孫を選択するには、これを行うだけです

SELECT FROM table WHERE ancestors LIKE "%6,2,1"

祖先の列を最新の状態に保つことは、あなたにとって価値があるよりも面倒かもしれませんが、どの DB でも実現可能な解決策です。

于 2008-10-04T06:45:59.117 に答える
1

これは間違いなく実行でき、SQL の場合はそれほど複雑ではありません。私はこの質問に答え、mysql 手続き型コードを使用した実際の例をここに示しました。

MySQL: 特定のノードで葉を見つける方法

ブース: 満足している場合は、回答の 1 つを承認済みとしてマークする必要があります。

于 2012-10-09T21:09:47.027 に答える
1

https://stackoverflow.com/questions/27013093/recursive-query-emulation-in-mysql (https://stackoverflow.com/users/1726419/yossico が提供)で説明されている「With Emulator」ルーチンを使用しました。これまでのところ、(パフォーマンスに関して) 非常に良い結果が得られていますが、検索するための豊富なデータや多数の子孫がありません。

于 2015-01-12T21:15:50.800 に答える
1

SQL はチューリング完全言語ではないため、この種のループを実行することはできません。SQL とツリー構造を使っていくつかの非常に賢いことを行うことができますが、任意の深さの階層の「その階層内」で特定の ID を持つ行を記述する方法が思いつきません。

あなたの最善の策は、@Danが提案したことに沿ったものです。これは、他のより有能な言語でツリーをたどることです。ループを使用して、汎用言語で実際にクエリ文字列を生成できます。クエリは、探している階層の深さを反映する複雑な一連の結合 (またはサブクエリ) です。これは、ループや複数のクエリよりも効率的です。

于 2008-10-04T06:07:57.337 に答える
-1

ほとんどの場合、そのために再帰を使用したいと思うでしょう。そして、それを行っている場合、ツリーの一部ではなく、ツリー全体を固定の深さに取得する方が簡単です (実際には簡単です)。

非常に大まかな擬似コードでは、次の行に沿って何かが必要になります。

getChildren(parent){
    children = query(SELECT * FROM table WHERE parent_id = parent.id)
    return children
}

printTree(root){
    print root
    children = getChildren(root)
    for child in children {
        printTree(child)
    }
}

実際には、このようなことをしたいことはめったにありません。テーブル内のすべての行に対して 1 つのリクエストを行うため、かなり非効率的です。そのため、小さなテーブル、またはあまり深くネストされていないツリーに対してのみ有効です。正直に言うと、どちらの場合も深さを制限したいでしょう。

ただし、これらの種類のデータ構造の人気を考えると、特に作成する必要があるクエリの数を削減するために、これを支援する MySQL のものがいくつかある可能性があります。

編集:考えてみると、これらすべてのクエリを作成することはほとんど意味がありません。とにかくテーブル全体を読んでいる場合は、すべてをRAMに丸呑みすることができます-それが十分に小さいと仮定して!

于 2008-10-04T05:54:58.983 に答える