🏨 📥 🎅🏼 階層データ構造とDoctrine 👨🏽‍🤝‍👨🏼 👨🏿‍🌾 🛐

はじめに

リレーショナル構造での階層データ（または単純なツリー）の保存はかなり重要なタスクであり、開発者が同様のタスクに直面したときにいくつかの問題を引き起こします。

まず、これはリレーショナルデータベースが階層構造（XMLファイルなど）の格納に適合していないという事実によるものであり、リレーショナルテーブルの構造は単純なリストです。ただし、階層データには親子関係があり、これはリレーショナル構造に実装されていません。

それでも、「データベースにツリーを保存する」というタスクは、遅かれ早かれ開発者の前で発生します。

以下では、リレーショナルデータベースでツリーのストレージを整理する際にどのようなアプローチが存在するかを詳細に調べ、ORM Doctrineがそのような構造を扱うために提供するツールについても検討します。

隣接リスト

構造説明

原則として、このようなデータ構造には、ツリーの隣接する頂点に関する情報の格納が含まれます。頂点頂点（1,2,3）を持つ最も単純なグラフを考えてみましょう：

3頂点グラフ

図 1. 3つの頂点を持つグラフ

ご覧のとおり、このグラフの各要素には、他の要素との通信に関する情報が保存されています。

  1-2,3
 2-1,3
 3-1,2

実際、このようなグラフはツリーを構築するために冗長です。なぜなら、通常の分岐構造の場合、親と子の関係のみを保存する必要があります。

  2-1
 3-1

次に、1つのルート要素（1）と2つのブランチ（2,3）を持つツリーを取得します。

ツリーグラフ

図 2.木の伯爵

原則として、必要に応じて、隣接する頂点のリストを使用して一方のグラフと他方のグラフをデータベースに表示できますが、ツリーに関心があるため、それらについて詳しく説明します。

したがって、隣接リストメソッドを使用してデータベースに階層構造を格納するには、データテーブルに相続人と親の関係に関する情報を格納する必要があります。実際のツリーの例を見てみましょう：

隣接リスト

図 3.隣接頂点法によるツリー構造

図では、木のノードは四角で示されています。各ノードには、名前（正方形内の上部の長方形）、識別子（左下の正方形）、および親識別子（右下の正方形）へのリンクがあります。図からわかるように 3、そのような構造の各相続人は彼の祖先を指します。データベースに関しては、次のように表形式で表示できます。

図 4.隣接頂点リスト法によって構築されたツリーデータテーブル

