[解決済み] フラットテーブルをツリーにパースする最も効率的/エレガントな方法は何ですか？

質問

順序付きツリー階層を格納するフラットテーブルがあるとする。

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

以下はその図です。 [id] Name . ルートノード0は架空のものです。

                       [0] ルート
                          / \ 
              [1] ノード1 [3] ノード2
              / \ \
    [2] ノード1.1 [6] ノード1.2 [5] ノード2.1
                    
          
 [4] ノード1.1.1

それを正しく並べられ、正しくインデントされたツリーとしてHTML（あるいはテキスト）に出力するには、どのような最小限の方法をとればよいでしょうか。

さらに、基本的なデータ構造（配列とハッシュマップ）しかなく、親/子参照を持つ派手なオブジェクトも、ORMもフレームワークもなく、あなたの両手だけだと仮定します。テーブルは結果セットとして表現され、ランダムにアクセスすることができます。

疑似コードでも平易な英語でも構いません、これは純粋に発想の問題です。

ボーナス質問です。このようなツリー構造をRDBMSに格納する根本的な良い方法はありますか？

編集・追加

あるコメントへの回答( マーク・ベッシー の）質問です。ルート・ノードは必要ありません。なぜなら、どうせ表示されることはないからです。ParentId = 0 は、quot;これらはトップレベルです" を表現するための規約です。Orderカラムは、同じ親を持つノードがどのようにソートされるかを定義します。

私が話したquot;結果セット"は、ハッシュマップの配列として描くことができます（この用語にとどまるために）。私の例では、すでにそこにあることを意味しました。いくつかの回答は、最初にそれを構築するために余分なマイルを行く、しかし、それは大丈夫です。

ツリーは任意の深さにすることができます。各ノードはN個の子供を持つことができます。しかし、私は何百万ものエントリーを持つツリーを考えていたわけではありません。

私が選んだノードの名前（「ノード1.1.1」）を、何か信頼できるものだと勘違いしないでください。ノードは「Frank」でも「Bob」でも同じように呼ぶことができ、命名構造を暗示するものではなく、単に読みやすくするためのものです。

私は自分自身の解決策を投稿したので、あなた方はそれをバラバラに引っ張ることができます。

どのように解決するのですか？

現在 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つの方法を使用しています。

• 隣接関係リスト ("parent"カラム)と
• パス列挙 (名前欄の点線付き数字)。

もう一つの解決策は ネストされたセット これも同じテーブルに格納することができます。 Read " SQLでツリーと階層を作る for Smarties これらの設計に関する詳しい情報はJoe Celkoによる "をご覧ください。

私は通常、次のようなデザインを好みます。 クロージャーテーブル (別名:隣接関係)を使って、木構造のデータを保存します。 これは別のテーブルを必要とするが、ツリーのクエリーは非常に簡単である。

クロージャーテーブルについては、私のプレゼンテーションで紹介しています。 SQLとPHPによる階層的データのモデル化 および拙著 SQLアンチパターン。データベースプログラミングの落とし穴を回避する .

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)
);

あるノードから別のノードに直接先祖返りしているすべてのパスをクロージャテーブルに格納する。 各ノードが自分自身を参照するための行を含めます。 例えば、あなたが質問で示したデータセットを使用します。

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_length が1である。

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 | 
+----+

Re comment from @ashraf: "ツリー全体を[名前順]にソートするのはどうでしょうか？

以下は、ノード1の子孫であるすべてのノードを返すクエリの例です。 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 クロージャテーブル階層型データベース - 正しい順序で情報を引き出す方法 .