データベースにツリーを保存する方法の概要
要するに：
- AL-親がparent_id型の列に格納されている場合： '' 1 ''
- MP-要素へのフルパスは、パスタイプの列に保存されます： '' 1.2.5 ''
- NS [ 2、3 ] -すべてのネストされた要素の範囲を格納するlftおよびrgt列のペア。たとえば、9要素のツリーのルートには、左値 '' 1 ''と右値 '' 18 ''があります。
詳細については、同志を参照してください ミクス [ 1 ] 。 同志が示すように、別のクロージャテーブルメソッドもあります。 復活ですが、これまでのトレンドには記録しません。
MySQLと再帰
MySQLの場合、再帰がありますが、ストアドプロシージャのレベルでのみ、さらに最大255レベルです。 一連のプログラミング言語+データベースで再帰を使用することもできますが、ここでのクエリの数は驚くべきものです。 データベース内のすべてを実行する方が適切です。
グーグルでは、任意の再帰的な問題があざなしで解決できることを学びます[ 4 ] 。 同様の質問をした後、試してみることができます...私たちは成功します！ 以下に、parent_idを認識してlftとrgtを埋めるrebuild_nested_set_tree関数を示します。
再帰なしのツリー塗りつぶし関数
簡単にするために、プレートにツリーが1つだけあり、8つの要素があることを想像してください。 関数は入力で何も受け取りません。 当然、製品版では、ツリーの特定のid頂点を受け取ります。これは、ロジックで考慮されます。 以下では、スペースを節約するために関数の本体のみを提供し、SQLFiddleで全文とクエリを確認します（このサービスを開いてくれたgrokruに感謝します）。
関数本体のソースrebuild_nested_set_tree
-- NULL UPDATE tree t SET lft = NULL, rgt = NULL; -- SET @i := 0; UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1) WHERE t.parent_id IS NULL; forever: LOOP -- -- SET @parent_id := NULL; SELECT t.id, t.rgt FROM tree t, tree tc WHERE t.id = tc.parent_id AND tc.lft IS NULL AND t.rgt IS NOT NULL ORDER BY t.rgt LIMIT 1 INTO @parent_id, @parent_right; -- , IF @parent_id IS NULL THEN LEAVE forever; END IF; -- SET @current_left := @parent_right; -- SELECT @current_left + COUNT(*) * 2 FROM tree WHERE parent_id = @parent_id INTO @parent_right; -- SET @current_length := @parent_right - @current_left; -- , UPDATE tree t SET rgt = rgt + @current_length WHERE rgt >= @current_left ORDER BY rgt; -- , UPDATE tree t SET lft = lft + @current_length WHERE lft > @current_left ORDER BY lft; -- SET @i := (@current_left - 1); UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1) WHERE parent_id = @parent_id ORDER BY id; END LOOP; -- RETURN (SELECT MAX(rgt) FROM tree t);
ここで何をしているの？
一般に、塗りつぶされた境界と塗りつぶされていない子を持つ左上の要素を見つけ、彼の子の数の長さを計算し、右側にある要素の境界を更新してから、彼の子の境界を更新します。 これらはすべて、境界のない要素がなくなるまで無限ループで再帰することなく行われます。
簡単なプレゼンテーションは、プロセスを視覚化するのに役立ちます。
参照資料
- 2008年12月10日、HabrのMikhusによる階層データ構造とDoctrine-各主要メソッドのデバイスについて詳しく説明
- 2000年10月20日、Intelligent EnterpriseのJoe CelkoによるSQLのツリー （英語）-隣接リストと比較したネストセットとは何か、2番目から1番目に変換する方法（Joe Celko-ネストセットの父）
- 階層データのデータベースへの保存 、Gijs Van Tulder、sitepoint.com、2003年4月30日（英語）-「左」インデックスと「右」インデックスの配布のロジックを説明するための写真、およびさまざまなアプローチでの作業の詳細の説明
- 再帰アルゴリズムは、反復アルゴリズムとして書き換えることができます...コミュニティwikiおよびKristopher Johnsonにより、stackoverflow.com、2009年12月11日（英語）-再帰アルゴリズムは、スタックを使用して反復アルゴリズムに変換できます。
- 2012年11月25日、sqlfiddle.comのgarexによる関数rebuild_nested_set_treeのソース -ツリーのあるテーブルの作成、テストデータの入力、移動用の関数の作成
- 再帰なしのネストされたセット： garexによる視覚化 、 slideshare.net 、2012年11月25日-いずれかのサイクルでのアルゴリズムの視覚化
変更履歴
- 別の方法についての言及を追加-クロージャテーブル
- 初期データでは、タイプミスが修正されています（「フラッシュ」は「ズボン」の下にある必要があります）
- minを含む倒錯は、関数の本体から削除され、制限1で適切な順序に置き換えられました（ただし、すべての適切な要素が移動したため、関数は正常に動作しました-後で驚きました）