または、SQLの形式で：

  CREATE TABLE al_tree（
     `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY、
     `parent_id` BIGINT NULL、
     `name` VARCHAR（50）NOT NULL
 ）TYPE = InnoDB DEFAULT CHARSET = utf8;

 CREATE INDEX fk_tree_tree ON al_tree（parent_id）;

 ALTER TABLE al_tree制約の追加fk_tree_tree
    外部キー（parent_id）参照al_tree（id）更新カスケード時、削除カスケード時。

 al_treeの値に挿入
     （1、NULL、「FOOD」）、
     （2、1、「野菜」）、
     （3、2、「ポテト」）、
     （4、2、「TOMATO」）、
     （5、1、「フルーツ」）、
     （6、5、「APPLE」）、
     （7、5、「バナナ」）;

ツリーを保存するためのそのようなアルゴリズムには、特定の利点と欠点があることにすぐ注意してください。まず第一に、それは非常に読みにくいです-そして、これはその主な欠点です。

ツリー全体を読み取る場合、データベースからの読み取りに関する問題はそれほど目立ちません。これはかなり単純なリクエストです：

  SELECT * FROM al_tree ORDER BY id;

結果：

  + ---- + ----------- + ----------- +
 |  id |  parent_id | 名前|
 + ---- + ----------- + ----------- +
 |  1 |  NULL | 食品|
 |  2 |  1 | 野菜|
 |  3 |  2 | ポテト|
 |  4 |  2 | トマト|
 |  5 |  1 | フルーツ|
 |  6 |  5 | アップル|
 |  7 |  5 | バナナ|
 + ---- + ----------- + ----------- +

ただし、将来的には、このような選択は、かなり容量の大きいソフトウェアによるデータの後処理を意味します。最初に、先祖と後継者の関係を考慮してデータを再帰的に再構築する必要があります。その後、それを使用してどこかに出力することができます。

ツリー全体を読み取る別のオプション：

  t1.name AS lvl1、t2.name as lvl2、t3.name as lvl3を選択します
 FROM al_tree AS t1
 LE_JOIN al_tree AS t2 ON t2.parent_id = t1.id
 LEFT JOIN al_tree AS t3 ON t3.parent_id = t2.id
 LEFT JOIN al_tree AS t4 ON t4.parent_id = t3.id
 WHERE t1.id = 1;

この場合の結果は次のようになります。

  + ------ + ----------- + -------- +
 |  lvl1 |  lvl2 |  lvl3 |
 + ------ + ----------- + -------- +
 | 食品| 野菜| ポテト|
 | 食品| 野菜| トマト|
 | 食品| フルーツ| アップル|
 | 食品| フルーツ| バナナ|
 + ------ + ----------- + -------- +

この形式のデータはすでにすぐに出力に適合していますが、ご覧のとおり、このアプローチの主な欠点は、階層内のネストレベルの数を確実に知る必要があることです。さらに、階層が大きくなるほど、JOINが多くなり、パフォーマンスが低下します。

ただし、この方法には大きな利点もあります。ツリーの変更、ツリー内のノードの交換および削除は簡単です。

結論-このアルゴリズムは、しばしば変更しやすい小さなツリー構造で操作する場合に適しています。

一方、このアルゴリズムは、「私は親を知っています-すべての相続人を読んでください」という形式の部分でそれらを読んだ場合、大きな木にもかなり自信を持っています。これの良い例は、動的にロードされるツリーです。この場合、アルゴリズムは実際にこの動作に最適化されています。

ただし、ツリーの他の部分を読み取り、回るときにパス、前および次のノードを見つけ、ツリーの枝全体を（完全な深さまで）読み取る必要がある場合には、あまり適していません。

Doctrineで連続する頂点のリストを使用する

最初に、Doctrineでテーブルテンプレートを整理することについて、いくつかの紹介的な言葉を作りたいと思います。教義でこの概念にすでに精通している人は、いくつかのパラグラフをより興味深いものにジャンプするかもしれません。

したがって、ORM Doctrineで操作するエンティティはActive Recordsです。つまりビジネスロジックを結合し、データベース自体と対話できるオブジェクト。しかし、Doctrineの開発者は、継承だけでなく、これらのオブジェクトに「動作パターン」を適用することにより、レコードオブジェクトの機能を拡張することを想定していました。これはDoctrine / Templateパッケージによって実装されます。

したがって、動作の前にアクティブレコードを表示する必要がある場合（たとえば、Versionable-すべての変更を監査する、I18N-多言語、またはNestedSet-「ネストセット」タイプのツリービュー）、これらのテンプレートを使用してこれを行うことができます動作。

既存のテンプレートのいずれかに接続するには、モデルを適切に構成するだけで十分です（YAML経由で、またはベースモデルテーブルのコードで直接）。

時間が来たら、それを行う方法を例で示します。

これまでのところ、残念ながら、または幸いなことに、テーブル用のテンプレートの形式では、Doctrineで隣接する頂点をリストする方法は実装されていません。必要に応じて、実装を自分で記述し、Doctrine開発者に提供することもできます-これはあなたの裁量です。

ただし、このモデルのフレームワーク内で実装できる主な機能は、動作パターンを使用せずにDoctrineで実装できます。残念ながら、ツリーを操作する機能は得られませんが、主な問題は解決できます。

これを行うには、モデルを適切に構成する必要があります。 YAMLを使用して、テーブルの構造を記述します。

 アルツリー：
   tableName：al_tree
  列：
     id：
      タイプ：整数（8）
      プライマリ：true
      自動インクリメント：true
    名前：
      タイプ：文字列（50）
       notnull：true
     parent_id：整数（8）

そして今、最も重要なことは、テーブル内の関係を正しく記述することです。次の行から書きます：

 関係：
    親：
      クラス：AlTree
      ローカル：parent_id
      外部：id
      タイプ：1
    子供：
      クラス：AlTree
      ローカル：id
      外部：parent_id
      タイプ：多く

次のコマンドを実行して、モデルを組み立てましょう。

  ./doctrine generate-models-yaml

それだけですモデルの準備ができました。実際、既製のBaseAlTree基本クラスでも同じことができます。

  <？php
 ...
  パブリック関数setUp（）
   {
     $ this-> hasOne（ 'AlTree as Parent'、array（ 'local' => 'parent_id'、
                                             'foreign' => 'id'））;

     $ this-> hasMany（ 'AlTree as Children'、array（ 'local' => 'id'、
                                                'foreign' => 'parent_id'））;;
   }
 ...
 ？>

今、私たちの仕事の結果を楽しむ時です。再帰を使用して通常のHTMLページにインデントで構築されたツリーを表示する簡単なコードを書きましょう。

 <？  / ** *ツリーのルート要素を抽出します* / $ root = Doctrine :: getTable（ 'AlTree'）-> findByDql（ 'WHERE parent_id IS NULL'）-> getFirst（）;  echo '<pre>';  printRTree（$ root）;  echo '</ pre>';  / ** *ツリーを再帰的に画面に出力します* * @param AlTree $ node-recording object-tree node * @param int $ level-転送されたノードのネストレベル* / function printRTree（AlTree $ node、$ level = 0）{/ * * *この行はツリーを「描画」します* / echo str_repeat（ "\ t"、$ level）。  $ node-> getName（）。  「\ n」;  / ** *次に、相続人がいるかどうかを確認し、そうであれば、再帰を入力します。  *注意してください-これは奇跡のプロパティです*モデルの設定で説明した*子供たち！  * / if（（$ children = $ node-> Children-> getIterator（））&& $ children-> count（）> 0）{$ level ++;  while（（$ child = $ children-> current（）））{/ ** *再帰を入力* / printRTree（$ child、$ level）;  $ children-> next（）;  }}}？>

モデルオブジェクトの接続を適切に構成した後、 ChildrenおよびParentプロパティが使用可能になったことに注意してください。ただし、それらへの最初の読み取りアクセスは、データベースへのクエリを生成します。したがって、単一のパスで大きなツリーを構築するには、このアプローチは非常にコストがかかります。

しかし同時に、動的にロードされたツリーをこの方法で実装するのは楽しいことです！

入れ子セット

構造説明

おそらく、すべてのWeb開発者がこのアルゴリズムとその速度について聞いたことがあるでしょう。はい、多くの階層データを頻繁に読み取る必要がある場合、このアルゴリズムは非常に優れています。このアプローチの本質を考慮してください。

ネストされたセットに基づいてツリーを構築する場合、図に矢印で示すように、このツリーを左から右にトラバースする原理を使用します。 5.これを行うには、ツリーの各ノードに対して、左（lft）と右（rgt）（ノード内の下部のボックス）に整数キーを定義します。そして、トラバース中に整数の増分値を与えます。何が起こったか見てください。

入れ子セット

図 5.ネストセット。

ルート要素は、他のすべてのキーの番号の範囲を含むキー1と14を受け取りました。 VEGETABLEブランチはキー2と7を受け取りました。これらのキーには、すべての相続人のキー番号の全範囲が含まれます。ここでは、ネストされたセットです。簡単ですね。

データベーステーブルのコンテキストで同じ構造を再作成しましょう。

ネストされたセットツリーテーブル

図 6.ネストされたセットメソッドに基づく階層データテーブル

または、SQLの形式で：

  CREATE TABLE ns_tree（
     `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY、
     `name` VARCHAR（50）NOT NULL、
     `lft` BIGINT NOT NULL、
     `rgt` BIGINT NOT NULL、
     `level` BIGINT NOT NULL
 ）TYPE = InnoDB DEFAULT CHARSET = utf8;

 CREATE INDEX nslrl_idx ON ns_tree（lft、rgt、level）;

 ns_treeの値に挿入
     （1、 'FOOD'、1、14、0）、
     （2、「野菜」、2、7、1）、
     （3、「ポテト」、3、4、2）、
     （4、「TOMATO」、5、6、2）、
     （5、「フルーツ」、8、13、1）、
     （6、「APPLE」、9、10、2）、
     （7、「バナナ」、11、12、2）;

