[轉(zhuǎn)] 如何用數(shù)據(jù)庫保存多級結(jié)構(gòu)的數(shù)據(jù)

wolf432

產(chǎn)品分類，多級的樹狀結(jié)構(gòu)的論壇，郵件列表等許多地方我們都會遇到這樣的問題：如何存儲多級結(jié)構(gòu)的數(shù)據(jù)？在
PHP
的應(yīng)用中，提供后臺數(shù)據(jù)存儲的通常是關(guān)系型
數(shù)據(jù)庫
，它能夠保存大量的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索和更新服務(wù)。然而關(guān)系型數(shù)據(jù)的基本形式是縱橫交錯的表，是一個平面的結(jié)構(gòu)，如果要將多級樹狀結(jié)構(gòu)存儲在關(guān)系型數(shù)據(jù)庫里就需要進行合理的翻譯
工作
。接下來我會將自己的所見所聞和一些實用的經(jīng)驗和大家探討一下：
層級結(jié)構(gòu)的數(shù)據(jù)保存在平面的數(shù)據(jù)庫中基本上有兩種常用設(shè)計
方法
：
1、毗鄰目錄模式(adjacency list model)
2、預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm)
我不是計算機專業(yè)的，也沒有學(xué)過什么數(shù)據(jù)結(jié)構(gòu)的東西，所以這兩個名字都是我自己按照字面的意思翻的，如果說錯了還請多多指教。
這兩個東西聽著好像很嚇人，其實非常容易理解。這里我用一個簡單食品目錄作為我們的示例數(shù)據(jù)。
我們的數(shù)據(jù)結(jié)構(gòu)是這樣的
以下是
代碼
：
Food
|
|---Fruit
|    |
|    |---Red
|    |    |
|    |    |--Cherry
|    |
|    |---Yellow
|          |
|          |--Banana
|
|---Meat
     |
     |--Beef
     |
     |--Pork
為了照顧那些英文一塌糊涂的PHP愛好者
Food:食物
Fruit:水果
Red:紅色
Cherry:櫻桃
Yellow:黃色
Banana:香蕉
Meat:肉類
Beef:牛肉
Pork:豬肉
毗鄰目錄模式(adjacency list model)
這種模式我們經(jīng)常用到，很多的教程和書中也介紹過。我們通過給每個節(jié)點增加一個屬性 parent 來表示這個節(jié)點的父節(jié)點從而將整個樹狀結(jié)構(gòu)通過平面的表描述出來。根據(jù)這個原則，例子中的數(shù)據(jù)可以轉(zhuǎn)化成如下的表：
以下是代碼：
+-----------------------+
|   parent |    name    |
+-----------------------+
|          |    Food    |
|   Food   |   Fruit    |
|   Fruit  |    Green   |
|   Green  |    Pear    |
|   Fruit  |    Red     |
|   Red    |    Cherry  |
|   Fruit  |    Yellow  |
|   Yellow |    Banana  |
|   Food   |    Meat    |
|   Meat   |    Beef    |
|   Meat   |    Pork    |
+-----------------------+
我
們看到 Pear 是Green的一個子節(jié)點，Green是Fruit的一個子節(jié)點。而根節(jié)點'Food'沒有父節(jié)點。 為了簡單地描述這個問題， 這個
例子中只用了name來表示一個記錄。 在實際的數(shù)據(jù)庫中，你需要用數(shù)字的id來標示每個節(jié)點，數(shù)據(jù)庫的表結(jié)構(gòu)大概應(yīng)該像這
樣：id, parent_id, name, descrīption。
有了這樣的表我們就可以通過數(shù)據(jù)庫保存整個多級樹狀結(jié)構(gòu)了。
顯示多級樹
如果我們需要顯示這樣的一個多級結(jié)構(gòu)需要一個遞歸函數(shù)。
以下是代碼：
;
對整個結(jié)構(gòu)的根節(jié)點（Food）使用這個函數(shù)就可以打印出整個多級樹結(jié)構(gòu)，由于Food是根節(jié)點它的父節(jié)點是空的，所以這樣調(diào)用: display_children('',0)。將顯示整個樹的內(nèi)容：
Food
Fruit
Red
  Cherry
Yellow
  Banana
