データベース内のツリーのストレージ。 パート1、理論

6か月前、 Laravel 3フレームワーク用のClosureTableバンドルを作成しました。 執筆の理由は、ビルカーウィンによる、 PHPを使用してMySQLに階層データを格納および処理する方法に関するこの素晴らしいプレゼンテーションでした。



だから。 階層構造を保存および処理するためのデータベース設計パターンがいくつかあります。

• 隣接リスト
• マテリアライズドパス
• 入れ子セット
• クロージャーテーブル

クロージャテーブルとは

この設計パターンの本質は、エンティティ間の関係が別のテーブルに格納され、メインテーブルにはエンティティ自体のデータのみが含まれることです。



リンクテーブルには、少なくとも2つのフィールドが含まれている必要があります。

• 祖先への参照（祖先）
• 子孫への参照

別のSuperPuper CMSの作成に取り組み、テキストページを編集するためのモジュールの開発を始めましょう。 2つのテーブルが必要です。

• pages
  
  
  
  にはページ情報が含まれます
• pages_treepath
  
  
  
  にはページ階層データが含まれます

データベーステーブルスキーマ



例として、次のページ階層を使用します。

子孫の選択

About Companyセクションのすべてのページを選択する場合、このようなSQLクエリを取得します。

 SELECT * FROM pages p JOIN pages_treepath t ON (p.id = t.descendant) WHERE t.ancestor = 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結果のブランチ。 矢印はページ間のリンクを示します。



「子孫」は「子孫」を意味し、「祖先」は祖先を意味します。 したがって、すべての子ページを取得するために、ページid



がdescendantへの子孫リンクと同じ意味を持つ場合、 pages_treepath



リンクテーブルをアタッチします。 この場合、親ページへのリンクのancestor



は1



で、ページ「会社について」の識別子です。

先祖サンプリング

そして、ボトムアップから：Corporateページですべての「親」を見てみましょう。

 SELECT * FROM pages p JOIN pages_treepath t ON (p.id = t.ancestor) WHERE t.descendant = 11
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合、反対。 階層の上位のページを探しているので、ページid



が祖先のancestor



へのリンクと等しくなる条件でリンクのテーブルをアタッチし、この例では11



に等しい子孫リンクで選択します。

新しいアイテムを挿入する

新しい空室を追加できます。 この場合、これらの値は表されていないため、リクエスト自体を見てみましょう。

 INSERT INTO pages VALUES (12, '  ', '', '    ', '0000-00-00 00:00:00', '0000-00-00 00:00:00') INSERT INTO pages_treepath (ancestor, descendant) SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4 UNION ALL SELECT 12, 12
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初の要求では、すべてが明確です-これは新しいデータの単純な挿入です。 ただし、2番目のリクエストは順番にソートする必要があるため、ここで何が起こるか見てみましょう。





新しい空席を挿入した後の要素間の関係

 SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このリクエストを完了すると、次のリンクのリストが取得されます。

 -------------------------
 | 先祖| 子孫|
 -------------------------
 |  4 |  12 |
 |  1 |  12 |
 -------------------------

以下を組み合わせて、前のクエリにもう1つ追加します。

 SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4 UNION ALL SELECT 12, 12
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それ自体へのページのリンクリンクは、リンクのリストに追加されます。

 -------------------------
 | 先祖| 子孫|
 -------------------------
 |  4 |  12 |
 |  1 |  12 |
 |  12 |  12 |
 -------------------------

ご覧のとおり、このSELECTクエリを使用すると、新しいページとそのすべての祖先の間にリンクを確立できます。 ancestor



は常にancestor



への参照であり、 descendant



は子孫への参照です。 最初に書き込まれたINSERTクエリは、結果をpages_treepath



テーブルに挿入します。

アイテムを削除

そして今、私たちはウェブデザイナーの欠員を閉じます。

 DELETE FROM pages_treepath WHERE descendant = 6 DELETE FROM pages WHERE id = 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここではすべてが簡単です。 まず、子孫へのリンクが6（Web Designerページ）であるすべてのリンクを削除してから、ページ自体を削除します。

ネストされたツリーを削除する

突然、ABCはしばらくの間、サイトの開発を停止しました。 対応するサブセクションを削除するには、このようなリクエストを実行する必要があります。

 DELETE FROM pages WHERE id IN ( SELECT descendant FROM ( SELECT descendant FROM pages p JOIN pages_treepath t ON p.id = t.descendant WHERE t.ancestor = 7 ) AS tmptable ) DELETE FROM pages_treepath WHERE descendant IN ( SELECT descendant FROM ( SELECT descendant FROM pages_treepath WHERE ancestor = 7 ) AS tmptable )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

前のリクエストとは異なり、これはやや複雑で、ページ自体が最初に削除され、その後ページ間の接続が削除されます（後者は最初の削除時にアクティブに使用されるため）。



クエリの複雑さは、部分的には、MySQLが同じテーブルからのSELECT



セレクションを含むWHERE



でレコードを削除することをMySQLが許可しないという事実によるものです。 MySQLの場合、一時テーブルにSELECTクエリを配置する必要があります。 一般に、クエリは次のようになります。

 DELETE FROM pages WHERE id IN ( SELECT descendant FROM pages p JOIN pages_treepath t ON p.id = t.descendant WHERE t.ancestor = 7 ) DELETE FROM pages_treepath WHERE descendant IN ( SELECT descendant FROM pages_treepath WHERE ancestor = 7 )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

pages



テーブルのDELETEクエリにネストされたSELECTクエリを注意深く見ると、同様のクエリを既に検討していることがわかります。 これは、ページ識別子のみが前のものと異なります。 選択の結果、サイトセクションのすべての子ページ（セクション自体を含む）を取得し、取得した識別子を持つすべてのページを削除します。



ページが削除された後、ページ間のリンクを削除するために残ります。 これを行うために、先祖へのリンクが[サイト]ページの識別子と等しい場合、子孫のdescendant



へのすべてのリンクを見つけます。

ネストレベル

要素のネストレベルを制御するフィールドをリレーションテーブルに追加できます。 このフィールドを使用すると、直系の祖先または直系の子孫の選択をより簡単に要求できます。 例：

 SELECT * FROM pages p JOIN pages_treepath t ON (p.id = t.descendant) WHERE t.ancestor = 4 AND t.level = 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

データベーステーブルスキーマ



継続する。