ご覧のとおり、テーブルに別のフィールド-レベルを追加入力しました。各ツリーブランチのネストレベルに関する情報を保存します。原則として、これはまったく必要ありません-ネストレベルは非常に簡単に計算できますが、このアルゴリズムは読み取り専用に最適化されているので、レベル情報をキャッシュしてパフォーマンスを向上させてみませんか？修辞的な質問...

データベースからツリーを読み取る

ツリー全体を読みます。

  SELECT node.id、node.name、node.level
 FROM ns_tree ASノード、
 ns_tree AS親
 WHERE node.lft BETWEEN parent.lft AND parent.rgt
 AND parent.id = 1
 ORDER BY node.lft;

結果は次のようになります。

  + ---- + ----------- + ------- +
 |  id | 名前| レベル|
 + ---- + ----------- + ------- +
 |  1 | 食品|  0 |
 |  2 | 野菜|  1 |
 |  3 | ポテト|  2 |
 |  4 | トマト|  2 |
 |  5 | フルーツ|  1 |
 |  6 | アップル|  2 |
 |  7 | バナナ|  2 |
 + ---- + ----------- + ------- +

理論的には、ネストのレベルをオンザフライで計算することで同じ結果を得ることができます。

  SELECT node.id、node.name、（COUNT（parent.id）-1）ASレベル
 FROM ns_tree ASノード、
 ns_tree AS親
 WHERE node.lft BETWEEN parent.lft AND parent.rgt
 GROUP BY node.name
 ORDER BY node.lft;