Meat
Beef
Pork
如果你只想顯示整個結(jié)構(gòu)中的一部分，比如說水果部分，就可以這樣調(diào)用：display_children('Fruit',0);
幾
乎使用同樣的方法我們可以知道從根節(jié)點到任意節(jié)點的路徑。比如 Cherry 的路徑是　
"Food >; Fruit >; Red"。 為了得到這樣的一個路徑我們需要從最深的一級"Cherry"開始， 查詢得到它的父節(jié)
點"Red"把它添加到路徑中， 然后我們再查詢Red的父節(jié)點并把它也添加到路徑中，以此類推直到最高層的"Food"
以下是代碼：
;
如果對"Cherry"使用這個函數(shù)：print_r(get_path('Cherry'))，就會得到這樣的一個數(shù)組了：
Array
(
  [0] =>; Food
  [1] =>; Fruit
  [2] =>; Red
)
接下來如何把它打印成你希望的格式，就是你的事情了。
缺點：
這種方法很簡單，容易理解，好上手。但是也有一些缺點。主要是因為運行速度很慢，由于得到每個節(jié)點都需要進行數(shù)據(jù)庫查詢，數(shù)據(jù)量大的時候要進行很多查詢才能完成一個樹。另外由于要進行遞歸運算，遞歸的每一級都需要占用一些內(nèi)存所以在空間利用上效率也比較低。
現(xiàn)在讓我們看一看另外一種不使用遞歸計算，更加快速的方法，這就是預(yù)排序遍歷樹算法(modified preorder tree traversal algorithm)
這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率。
我
們首先將多級數(shù)據(jù)按照下面的方式畫在紙上，在根節(jié)點Food的左側(cè)寫上 1 然后沿著這個樹繼續(xù)向下 在 Fruit 的左側(cè)寫上 2 然后繼續(xù)前進，沿
著整個樹的邊緣給每一個節(jié)點都標上左側(cè)和右側(cè)的數(shù)字。最后一個數(shù)字是標在Food 右側(cè)的 18。 在下面的這張圖中你可以看到整個標好了數(shù)字的多級結(jié)
構(gòu)。（沒有看懂？用你的手指指著數(shù)字從1數(shù)到18就明白怎么回事了。還不明白，再數(shù)一遍，注意移動你的手指）。
這些數(shù)字標明了各個節(jié)點之間的關(guān)系，"Red"的號是3和6，它是 "Food" 1-18 的子孫節(jié)點。 同樣，我們可以看到 所有左值大于2和右值小于11的節(jié)點 都是"Fruit" 2-11 的子孫節(jié)點
以下是代碼：
                                1 Food 18
                                    |
                +-------------------------------------------+
                |                                                       |
            2 Fruit 11                                    12 Meat 17
                |                                                       |
    +------------------------+                   +-----------------------+
    |                                |                   |                              |
3 Red 6               7 Yellow 10         13 Beef 14            15 Pork 16
    |                                |
