[解決済み] フラットテーブルをツリーにパースする最も効率的/エレガントな方法は何ですか?
質問
順序付きツリー階層を格納するフラットテーブルがあるとする。
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 クロージャテーブル階層型データベース - 正しい順序で情報を引き出す方法 .
関連
-
[解決済み] ストアドプロシージャ 'dbo.aspnet_CheckSchemaVersion' が見つかりませんでした。
-
[解決済み] SQL Serverで実行中の合計を計算する
-
[解決済み] MySQLの「スキーマの作成」と「データベースの作成」 - 違いはあるのか?
-
[解決済み] テーブルネーミングのジレンマ:単数形と複数形の名前【非公開
-
[解決済み] JOINとINNER JOINの違いについて
-
[解決済み] PostgreSQLからのPL/pgSQL出力をCSVファイルに保存する
-
[解決済み] SQL Serverでテーブルからカラム名を取得するにはどうすればよいですか?
-
[解決済み] SQLite - UPSERT *not* INSERT or REPLACE
-
[解決済み] 木の深さと高さはどう違うのですか?
-
[解決済み] javascriptでフラット配列からツリー配列を構築する
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
MySQL - ストアドプロシージャ (データ型、関数)
-
[解決済み] MySQLの「スキーマの作成」と「データベースの作成」 - 違いはあるのか?
-
[解決済み] データベースのインデックス作成はどのように行われるのですか?[クローズド]
-
[解決済み] 複数の列でgroup byを使用する
-
[解決済み] JOINとINNER JOINの違いについて
-
[解決済み] INNER JOINよりもCROSS APPLYを使用すべきなのはどのような場合ですか?
-
[解決済み] SQL SELECT WHERE フィールドに単語が含まれる場合
-
[解決済み] SQL ServerにおけるINSERT OR UPDATEに関する解決策
-
[解決済み] SQL Server の CASE ステートメントで OR がサポートされていない。
-
[解決済み] SQLサーバーで行を列に効率的に変換する