樹狀資料結構儲存方式（查詢篇）

鄰接列表模型

在日常業務開發中，我們常常會碰觸一些具有層次結構的樹狀資料。而在用關係型資料庫儲存時，往往將這種資料結構以一種稱為鄰接列表的模型進行存儲，像這樣：

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 是作為集合的邊界，兩者差值越大，則集合越大，裡面的元素就越多。

根據子集，找出父級的分類

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 來說，卻會讓整個在處理這個資料模型的時候，變得特別慢。

嵌套集模型

相較於鄰接列表模型，這種資料模型顯然並不是那麼好理解。而且不能那麼簡單的添加數據，它需要在添加的時候計算左右兩邊的數值，並挪動以後的數值，這增加了添加數據的壓力。

同樣，它帶來的好處是，可以讓你以一條簡單的查詢，就完成一個樹的查詢，可以根據 lft 和 rgt 兩個參數就算出其有多少個子元素。

總結

兩種模型各有優劣，一種優於插入，一種優於查詢。雖然我偏向嵌套集模型，但是還是需要根據特定業務來選用。

以上是樹狀資料結構儲存方式（查詢篇）的詳細內容。更多資訊請關注PHP中文網其他相關文章！