4 Cherry 5               8 Banana 9
這樣整個樹狀結(jié)構(gòu)可以通過左右值來存儲到數(shù)據(jù)庫中。繼續(xù)之前，我們看一看下面整理過的數(shù)據(jù)表。
以下是代碼：
+-----------------------+-----+-----+
|   parent |    name  | lft   | rgt |
+-----------------------+-----+-----+
|              |    Food    | 1   | 18  |
|   Food   |   Fruit      | 2   | 11  |
|   Fruit    |    Red      | 3   |  6  |
|   Red     |    Cherry  | 4   |  5  |
|   Fruit    |    Yellow  | 7   | 10  |
|   Yellow |    Banana | 8   |  9  |
|   Food   |    Meat     | 12  | 17  |
|   Meat   |    Beef     | 13  | 14  |
|   Meat   |    Pork     | 15  | 16  |
+-----------------------+-----+-----+
注意：由于"left"和"right"在 SQL中有特殊的意義，所以我們需要用"lft"和"rgt"來表示左右字段。 另外這種結(jié)構(gòu)中不再需要"parent"字段來表示樹狀結(jié)構(gòu)。也就是 說下面這樣的表結(jié)構(gòu)就足夠了。
以下是代碼：
+------------+-----+-----+
|    name    | lft | rgt |
+------------+-----+-----+
|    Food    | 1   | 18  |
|   Fruit    | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
|    Meat    | 12  | 17  |
|    Beef    | 13  | 14  |
|    Pork    | 15  | 16  |
+------------+-----+-----+
好了我們現(xiàn)在可以從數(shù)據(jù)庫中獲取數(shù)據(jù)了，例如我們需要得到"Fruit"項下的所有所有節(jié)點就可以這樣寫查詢語句：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
這個查詢得到了以下的結(jié)果。
以下是代碼：
+------------+-----+-----+
|    name    | lft | rgt |
+------------+-----+-----+
|   Fruit    | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
+------------+-----+-----+
看到了吧，只要一個查詢就可以得到所有這些節(jié)點。為了能夠像上面的遞歸函數(shù)那樣顯示整個樹狀結(jié)構(gòu)，我們還需要對這樣的查詢進行排序。用節(jié)點的左值進行排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的問題如何顯示層級的縮進了。
以下是代碼：
;0)
   {
           // 檢查我們是否應(yīng)該將節(jié)點移出堆棧
           while ($right[count($right)-1];
如果你運行一下以上的函數(shù)就會得到和遞歸函數(shù)一樣的結(jié)果。只是我們的這個新的函數(shù)可能會更快一些，因為只有2次數(shù)據(jù)庫查詢。
要獲知一個節(jié)點的路徑就更簡單了，如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個查詢。
SELECT name FROM tree WHERE lft ; 5 ORDER BY lft ASC;
這樣就會得到以下的結(jié)果：
以下是代碼：
+------------+
|    name    |
+------------+
|   Food     |
|   Fruit    |
|    Red     |
+------------+
那么某個節(jié)點到底有多少子孫節(jié)點呢？很簡單，子孫總數(shù)=(右值-左值-1)/2
descendants = (right – left - 1) / 2
不相信？自己算一算啦。
用這個簡單的公式，我們可以很快的算出"Fruit 2-11"節(jié)點有4個子孫節(jié)點，而"Banana 8-9"節(jié)點沒有子孫節(jié)點，也就是說它不是一個父節(jié)點了。
很神奇吧？雖然我已經(jīng)多次用過這個方法，但是每次這樣做的時候還是感到很神奇。
這的確是個很好的辦法，但是有什么辦法能夠幫我們建立這樣有左右值的數(shù)據(jù)表呢？這里再介紹一個函數(shù)給大家，這個函數(shù)可以將name和parent結(jié)構(gòu)的表自動轉(zhuǎn)換成帶有左右值的數(shù)據(jù)表。
以下是代碼：
;
當然這個函數(shù)是一個遞歸函數(shù)，我們需要從根節(jié)點開始運行這個函數(shù)來重建一個帶有左右值的樹
rebuild_tree('Food',1);
這個函數(shù)看上去有些復(fù)雜，但是它的作用和手工對表進行編號一樣，就是將立體多層結(jié)構(gòu)的轉(zhuǎn)換成一個帶有左右值的數(shù)據(jù)表。
那么對于這樣的結(jié)構(gòu)我們該如何增加，更新和刪除一個節(jié)點呢？
增加一個節(jié)點一般有兩種方法：
第一種，保留原有的name 和parent結(jié)構(gòu)，用老方法向數(shù)據(jù)中添加數(shù)據(jù)，每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對整個結(jié)構(gòu)重新進行一次編號。
第
二種，效率更高的辦法是改變所有位于新節(jié)點右側(cè)的數(shù)值。舉例來說：我們想增加一種新的水果"Strawberry"（草莓）它將成為"Red"節(jié)點的最后
一個子節(jié)點。首先我們需要為它騰出一些空間。"Red"的右值應(yīng)當從6改成8，"Yellow 7-10 "的左右值則應(yīng)當改成 9-12。 依次類推我
們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節(jié)點 （5 是"Red"最后一個子節(jié)點的右值） 加上2。 所以我們這樣進行數(shù)據(jù)庫操
作：
UPDATE tree SET rgt=rgt+2 WHERE rgt>;5;
UPDATE tree SET lft=lft+2 WHERE lft>;5;
這樣就為新插入的值騰出了空間，現(xiàn)在可以在騰出的空間里建立一個新的數(shù)據(jù)節(jié)點了， 它的左右值分別是6和7
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
再做一次查詢看看吧！怎么樣？很快吧。
好了，現(xiàn)在你可以用兩種不同的方法設(shè)計你的多級數(shù)據(jù)庫結(jié)構(gòu)了，采用何種方式完全取決于你個人的判斷，但是對于層次多數(shù)量大的結(jié)構(gòu)我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數(shù)據(jù)，則第一種方法更為簡便。
另外，如果數(shù)據(jù)庫支持的話 你還可以將rebuild_tree()和 騰出空間的操作寫成數(shù)據(jù)庫端的觸發(fā)器函數(shù)， 在插入和更新的時候自動執(zhí)行， 這樣可以得到更好的運行效率， 而且你添加新節(jié)點的SQL語句會變得更加簡單。
               
               
               

本文來自ChinaUnix博客，如果查看原文請點：http://blog.chinaunix.net/u3/93245/showart_1968607.html