設計無限級分類

産品分類，多級的樹狀結構的論壇，郵件清單等許多地方我們都會遇到這樣的問題：如何存儲多級結構的資料？在PHP的應用中，提供背景資料存儲的通常是關系 型資料庫，它能夠儲存大量的資料，提供高效的資料檢索和更新服務。然而關系型資料的基本形式是縱橫交錯的表，是一個平面的結構，如果要将多級樹狀結構存儲 在關系型資料庫裡就需要進行合理的翻譯工作。接下來我會将自己的所見所聞和一些實用的經驗和大家探讨一下：

層級結構的資料儲存在平面的資料庫中基本上有兩種常用設計方法：

• 毗鄰目錄模式(adjacency list model)
• 預排序周遊樹算法(modified preorder tree traversal algorithm)

我不是計算機專業的，也沒有學過什麼資料結構的東西，是以這兩個名字都是我自己按照字面的意思翻的，如果說錯了還請多多指教。這兩個東西聽着好像很吓人，其實非常容易了解。

簡單需求分析： 

1.實作無限級分類。 

2.實作無限級連結導航 

3.實作逐級分類下各條資訊的查詢，包括最多浏覽量，最多評論量，最新資訊。 

4.随意轉移子分類到任何級别而不用修改分類下的資訊表 

5.使用最少的參數得到所要的資訊，URL參數最好隻有一個，比如cID=1或者ID=1 

6.不管多少級，隻有一個PHP檔案實作類清單和各種方式的資訊調用。 

表為兩張，一張分類表，一張資訊表。 

資訊表如下： 

`ID` int(10) unsigned NOT NULL auto_increment, 

`cID` tinyint(3) unsigned NOT NULL default '0', 

`title` varchar(255) NOT NULL default 'No Title', 

`content` mediumtext NOT NULL, 

最簡單的無限級分類資料表，隻是設定一個parentID來判斷父ID 

資料表如下： 

`cID` tinyint(3) unsigned NOT NULL auto_increment, 

`parentID` tinyint(3) unsigned NOT NULL default '0', 

`order` tinyint(3) NOT NULL default '0', 

`name` varchar(255) NOT NULL default '', 

這樣可以根據cID = parentID來判斷上一級内容，運用遞歸至最頂層。 

缺點是隻能查詢最小分類下的資訊。這樣就不能完成需求3、4點，而第二點也勉強符合 

第二種方法是設定parentID為varchar類型，将父類id都集中在這個字段裡，用符号隔開，比如：1,3,6 

這樣可以比較容易得到各上級分類的ID，而且在查詢分類下的資訊的時候，可以使用如：Select * From information Where cID Like "1,3%"。這樣能比較好解決需求3。不過在添加分類和轉移分類的時候操作将非常麻煩。 

我就說到這裡，請大家讨論一下如何能夠最簡單的方法實作無限級分類——考慮性能，代碼的簡練性，前背景操作的容易性，擴充性！

2、預排序周遊樹算法

Java代碼  

1. --  
2. -- 表的結構 `category`  
3. --  
4. CREATE TABLE IF NOT EXISTS `category` (  
5.   `id` int(11) NOT NULL AUTO_INCREMENT,  
6.   `type` int(11) NOT NULL COMMENT '1為文章類型2為産品類型3為下載下傳類型',  
7.   `title` varchar(50) NOT NULL,  
8.   `lft` int(11) NOT NULL,  
9.   `rgt` int(11) NOT NULL,  
10.   `lorder` int(11) NOT NULL COMMENT '排序',  
11.   `create_time` int(11) NOT NULL,  
12.   PRIMARY KEY (`id`)  
13. ) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=10 ;  
14. --  
15. -- 導出表中的資料 `category`  
16. --  
17. INSERT INTO `category` (`id`, `type`, `title`, `lft`, `rgt`, `lorder`, `create_time`) VALUES  
18. (1, 1, '頂級欄目', 1, 18, 1, 1261964806),  
19. (2, 1, '公司簡介', 14, 17, 50, 1264586212),  
20. (3, 1, '新聞', 12, 13, 50, 1264586226),  
21. (4, 2, '公司産品', 10, 11, 50, 1264586249),  
22. (5, 1, '榮譽資質', 8, 9, 50, 1264586270),  
23. (6, 3, '資料下載下傳', 6, 7, 50, 1264586295),  
24. (7, 1, '人才招聘', 4, 5, 50, 1264586314),  
25. (8, 1, '留言闆', 2, 3, 50, 1264586884),  
26. (9, 1, '總裁', 15, 16, 50, 1267771951);  

