MySQL ツリー構造データベース テーブル設計

序文

私は最近ツリーメニューを研究し、オンラインで多くの例を見つけました。以下は私がインターネットで見つけた情報で、自分でもう一度練習して、次回忘れないように記録したものです。

プログラミングの過程では、企業の部門、列構造、製品カテゴリなどの特定のデータ間の関係を表すためにツリー構造がよく使用されます。一般的に、これらのツリー構造はデータベースの助けを借りて永続化する必要があります。ただし、現在、さまざまなリレーショナル データベースはデータ情報を 2 次元テーブルの形式で記録および保存するため、ツリーを DBMS に直接保存することはできません。適切なスキーマとそれに対応する CRUD アルゴリズムを設計することが、リレーショナル データベースにツリー構造を保存するための鍵となります。

理想的なツリー構造には、データ ストレージの冗長性が低く、直感性に優れていること、検索とトラバーサルのプロセスがシンプルで効率的であること、ノードの追加、削除、変更、クエリ (CRUD) 操作が効率的であることなどの特性が必要です。ネットで偶然、とても素敵なデザインを見つけました。原文は英語でした。読んでみて、面白そうだったので、整理してみました。この記事では、ツリー構造の Schema 設計スキームを 2 つ紹介します。1 つは直感的でシンプルな設計アイデアであり、もう 1 つは左と右の値のエンコーディングに基づく改良されたスキームです。

1. 基本データ

この記事では、食品の系統樹の例を使用して、食品をカテゴリ、色、種類別に整理する方法を説明します。ツリー構造は次のとおりです。

2. 継承駆動設計

ツリー構造の最も直感的な分析は、ノード間の継承関係です。ノードの親ノードを明示的に記述することで、2 次元の関係テーブルを確立できます。このソリューションのツリー テーブル構造は通常、{Node_id、Parent_id} として設計されます。上記のデータは、次の図に示すように記述できます。

このソリューションの利点は明らかです。設計と実装は自然で、非常に直感的で便利です。もちろん、デメリットも非常に顕著です。ノード間の継承関係が直接記録されるため、ツリー上の CRUD 操作は非効率的になります。これは主に、頻繁な「再帰」操作が原因です。再帰プロセスはデータベースに絶えずアクセスし、各データベース IO には時間のオーバーヘッドが発生します。もちろん、このソリューションが役に立たないわけではありません。ツリーのサイズが比較的小さい場合は、キャッシュ メカニズムを使用してツリーを最適化し、ツリー情報をメモリにロードして処理し、直接のデータベース IO 操作によるパフォーマンスのオーバーヘッドを回避できます。

3. 左右の値のエンコーディングに基づく設計

一般的なデータベース ベースのアプリケーションでは、クエリの需要は削除や変更の需要よりも常に大きくなります。ツリー構造をクエリする際の「再帰」プロセスを回避するために、ツリーの事前順序トラバーサルに基づいて、ツリーのデータを保存するための新しい非再帰クエリと無限にグループ化された左と右の値のエンコード スキームが設計されています。

このテーブル構造を初めて見たとき、ほとんどの人は左の値 (Lft) と右の値 (Rgt) がどのように計算されるのかよくわからないと思います。また、このテーブル設計では、親ノードと子ノード間の継承関係が保持されていないように思われます。しかし、表の数字を指で 1 から 18 まで数えてみると、あることに気づくはずです。はい、下の図に示すように、指を動かす順序はツリーの事前順序トラバーサルを実行する順序です。ルート ノード Food の左側 (1 とマークされている) から開始し、事前順序トラバーサルの方向に従って、トラバースしたパスに 1 つずつ番号をマークし、最終的にルート ノード Food に戻り、右側に 18 と書き込みます。

この設計に基づいて、左の値が 2 より大きく、右の値が 11 より小さいすべてのノードが Fruit の後続ノードであると推測でき、ツリー全体の構造は左と右の値を通じて保存されます。しかし、これだけでは十分ではありません。私たちの目標はツリー上で CRUD 操作を実行できるようにすることです。つまり、対応するアルゴリズムを構築する必要があります。

4. ツリー構造 CRUD アルゴリズム

（１）ノードの子孫ノードを取得する

ノードの子孫ノードの事前順序トラバーサル リストを返すには、1 つの SQL ステートメントだけが必要です。Fruit を例に挙げます。

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC

クエリ結果は次のとおりです。

では、特定のノードには子孫ノードがいくつあるのでしょうか?ノードの左と右の値を使用して、その子孫ノードを囲むことができます。子孫の合計数 = (右の値 - 左の値 - 1) / 2。Fruitを例にとると、その子孫の合計数は、(11 - 2 - 1) / 2 = 4です。同時に、ツリー構造をより直感的に表示するには、ツリー内のノードのレベルを知る必要があります。これは、左と右の値の SQL クエリを通じて実現できます。Fruit を例にとると、SELECTCOUNT(*) FROM tree WHERE lft <= 2 AND rgt >=11 です。説明の便宜上、Tree のビューを作成し、階層列を追加します。列の値は、カスタム関数を記述することで計算できます。関数の定義は次のとおりです。

テーブルを作成

テーブル「tree」を作成します（
  `id` int(11) NULLではない、
  `name` varchar(255) デフォルト NULL,
  `lft` int(255) デフォルト NULL,
  `rgt` int(11) デフォルト NULL
)ENGINE=InnoDB デフォルト文字セット=utf8;