自分で結果を比較してみてください-最初の結果と同じになります。この場合、リクエスト自体のみがよりリソースを消費します。また、ネストされたセットは最適な読み取りアルゴリズムであるため、残りのデータの隣にあるネストレベルのキャッシュという小さな最適化は、それほど悪い戦略ではありません。

同じ、かなり単純な方法で、ブランチ全体、ツリーからのパス、ノードのバイパスなどを読み取ることができます。

たとえば、この例からすべての野菜（VEGETABLE）を抽出する場合、これは非常に簡単です。

  SELECT node.id、node.name、node.level
 FROM ns_tree ASノード、ns_tree AS親
 WHERE node.lft BETWEEN parent.lft AND parent.rgt AND parent.id = 2
 ORDER BY node.lft;

さらに、結果から親を除外する必要がある場合は、いくつかの方法を実行できます。

HAVINGレベルの追加> 1
WHEREに追加：AND node.id！= 2条件

または別の方法で-それは読者のための創造的なタスクにしましょう。

はい、外部関連データとの集約を含む、高速で柔軟な読み取りがこのアルゴリズムのハイライトです。

それにもかかわらず、銀の裏地はありません。この場合、ネストされたセットツリーに変更を加えるか、そのブランチを削除する必要があるときに、大きな困難が始まります。

これは、まず、変更がある場合、変更するノードの右側にあるツリーのその部分のすべてのキーを再カウントする必要があるだけでなく、ネストレベルに関する情報を更新する必要があるためです。そして、これらすべてを1つの簡単なリクエストで行うことはできません。

自分で見てください。

新しいブランチを追加する

VEGETABLESおよびFRUITと同じレベルで、SEA FOODという名前の新しいブランチをツリーに追加するとします。

  BEGIN;

 SELECT @treeRight：= rgt FROM ns_tree
 WHERE id = 2;  / * id = 2のVEGETABLESブランチの右側* /

更新ns_tree SET rgt = rgt + 2 WHERE rgt> @treeRight;
 UPDATE ns_tree SET lft = lft + 2 WHERE lft> @treeRight;

 ns_treeの値に挿入（0、 'SEA FOOD'、@treeRight + 1、@treeRight + 2、1）;

 COMMIT;

MySQL、またはトランザクションをサポートしないバージョンでMYISAMテーブルを使用する場合、BEGINおよびCOMMITの代わりに書き込みロックを使用できます。

  LOCK TABLE ns_tree WRITE;
 ...
テーブルのロック解除。

ご覧のとおり、新しいブランチを追加するタスクは非常にコストがかかり、簡単ではありません。ただし、解決可能。

ブランチを削除