現在讓我們看一看另外一種不使用遞歸計算，更加快速的方法，這就是預排序周遊樹算法(modified preorder tree traversal algorithm)

這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易了解，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率。

我們首先将多級資料按照下面的方式畫在紙上，在根節點Food的左側寫上 1 然後沿着這個樹繼續向下 在 Fruit 的左側寫上 2 然後繼續前進，沿着整個樹的邊緣給每一個節點都标上左側和右側的數字。最後一個數字是标在Food 右側的 18。 在下面的這張圖中你可以看到整個标好了數字的多級結構。（沒有看懂？用你的手指指着數字從1數到18就明白怎麼回事了。還不明白，再數一遍，注意移動你的 手指）。

這些數字标明了各個節點之間的關系，"Red"的号是3和6，它是 "Food" 1-18 的子孫節點。 同樣，我們可以看到 所有左值大于2和右值小于11的節點 都是"Fruit" 2-11 的子孫節點

Java代碼  

1.                          1 Food 18  
2.                              |  
3.             +------------------------------+  
4.             |                              |  
5.         2 Fruit 11                     12 Meat 17  
6.             |                              |  
7.     +-------------+                 +------------+  
8.     |             |                 |            |  
9.  3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16  
10.     |             |  
11. 4 Cherry 5    8 Banana 9  

 這樣整個樹狀結構可以通過左右值來存儲到資料庫中。繼續之前，我們看一看下面整理過的資料表。

Java代碼  

1. +----------+------------+-----+-----+  
2. |  parent  |    name    | lft | rgt |  
3. +----------+------------+-----+-----+  
4. |          |    Food    | 1   | 18  |  
5. |   Food   |   Fruit    | 2   | 11  |  
6. |   Fruit  |    Red     | 3   |  6  |  
7. |   Red    |    Cherry  | 4   |  5  |  
8. |   Fruit  |    Yellow  | 7   | 10  |  
9. |   Yellow |    Banana  | 8   |  9  |  
10. |   Food   |    Meat    | 12  | 17  |  
11. |   Meat   |    Beef    | 13  | 14  |  
12. |   Meat   |    Pork    | 15  | 16  |  
13. +----------+------------+-----+-----+  

注意：由于"left"和"right"在 SQL中有特殊的意義 ，是以我們需要用"lft"和"rgt"來表示左右字段。 另外這種結構中不再需要"parent"字段來表示樹狀結構。也就是 說下面這樣的表結構就足夠了。

好了我們現在可以從資料庫中擷取資料了，例如我們需要得到"Fruit"項下的所有所有節點就可以這樣寫查詢語句：

Java代碼  

1. SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;  

這個查詢得到了以下的結果。

Java代碼  

1. +------------+-----+-----+  
2. |    name    | lft | rgt |  
3. +------------+-----+-----+  
4. |    Fruit   | 2   | 11  |  
5. |    Red     | 3   |  6  |  
6. |    Cherry  | 4   |  5  |  
7. |    Yellow  | 7   | 10  |  
8. |    Banana  | 8   |  9  |  
9. +------------+-----+-----+  

 要獲知一個節點的路徑就更簡單了，如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個查詢。

Java代碼  

1. SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;  

 那麼某個節點到底有多少子孫節點呢？很簡單，子孫總數=(右值-左值-1)/2

用這個簡單的公式，我們可以很快的算出"Fruit 2-11"節點有4個子孫節點，而"Banana 8-9"節點沒有子孫節點，也就是說它不是一個父節點了。

那麼對于這樣的結構我們該如何增加，更新和删除一個節點呢？

增加一個節點一般有兩種方法：

第一種，保留原有的name 和parent結構，用老方法向資料中添加資料，每增加一條資料以後使用rebuild_tree函數對整個結構重新進行一次編号。

第二種，效率更高的辦法是改變所有位于新節點右側的數值。舉例來說：我們想增加一種新的水果"Strawberry"（草莓）它将成為"Red"節點的最 後一個子節點。首先我們需要為它騰出一些空間。"Red"的右值應當從6改成8，"Yellow 7-10 "的左右值則應當改成 9-12。 依次類推我們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節點 （5 是"Red"最後一個子節點的右值） 加上2。 是以我們這樣進行資料庫操作：

Java代碼  