`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('1', 'Food', '1', '18') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('2', 'Fruit', '2', '11') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('3', 'Red', '3', '6') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('4', 'Cherry', '4', '5') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('5', 'Yellow', '7', '10') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('6', 'Banana', '8', '9') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('7', 'Meat', '12', '17') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('8', 'Beef', '13', '14') を挿入します。
`jpa`.`tree` (`id`, `name`, `lft`, `rgt`) に VALUES ('9', 'Pork', '15', '16') を挿入します。

ビュー「treeview」を作成します 
選択 
  `a`.`id` を `id` として、
  `a`.`name` を `name` として、
  `a`.`lft` を `lft` として、
  `a`.`rgt` を `rgt` として、
  `CountLayer` (`a`.`id`) を `layer` として 
から
  `木` `a` 

レベル計算関数に基づいてビューを作成し、ノード レベルの新しい一連のレコードを追加します。

> CREATE FUNCTION `CountLayer` (`node_id` INT) は INT (11) を返します 
始める
    結果をINT(10)で宣言する デフォルトは0;
    lftid INT を宣言します。
    rgtid INT を宣言します。
    SELECT lft,rgt INTO lftid, rgtid FROM tree WHERE id = node_id;
    SELECT COUNT(*) INTO result FROM tree WHERE lft <= lftid AND rgt >= rgtid;
    RETURN（結果）;
終わり

特定のノードのすべての子孫ノードと対応するレベルを計算するストアド プロシージャを作成します。

CREATE PROCEDURE `GetChildrenNodeList`(IN `node_id` INT)
始める
lftid INT を宣言します。
rgtid INT を宣言します。
SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
SELECT * FROM treeview WHERE lft BETWEEN lftid AND rgtid ORDER BY lft ASC;
終わり 

ここで、上記のストアド プロシージャを使用して、ノード Fruit のすべての子孫ノードと対応するレベルを計算します。クエリの結果は次のようになります。

上記の実装から、左右の値エンコーディングを使用する設計スキームでは、ツリーをトラバースするときに 2 つのデータベース クエリを実行するだけで済み、再帰が排除されることがわかります。また、クエリ条件はすべて数値比較であるため、クエリ効率が非常に高くなります。ツリーのサイズが拡大し続けると、左右の値エンコーディングに基づく設計スキームは、従来の再帰スキームよりもクエリ効率を大幅に向上させます。もちろん、ここではノードの子孫を取得するための単純なアルゴリズムのみを示しました。このツリーを実際に使用するには、同じレベルでノードを挿入したり削除したりする機能を実装する必要があります。

（２）ノードの系図パスを取得する

ノードの系図パスを取得したい場合、左と右の値の分析に基づいて完了するには、1 つの SQL ステートメントだけが必要です。 Fruit を例に挙げます: SELECT* FROM tree WHERE lft < 2 AND rgt > 11 ORDER BY lft ASC。比較的完全なストアド プロシージャは次のとおりです。

CREATE PROCEDURE `GetParentNodePath`(IN `node_id` INT)
始める
lftid INT を宣言します。
rgtid INT を宣言します。
SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
SELECT * FROM treeview WHERE lft < lftid AND rgt > rgtid ORDER BY lft ASC;
終わり

（３）ノードに子孫ノードを追加する

「Red」ノードの下に新しい子ノード「Apple」を追加すると、ツリーは次の図のようになります。ここで、赤いノードは新しく追加されたノードです。

CREATE PROCEDURE `AddSubNode`(IN `node_id` INT, IN `node_name` VARCHAR(64))
始める
   rgtid INT を宣言します。
   t_error INT をデフォルト 0 として宣言します。  
   DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET t_error=1; -- エラー処理 SELECT rgt INTO rgtid FROM tree WHERE id= node_id; 
   トランザクションを開始します。
        ツリーを更新します。SET rgt = rgt + 2 WHERE rgt >= rgtid;
        ツリーを更新します。SET lft = lft + 2 WHERE lft >= rgtid;
        ツリーに (NAME,lft,rgt) VALUES (node_name,rgtid,rgtid+1) を挿入します。    
    t_error =1の場合  
     ロールバック;
    それ以外
      専念;
    終了の場合;
終わり 

（4）ノードを削除する

ノードを削除する場合、そのノードのすべての子孫ノードが同時に削除され、削除されるノードの数は（削除されたノードの右側の値 - 削除されたノードの左側の値 + 1）/ 2となり、残りのノードの左側と右側の値が削除されたノードの左側と右側の値より大きい場合は調整されます。ツリーに何が起こるか見てみましょう。Beef を例にとると、削除の影響は以下の図に示されています。

次に、対応するストアド プロシージャを構築します。

CREATE PROCEDURE `DelNode`(IN `node_id` INT)
始める
   lftid INT を宣言します。
     rgtid INT を宣言します。
   t_error INT をデフォルト 0 として宣言します。  
   DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET t_error=1; -- エラー処理 SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
   トランザクションを開始します。
       lft >= lftid かつ rgt <= rgtid の場合、tree から削除します。
       ツリーを更新します。SET lft = lft -(rgtid - lftid + 1) WHERE lft > lftid;
       ツリーを更新します。SET rgt = rgt -(rgtid - lftid + 1) WHERE rgt >rgtid;
    t_error =1の場合  
     ロールバック;
    それ以外
      専念;
    終了の場合;

終わり 

V. 結論

左と右の値のエンコードを通じて無制限のグループ化を実現するツリー構造スキーマ設計スキームを要約すると、次のようになります。

（１）利点：再帰演算なしで無制限のグループ化を実現し、クエリ条件は整数の比較に基づいているため、非常に効率的です。

（2）デメリット：ノードの追加、削除、変更にはコストがかかり、テーブル内のデータの多くの側面に変更が伴います。

参考文献

https://www.jb51.net/article/223579.htm