新しく作成したブランチを削除してみましょう。

  BEGIN;

 SELECT @treeLeft：= lft、@ treeRight：= rgt、@ treeWidth：= rgt-lft + 1
 ns_treeから
 WHERE id = 8;  / *「SEA FOOD」という名前の新しいレコードの識別子です* /

 ns_tree WHERE lft BETWEEN @treeLeft AND @treeRightから削除します。
 / *
  注意！
  注意してください-私たちはIDで削除しません、
  この場合、それは私たちに合っています。
  しかし、一般的には、ブランチ全体とその内容を削除する必要があります！
 * /

 ns_tree SET rgt = rgt-@treeWidth WHERE rgt> @treeRightを更新;
 ns_tree SET lft = lft-@treeWidth WHERE lft> @treeRight;

 COMMIT;

結論-ネストされたセットは、データベースからツリーの構造を読み取る必要がある場合に非常に適しています。さらに、あらゆるサイズのツリーに等しく適しています。

ただし、頻繁に変更される階層構造では、明らかに最適な選択ではありません。

Doctrineでネストされたセットを使用する

しかし、このメソッドはモデルにバインドできる動作パターンの実装としてDoctrineに反映されます。

これを行うには、基本クラスコードのYAML構成またはpramoを介してモデルを構成することにより、非常に簡単です。

YAML：

  NsTree：
   tableName：ns_tree
   actAs：[NestedSet]
  列：
     id：
      タイプ：整数（8）
      プライマリ：true
      自動インクリメント：true
    名前：
      タイプ：文字列（50）
       notnull：true
     lft：
      タイプ：整数（8）
       notnull：true
     rgt：
      タイプ：整数（8）
       notnull：true
    レベル：
      タイプ：整数（8）
       notnull：true

ご覧のとおり、クラスの説明でactAs：[NestedSet]を指定するだけで十分です。

ただし、DoctrineはNestedSetモデルに対してより柔軟な設定を提供します。たとえば、1つのテーブルに複数のツリーを保存できます。これを行うには、各レコードのツリールートの識別子を格納するテーブルに追加フィールドを入力する必要があります。

この場合、構成は次のように記述する必要があります。

  NsTree：
   tableName：ns_tree
   actAs： 
     NestedSet：
       hasManyRoots：true
       rootColumnName：root_id
  列：
     id：
      タイプ：整数（8）
      プライマリ：true
      自動インクリメント：true
     root_id：
      タイプ：整数（8）
       notnull：true
    名前：
      タイプ：文字列（50）
       notnull：true
     lft：
      タイプ：整数（8）
       notnull：true
     rgt：
      タイプ：整数（8）
       notnull：true
    レベル：
      タイプ：整数（8）
       notnull：true

モデルの既存の基本クラスでも同じことができます。

最初の場合：

  <？php
 ...
    パブリック関数setTableDefinition（）
     {
         ...
         $ this-> actAs（ 'NestedSet'）;
        ...
     }
 ...
 ？>

または：

  <？php
 ...
    パブリック関数setTableDefinition（）
     {
         ...
         $ this-> actAs（ 'Doctrine_Template_NestedSet'）;
        ...
     }
 ...
 ？>

2番目の場合（複数のツリー）：

  <？php
 ...
    パブリック関数setTableDefinition（）
     {
         ...
         $ options = array（ 'hasManyRoots' => true、
                          'rootColumnName' => 'root_id'）;
         $ this-> actAs（ 'NestedSet'、$ options）;
        ...
     }
 ...
 ？>

Doctrineはデフォルトのフィールド名として「root_id」を使用することに注意してください。したがって、実際のテーブルの名前と一致する場合、このオプションを指定する必要はありません。それ以外の場合は、尋ねることができます。

Doctrineのネストされたセットツリーの例

画面上のツリー全体を抽出して印刷します。

  <？php
 $ tree = Doctrine :: getTable（ 'NsTree'）-> getTree（）-> fetchTree（）;
 echo "<pre>";
 foreach（$ノードとしての$ツリー）{
     echo str_repeat（ "\ t"、$ node ['level']）。  $ノード['name']。  「\ n」;
 }
 echo "</ pre>";
 ？>

それがいかに簡単かを見てください！

追加の例と情報については、Doctrineの公式ドキュメントのセクション8.2.4および8.2.5を参照できます。