1. UPDATE tree SET rgt = rgt + 2 WHERE rgt > 5;  
2. UPDATE tree SET lft = lft + 2 WHERE lft > 5;  

 這樣就為新插入的值騰出了空間，現在可以在騰出的空間裡建立一個新的資料節點了， 它的左右值分别是6和7

Java代碼  

1. INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';  

 資料庫結構:

采用左右值編碼的儲存該樹的資料記錄如下（設表名為tree）：

c_id | name | left_node | right_node

1     |商品    |      1       |   18

2     | 食品  |       2      |  11

3     | 肉類  |     3         |  6

4     | 豬肉    |    4        |    5

5     | 菜類  |     7        |   10

6     | 白菜  |    8         |    9

7     | 電器  |    2         |    17

8     | 電視  |    13       |    14

9     | 電棒  |    15       |     16

第一次看見上面的資料記錄，相信大部分人都不清楚左值（left_node）和右值（right_node）是根據什麼規則計算出來的，而且，這種表設計似乎沒有儲存父節點的資訊。下面把左右值和樹結合起來，請看：

　　　　　　　　　 1商品18

　　　　　+---------------------------------------+

        2食品11                                12電器17

+-----------------+               +---------------------+

3肉類6           7菜類10       13電視14              15電棒16

4豬肉5            8白菜9

請用手指指着上圖中的數字，從1數到18，學習過資料結構的朋友肯定會發現什麼吧？對，你手指移動的順序就是對這棵樹的進行先序周遊的順序。接下來，讓我講述一下如何利用節點的左右值，得到該節點的父節點，子孫節點數量，及自己在樹中的層數。

采用左右值編碼的設計方案，在進行類别樹的周遊時，由于隻需進行2次查詢，消除了遞歸，再加上查詢條件都為數字比較，效率極高，類别樹的記錄條目越多，執行效率越高。

應用

某個節點到底有多少子孫節點？

子孫總數＝（父節點的右值 - 父節點的左值-1）/2

以節點“食品”舉例，其子孫總數＝（11-2-1）/ 2 ＝ 4

如何判斷某一節點下有沒有子節點？

  當 該節點左值-1 等于 其右值 時，其下沒有子節點。

檢索某一父節點的所有子節點？

假定我們要對節點“食品”及其子孫節點進行先序周遊的清單，隻需使用如下一條sql語句：

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

如何取得父類？

SELECT * FROM `tree` WHERE `left_node`<$left_node AND `right_node`>$right_node

檢索之後如何清單？

當左值+1==右值時，該節點沒有子節點，則下一節點不為其子節點

若下一節點的左值==上一節點右值+1，則2個節點是同級關系

若下一節點的左值==上一節點的左值+1時，則第2個節點應是第一個節點的子節點

若下一節點的左值-上一節點的右值>1時，則下一節點比上一節點高

（下一節點的左值-上一節點的右值）

級

在某一父節點下添加一個子節點？

1. 要求該子節點為該父節點下排序第一的節點，則$left_node = 父節點left_node+1, $right_node = $left_node+1;

2. 要求該節點位于父節點下一個子節點A後面，則$left_node = 節點A的right_node+1, $right_node = $left_node+1;

3. 要求該節點是位于父節點下排序最後一位的節點，則$left_node = 父節點right_node, $right_node = $left_node+1;

Sql:

UPDATE `tree` SET `right_node`=`right_node`+2 WHERE `right_node`>=$left_node

UPDATE `tree` SET `left_node`=`left_node`+2 WHERE `left_node`>=$left_node

INSERT INTO `tree` (`name` , `left_node` , `right_node`) VALUES

(`名字` , $left_node , $right_node)

移動節點，包括其子節點至節點A下？

設該節點左值$left_node , 右值$right_node

其子節點的數目為$count = ($right_node - $left_node -1 )/2 , 節點A左值為$A_left_node ,

UPDATE `tree` SET `right_node`=`right_node`-$right_node-$left_node-1 WHERE `right_node`>$right_node AND `right_node`<$A_left_node

UPDATE `tree` SET `left_node`=`left_node`-$right_node-$left_node-1 WHERE `left_node`>$right_node AND `left_node`<=$A_left_node

UPDATE `tree` SET `left_node`=`left_node`+$A_left_node-$right_node , `right_node`=`right_node`+$A_left_node-$right_node WHERE `left_node`>=$left_node

AND `right_node`<=$right_node

删除所有子節點？

DELETE FROM `tree` WHERE `left_node`>父節點的左值 AND `right_node`>父節點的右值

删除一個節點及其子節點？

在上例中的<号>号後面各加一個=号