樹狀數據結構存儲方式是什么

這篇文章給大家分享的是有關樹狀數據結構存儲方式是什么的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。

鄰接列表模型

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

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

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

感謝各位的閱讀！關于樹狀數據結構存儲方式是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！