マテリアライズドパス

構造説明

階層構造を格納するためのもう1つのかなり興味深いアプローチ。アルゴリズムの主なアイデアは、ツリーの最上部からノードへのフルパスを保存することです。次のようになります。

実体化されたパス

図 7.「マテリアライズドパス」の原則に基づいて編成されたツリー構造

このようなパスを形成する原理は非常に簡単です。パスの深さは、ツリーのレベルです。ブランチ内では、番号付けは増分です。言い換えると、野菜は食品の最初の子、果物は次の子などです。

テーブルの形でこれを見る方が簡単です：

  + --------------- + ------- +
 | 名前| パス|
 + --------------- + ------- +
 | 食品|  1 |
 | 野菜|  1.1 |
 | ポテト|  1.1.1 |
 | トマト|  1.1.2 |
 | フルーツ|  1.2 |
 | アップル|  1.2.1 |
 | バナナ|  1.2.2 |
 + --------------- + ------- +

おそらくこれはさらに明白です。

データベースでは、これはすべて以下に反映されます。

マテリアライズドパステーブルの構造

図 8.「マテリアライズドパス」の原則に基づいて編成された階層データのテーブル構造

または、SQLの形式で：

  CREATE TABLE mp_tree（
     `id` BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY、
     `name` VARCHAR（50）NOT NULL、
     `path` VARCHAR（100）NOT NULL
 ）TYPE = InnoDB DEFAULT CHARSET = utf8;

 CREATE INDEX mpp_idx ON mp_tree（ `path`）;

 mp_tree値への挿入
     （1、 'FOOD'、 '1'）、
     （2、「野菜」、「1.1」）、
     （3、「ポテト」、「1.1.1」）、
     （4、「TOMATO」、「1.1.2」）、
     （5、「フルーツ」、「1.2」）、
     （6、「APPLE」、「1.2.1」）、
     （7、「バナナ」、「1.2.2」）;

このアプローチの利点は何ですか？

第一に、ネストされたセットと比較して、変更しやすくなっています。同時に、ツリー全体とその部分を選択するのに十分便利です。しかし、彼は完璧ではありません。特にブランチの先祖の検索に関して。

ノードへのパスを見つける：

  mp_tree t1、mp_tree t2からt1.nameを選択します
 CONCATのようなWHERE t2.path（t1.path、 '。％'）
 AND t2.id = 3;  / *「POTATO」という名前のノードへのパスを検索します* /

結果：

  + ----------- +
 | 名前|
 + ----------- +
 | 食品|
 | 野菜|
 + ----------- +

ネストのレベルの計算。

この問題を解決するには、原則として、パス内のポイント（またはポイントを使用しない場合は他のセパレーター）の数をカウントするだけで十分です。残念ながら、MySQLには適切な機能はありませんが、独自に非常に簡単に実装できます。

  CREATE FUNCTION STRFIND（str VARCHAR（255）、delimtr CHAR（1））RETURNS INT
開始
 DECLARE _cnt INT;
 DECLARE _start INT;
 SET _cnt = -1;
 SET _start = 1;
 _start> 0 DO中
   SET _start = LOCATE（delimtr、str）;
   SET str = SUBSTRING（str、_start + 1）;
   SET _cnt = _cnt + 1;
終了中;
 RETURN _cnt;
終了

ブランチの選択：

  SELECT名、strfind（パス、「。」）ASレベル 
 mp_treeから 
 WHEREパスLIKE '1.1％';  / *ブランチ「野菜」全体を選択* /;

結果：

  + ----------- + ------- +
 | 名前| レベル|
 + ----------- + ------- +
 | 野菜|  1 |
 | ポテト|  2 |
 | トマト|  2 |
 + ----------- + ------- +

この例では、自己記述関数を使用したため、非常に便利でした。

親検索：

  t2を選択* 
 FROM mp_tree t1、mp_tree t2 
 WHERE t1.id = 3 AND t2.path = SUBSTRING（t1.path、1、（LENGTH（t1.path）-LOCATE（ '。'、REVERSE（t1.path）））;

ご覧のとおり、これらのクエリはすべて（前の方法と比較して）最大のパフォーマンスを発揮しませんが、それでも、この特定のアルゴリズムを使用すると、読み取り操作と変更操作の両方が頻繁に実行されるツリーにとって著しく便利になります。

