ツリーデータ構造の格納方法（クエリ）

隣接リスト モデル

日常のビジネス開発では、階層構造を持つツリー状のデータに遭遇することがよくあります。リレーショナル データベースに格納される場合、このデータ構造は多くの場合、次のような隣接リストと呼ばれるモデルに格納されます。

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `pid` int(11) DEFAULT 0,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

このモデルは次のことを表します。図は次のとおりです。

# このデータ モデルについては多くの人がすでによく知っていると思うので、ここでは詳しく説明しません。次のデータ モデルに注目してみましょう。

ネストされたセット モデル

ツリーを表す別の方法は、ツリーをセットとして保存することです。次のテーブル構造を再定義します:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `lft` int(11) NOT NULL UNIQUE CHECK (lft> 0),
  `rgt` int(11) NOT NULL UNIQUE CHECK (rgt> 1),
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

そして、このモデルの図は次のようになります:

lft と rgt はセットの境界として使用され、この 2 つの差が大きいほどセットが大きくなり、セット内の要素が多くなります。

サブセットに従って、親カテゴリを見つけます

SELECT c2.* 
  FROM categories as c1, categories as c2
  WHERE c1.lft BETWEEN c2.lft and c2.rgt 
      AND c1.title = '华为';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  5 | Harmony OS  |  10 |  13 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

親に従って、その下のすべてのサブセットを見つけます

SELECT c1.*
   FROM categories AS c1, categories AS c2
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
    AND c2.title = 'Smartphones';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  3 | Android     |   2 |   5 |
|  4 | iOS         |   6 |   9 |
|  5 | Harmony OS  |  10 |  13 |
|  6 | 小米        |   3 |   4 |
|  7 | iPhone      |   7 |   8 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

各カテゴリのレベルを表示

 SELECT COUNT(c2.id) AS indentation, c1.title
  FROM categories AS c1, categories AS c2下周三we'fv
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
  GROUP BY c1.title
  ORDER BY c1.lft;
+-------------+-------------+
| indentation | title       |
+-------------+-------------+
|           1 | Smartphones |
|           2 | Android     |
|           3 | 小米        |
|           2 | iOS         |
|           3 | iPhone      |
|           2 | Harmony OS  |
|           3 | 华为        |
+-------------+-------------+

利点と欠点

隣接リスト モデル

隣接リスト モデルは理解しやすく、必要なコードも非常に複雑です。単純。

しかし、ほとんどのプログラミング言語では、速度が遅く、非効率的です。これは主に再帰によって発生します。ツリー内の各ノードに対してデータベース クエリを実行する必要があります。

これにより、大きなツリーを扱う場合、各クエリに時間がかかるため、関数が非常に遅くなる可能性があります。関数ごとに、数値を取得するために再帰的アルゴリズムが必要になるためです。

もちろん、List のような再帰に適した言語を使用する場合は、このデータ モデルの欠点を無視できます。ただし、PHP の場合、このデータ モデルの処理全体が非常に遅くなります。

ネストされたセット モデル

隣接リスト モデルと比較すると、このデータ モデルは明らかにそれほど理解しやすいものではありません。また、データを追加するのはそう簡単ではなく、追加するときに左側と右側の値を計算し、後続の値を移動する必要があるため、データを追加するプレッシャーが高まります。

同様に、これがもたらす利点は、単純なクエリでツリー クエリを完了できることと、2 つのパラメータ lft と rgt に基づいてサブ要素の数を計算できることです。

概要

両方のモデルにはそれぞれ長所と短所があり、1 つは挿入よりも優れており、もう 1 つはクエリよりも優れています。私はネストされたセット モデルを好みますが、それでも特定のビジネスに基づいて選択する必要があります。

以上がツリーデータ構造の格納方法（クエリ）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。