無(wú)論你要構(gòu)建自己的論壇，在你的網(wǎng)站上發(fā)布消息還是書寫自己的CMS程序，你都會(huì)遇到要在數(shù)據(jù)庫(kù)中存儲(chǔ)層次數(shù)據(jù)的情況。同時(shí)，除非你使用一種像XML的數(shù)據(jù)庫(kù)，否則關(guān)系數(shù)據(jù)庫(kù)中的表都不是層次結(jié)構(gòu)的，他們只是一個(gè)平坦的列表。所以你必須找到一種把層次數(shù)據(jù)庫(kù)轉(zhuǎn)化的方法。

存儲(chǔ)樹形結(jié)構(gòu)是一個(gè)很常見的問(wèn)題，他有好幾種解決方案。主要有兩種方法：鄰接列表模型和改進(jìn)前序遍歷樹算法

在本文中，我們將探討這兩種保存層次數(shù)據(jù)的方法。我將舉一個(gè)在線食品店樹形圖的例子。這個(gè)食品店通過(guò)類別、顏色和品種來(lái)組織食品。樹形圖如下：

本文包含了一些代碼的例子來(lái)演示如何保存和獲取數(shù)據(jù)。我選擇php來(lái)寫例子，因?yàn)槲页Ｓ眠@個(gè)語(yǔ)言，而且很多人也都使用或者知道這個(gè)語(yǔ)言。你可以很方便地把它們翻譯成你自己用的語(yǔ)言。

如你所見，對(duì)每個(gè)節(jié)點(diǎn)保存一個(gè)“父”節(jié)點(diǎn)。我們可以看到“Pear”是“Green”的一個(gè)子節(jié)點(diǎn)，而后者又是“Fruit”的子節(jié)點(diǎn)，如此類推。 根節(jié)點(diǎn)，“Food”，則他的父節(jié)點(diǎn)沒(méi)有值。為了簡(jiǎn)單，我只用了“title”值來(lái)標(biāo)識(shí)每個(gè)節(jié)點(diǎn)。當(dāng)然，在實(shí)際的數(shù)據(jù)庫(kù)中，你要使用數(shù)字的ID。

顯示樹
現(xiàn)在我們已經(jīng)把樹放入數(shù)據(jù)庫(kù)中了，得寫一個(gè)顯示函數(shù)了。這個(gè)函數(shù)將從根節(jié)點(diǎn)開始――沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)――同時(shí)要顯示這個(gè)節(jié)點(diǎn)所有的子節(jié)點(diǎn)。對(duì)于這些子節(jié)點(diǎn)，函數(shù)也要獲取并顯示這個(gè)子節(jié)點(diǎn)的子節(jié)點(diǎn)。然后，對(duì)于他們的子節(jié)點(diǎn)，函數(shù)還要再顯示所有的子節(jié)點(diǎn)，然后依次類推。

也許你已經(jīng)注意到了，這種函數(shù)的描述，有一種普遍的模式。我們可以簡(jiǎn)單地只寫一個(gè)函數(shù)，用來(lái)獲得特定節(jié)點(diǎn)的子節(jié)點(diǎn)。這個(gè)函數(shù)然后要對(duì)每個(gè)子節(jié)點(diǎn)調(diào)用自身來(lái)再次顯示他們的子節(jié)點(diǎn)。這就是“遞歸”機(jī)制，因此稱這種方法叫“遞歸方法”。

要實(shí)現(xiàn)整個(gè)樹，我們只要調(diào)用函數(shù)時(shí)用一個(gè)空字符串作為 $parent 和 $level = 0: display_children('',0); 函數(shù)返回了我們的食品店的樹狀圖如下：
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork

注意如果你只想看一個(gè)子樹，你可以告訴函數(shù)從另一個(gè)節(jié)點(diǎn)開始。例如，要顯示“Fruit”子樹，你只要display_children('Fruit',0);
The Path to a Node節(jié)點(diǎn)的路徑
利用差不多的函數(shù)，我們也可以查詢某個(gè)節(jié)點(diǎn)的路徑如果你只知道這個(gè)節(jié)點(diǎn)的名字或者ID。例如，“Cherry”的路徑是“Food”> “Fruit”>“Red”。要獲得這個(gè)路徑，我們的函數(shù)要獲得這個(gè)路徑，這個(gè)函數(shù)必須從最深的層次開始：“Cheery”。但后查找這個(gè)節(jié)點(diǎn)的父 節(jié)點(diǎn)，并添加到路徑中。在我們的例子中，這個(gè)父節(jié)點(diǎn)是“Red”。如果我們知道“Red”是“Cherry”的父節(jié)點(diǎn)。

這個(gè)函數(shù)現(xiàn)在返回了指定節(jié)點(diǎn)的路徑。他把路徑作為數(shù)組返回，這樣我們可以使用print_r(get_path('Cherry')); 來(lái)顯示，其結(jié)果是：
Array
(
   [0] => Food
   [1] => Fruit
   [2] => Red)
不足
正如我們所見，這確實(shí)是一個(gè)很好的方法。他很容易理解，同時(shí)代碼也很簡(jiǎn)單。但是鄰接列表模型的缺點(diǎn)在哪里呢？在大多數(shù)編程語(yǔ)言中，他運(yùn)行很慢，效率很差。這主要是“遞歸”造成的。我們每次查詢節(jié)點(diǎn)都要訪問(wèn)數(shù)據(jù)庫(kù)。

每次數(shù)據(jù)庫(kù)查詢都要花費(fèi)一些時(shí)間，這讓函數(shù)處理龐大的樹時(shí)會(huì)十分慢。

造成這個(gè)函數(shù)不是太快的第二個(gè)原因可能是你使用的語(yǔ)言。不像Lisp這類語(yǔ)言，大多數(shù)語(yǔ)言不是針對(duì)遞歸函數(shù)設(shè)計(jì)的。對(duì)于每個(gè)節(jié)點(diǎn)，函數(shù)都要調(diào)用他自 己，產(chǎn)生新的實(shí)例。這樣，對(duì)于一個(gè)4層的樹，你可能同時(shí)要運(yùn)行4個(gè)函數(shù)副本。對(duì)于每個(gè)函數(shù)都要占用一塊內(nèi)存并且需要一定的時(shí)間初始化，這樣處理大樹時(shí)遞歸 就很慢了。

我們先把樹按照水平方式擺開。從根節(jié)點(diǎn)開始（“Food”），然后他的左邊寫上1。然后按照樹的順序（從上到下）給“Fruit”的左邊寫上2。這 樣，你沿著樹的邊界走啊走（這就是“遍歷”），然后同時(shí)在每個(gè)節(jié)點(diǎn)的左邊和右邊寫上數(shù)字。最后，我們回到了根節(jié)點(diǎn)“Food”在右邊寫上18。下面是標(biāo)上 了數(shù)字的樹，同時(shí)把遍歷的順序用箭頭標(biāo)出來(lái)了。

我們稱這些數(shù)字為左值和右值（如，“Food”的左值是1，右值是18）。正如你所見，這些數(shù)字按時(shí)了每個(gè)節(jié)點(diǎn)之間的關(guān)系。因?yàn)椤癛ed”有3和6 兩個(gè)值，所以，它是有擁有1-18值的“Food”節(jié)點(diǎn)的后續(xù)。同樣的，我們可以推斷所有左值大于2并且右值小于11的節(jié)點(diǎn)，都是有2-11的 “Food”節(jié)點(diǎn)的后續(xù)。這樣，樹的結(jié)構(gòu)就通過(guò)左值和右值儲(chǔ)存下來(lái)了。這種數(shù)遍整棵樹算節(jié)點(diǎn)的方法叫做“改進(jìn)前序遍歷樹”算法。

在繼續(xù)前，我們先看看我們的表格里的這些值：