著者が知る限り、アルゴリズムはかなり大量のデータに対してかなり自信があると感じています。

このアルゴリズムで最も不快なのは、ノードを既存の構造の中央に（他のノード間で）挿入する操作です。これは、基になるノードのすべてのパスの変更を伴います。公平に言えば、このような操作はどのデータストレージモデルにとっても取るに足らないものであると言えます。別の難しい操作は、1つのブランチを別のブランチに転送することです。

しかし、削除、最後への追加、またはノードの変更は非常に簡単な操作であり、原則として、このモデルで問題を引き起こすことはありません。

例からわかるように、このアルゴリズムは、隣接する頂点のリスト（入れ子集合）で行われたように、別のレベルフィールドを導入することで、読み取り用にわずかに最適化することもできます。ただし、これにより、ツリーノードの追加、変更、削除の操作が多少複雑になります。変更のたびに、ツリーのすべてまたは一部のレベルを再集計する必要があります。最終的には、パフォーマンスバイアスをどのように決定するかは開発者次第です。

Doctrineでの使用

残念ながら、現時点では、このツリーの保存方法はDoctrine ORMでの実装をまだ発見していません（執筆時点での現在のバージョンは1.0.4、1.1.0です-アルファ版でも実装されていません）。

それにもかかわらず、その実装が将来登場すると信じるすべての前提条件があります。ライブラリのソースコードには、Doctrine / TreeパッケージのMaterializedPathという抽象空クラスが含まれています。

作成者はイベントをフォローし、実装が反映されるとすぐにこの記事を更新するため、後でここに戻ることができます。

複合アプローチ

実際のところ、上記の方法は2つの方向でのみ組み合わせることができることに注意してください。

隣接リスト+マテリアライズドパス
隣接リスト+ネストされたセット

ネストされたセットとマテリアライズドパスを組み合わせてもあまり意味がありません。あなたは読み書きのいずれにおいても実質的な利益を得ることはありません。

実際、データベースレベルでのアプローチの組み合わせは、隣接リストとマテリアライズドパスのテーブルに親レコードへのリンクを格納するフィールドの入力に限定されます。

データ構造の表AL + MPおよびAL + NS

図 9.階層データ構造AL + MPおよびAL + NSのモデルの表

このアプローチの意味は明らかです。

AL + MP

MPで使用されるALの場合：

ブランチとサブツリー全体を選択するための操作を改善する
ブランチ転送操作が悪化している

ALで使用されるMPの場合：

特定のノードの親選択操作の改善
特定のノードの相続人を選択するための操作の改善

AL + NS

AL + NSの場合、相互の利点はそれほど明白ではありません。これは主に、NSモデルでツリーノードを変更する問題の欠点が、この分野のALのすべての利点を完全に無効にしているという事実によるものです。つまり、このような束は、NSアルゴリズムの特定のノードの親と相続人の検索における質的な改善と、アルゴリズム自体の信頼性の向上としてのみ考慮されるべきであることを意味します（破損の場合、キーは常に再構築できます-ALはリンクに関する情報を保存します）。信頼性の向上の主張は、以前の方法の組み合わせに対して有効です。しかし、これは定性的な改善ですが、それほど明白ではありませんが、そうですか？

おわりに

この記事では、リレーショナルデータベースに階層データを格納するためのいくつかの基本的な方法を検討し、それらのすべての利点と欠点を概説しました。また、実際にはDoctrine ORM実装で使用できるものとそれらの使用方法を示しました。

明らかに、特定のケースごとに特定の方法を選択することもそれほど簡単ではありませんが、著者は、この資料が意識的で正しい決定の採用に貢献し、新しいより最適なソリューションを見つける創造的なプロセスに貢献することを願っています。

開発に頑張ってください！

_{PSこれは私のブログのオリジナル記事のクロスポストです。}

階層データ構造とDoctrine

はじめに

隣接リスト

構造説明

Doctrineで連続する頂点のリストを使用する

入れ子セット

構造説明

Doctrineでネストされたセットを使用する

マテリアライズドパス

構造説明

Doctrineでの使用

複合アプローチ

おわりに

More articles: