フラットテーブルをツリーに解析する最も効率的でエレガントな方法は何ですか? 質問する

Question

今MySQL 8.0は再帰クエリをサポート、こう言える。一般的なSQLデータベースはすべて再帰クエリをサポートしています標準構文では。

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

プレゼンテーションでMySQL 8.0の再帰クエリをテストしました再帰クエリのスローダウン2017年。

以下は 2008 年の私の最初の回答です。

リレーショナルデータベースにツリー構造データを保存する方法はいくつかあります。例で示しているのは、次の 2 つの方法です。

隣接リスト（「親」列）と
パス列挙(名前の列のドット付き数字)。

もう 1 つのソリューションはNested Setsと呼ばれ、同じテーブルに保存することもできます。「賢い人のためのSQLのツリーと階層これらのデザインの詳細については、Joe Celko の「」を参照してください。

私は通常、ツリー構造のデータを格納するために、クロージャテーブル(別名「隣接関係」)と呼ばれる設計を好みます。別のテーブルが必要になりますが、ツリーのクエリは非常に簡単になります。

私のプレゼンテーションではクロージャテーブルについて説明しますSQL と PHP を使用した階層データのモデルそして私の本ではSQL アンチパターン第 1 巻: データベースプログラミングの落とし穴を回避する。

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

1 つのノードから別のノードへの直接の祖先が存在するすべてのパスをクロージャテーブルに保存します。各ノードが自身を参照するための行を含めます。たとえば、質問で示したデータセットを使用すると、次のようになります。

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

これで、次のようにノード 1 から始まるツリーを取得できます。

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

出力（MySQL クライアント内）は次のようになります。

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

つまり、ノード 3 と 5 は、ノード 1 の下位ではなく別の階層の一部であるため除外されます。

Re: e-satis からのコメント (直接の子または直接の親について)。直接の子または親 (またはその他の距離) を具体的に照会しやすくするために、「 path_length」列を追加できます。ClosureTable

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

次に、特定のノードの直下の子を照会するための用語を検索に追加できます。これらは、path_length1 である子孫です。

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

@ashraf からのコメント: 「ツリー全体を [名前で] 並べ替えるのはどうでしょうか?」

以下は、ノード 1 の子孫であるすべてのノードを返し、それらをなどの他のノード属性を含む FlatTable に結合し、name名前で並べ替えるクエリの例です。

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

@Nate からのコメントについて:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

今日、あるユーザーが編集を提案しました。SO モデレーターは編集を承認しましたが、私はそれを元に戻します。

編集では、上記の最後のクエリの ORDER BY はにすべきであると示唆されていますORDER BY b.path_length, f.name。これは、順序が階層と一致するようにするためと思われます。しかし、これは機能しません。「Node 1.1.1」が「Node 1.2」の後に順序付けられるからです。

順序を階層構造に合致させたい場合、それは可能ですが、パスの長さで単純に順序付けるだけではだめです。例えば、私の回答を参照してください。MySQL クロージャテーブル階層データベース - 正しい順序で情報を引き出す方法。

Answer 1