注意單詞“l(fā)eft”和“right”在SQL中有特殊的含義。因此，我們只能用“l(fā)ft”和“rgt”來(lái)表示這兩個(gè)列。（譯注――其實(shí)Mysql 中可以用“`”來(lái)表示，如“`left`”，MSSQL中可以用“[]”括出，如“[left]”，這樣就不會(huì)和關(guān)鍵詞沖突了。）同樣注意這里我們已經(jīng)不需要“parent”列了。我們只需要使用lft和rgt就可以存儲(chǔ)樹的結(jié)構(gòu)。

獲取樹
如果你要通過(guò)左值和右值來(lái)顯示這個(gè)樹的話，你要首先標(biāo)識(shí)出你要獲取的那些節(jié)點(diǎn)。例如，如果你想獲得“Fruit”子樹，你要選擇那些左值在2到11的節(jié)點(diǎn)。用SQL語(yǔ)句表達(dá)：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
這個(gè)會(huì)返回：

好吧，現(xiàn)在整個(gè)樹都在一個(gè)查詢中了?，F(xiàn)在就要像前面的遞歸函數(shù)那樣顯示這個(gè)樹，我們要加入一個(gè)ORDER BY子句在這個(gè)查詢中。如果你從表中添加和刪除行，你的表可能就順序不對(duì)了，我們因此需要按照他們的左值來(lái)進(jìn)行排序。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
就只剩下縮進(jìn)的問(wèn)題了。

要顯示樹狀結(jié)構(gòu)，子節(jié)點(diǎn)應(yīng)該比他們的父節(jié)點(diǎn)稍微縮進(jìn)一些。我們可以通過(guò)保存一個(gè)右值的一個(gè)棧。每次你從一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)開始時(shí)，你把這個(gè)節(jié)點(diǎn)的右值 添加到棧中。你也知道子節(jié)點(diǎn)的右值都比父節(jié)點(diǎn)的右值小，這樣通過(guò)比較當(dāng)前節(jié)點(diǎn)和棧中的前一個(gè)節(jié)點(diǎn)的右值，你可以判斷你是不是在顯示這個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)。當(dāng) 你顯示完這個(gè)節(jié)點(diǎn)，你就要把他的右值從棧中刪除。要獲得當(dāng)前節(jié)點(diǎn)的層數(shù)，只要數(shù)一下棧中的元素。

如果運(yùn)行這段代碼，你可以獲得和上一部分討論的遞歸函數(shù)一樣的結(jié)果。而這個(gè)函數(shù)可能會(huì)更快一點(diǎn)：他不采用遞歸而且只是用了兩個(gè)查詢

節(jié)點(diǎn)的路徑
有了新的算法，我們還要另找一種新的方法來(lái)獲得指定節(jié)點(diǎn)的路徑。這樣，我們就需要這個(gè)節(jié)點(diǎn)的祖先的一個(gè)列表。

由于新的表結(jié)構(gòu)，這不需要花太多功夫。你可以看一下，例如，4-5的“Cherry”節(jié)點(diǎn)，你會(huì)發(fā)現(xiàn)祖先的左值都小于4，同時(shí)右值都大于5。這樣，我們就可以使用下面這個(gè)查詢：
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
注意，就像前面的查詢一樣，我們必須使用一個(gè)ORDER BY子句來(lái)對(duì)節(jié)點(diǎn)排序。這個(gè)查詢將返回：

+-------+
| title |
+-------+
| Food  |
| Fruit |
| Red   |
+-------+

我們現(xiàn)在只要把各行連起來(lái)，就可以得到“Cherry”的路徑了。
有多少個(gè)后續(xù)節(jié)點(diǎn)？How Many Descendants
如果你給我一個(gè)節(jié)點(diǎn)的左值和右值，我就可以告訴你他有多少個(gè)后續(xù)節(jié)點(diǎn)，只要利用一點(diǎn)點(diǎn)數(shù)學(xué)知識(shí)。
因?yàn)槊總€(gè)后續(xù)節(jié)點(diǎn)依次會(huì)對(duì)這個(gè)節(jié)點(diǎn)的右值增加2，所以后續(xù)節(jié)點(diǎn)的數(shù)量可以這樣計(jì)算：
descendants = (right