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

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

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 兩個引數就算出其有多少個子元素。

總結

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

以上就是樹狀資料結構儲存方式（查詢篇）的詳細內容，更多請關注TW511.COM其它相關文章！