一、引言
產(chǎn)品分類，多級(jí)的樹(shù)狀結(jié)構(gòu)的論壇，郵件列表等許多地方我們都會(huì)遇到這樣的問(wèn)題：如何存儲(chǔ)多級(jí)結(jié)構(gòu)的數(shù)據(jù)？在php的應(yīng)用中，提供后臺(tái)數(shù)據(jù)存儲(chǔ)的通常是關(guān)系型數(shù)據(jù)庫(kù)，它能夠保存大量的數(shù)據(jù)，提供高效的數(shù)據(jù)檢索和更新服務(wù)。然而關(guān)系型數(shù)據(jù)的基本形式是縱橫交錯(cuò)的表，是一個(gè)平面的結(jié)構(gòu)，如果要將多級(jí)樹(shù)狀結(jié)構(gòu)存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)里就需要進(jìn)行合理的翻譯工作。接下來(lái)我會(huì)將自己的所見(jiàn)所聞和一些實(shí)用的經(jīng)驗(yàn)和大家探討一下：
層級(jí)結(jié)構(gòu)的數(shù)據(jù)保存在平面的數(shù)據(jù)庫(kù)中基本上有兩種常用設(shè)計(jì)方法：
    * 毗鄰目錄模式(adjacency list model)
    * 預(yù)排序遍歷樹(shù)算法(modified preorder tree traversal algorithm)
我不是計(jì)算機(jī)專業(yè)的，也沒(méi)有學(xué)過(guò)什么數(shù)據(jù)結(jié)構(gòu)的東西，所以這兩個(gè)名字都是我自己按照字面的意思翻的，如果說(shuō)錯(cuò)了還請(qǐng)多多指教。這兩個(gè)東西聽(tīng)著好像很?chē)樔耍鋵?shí)非常容易理解。

二、模型
這里我用一個(gè)簡(jiǎn)單食品目錄作為我們的示例數(shù)據(jù)。
我們的數(shù)據(jù)結(jié)構(gòu)是這樣的，以下是代碼：
復(fù)制代碼 代碼如下:
Food

|---Fruit

|    |---Red

|    |    |--Cherry

|    +---Yellow

|          +--Banana

+---Meat
      |--Beef
      +--Pork

為了照顧那些英文一塌糊涂的php愛(ài)好者
復(fù)制代碼 代碼如下:
Food  : 食物
Fruit : 水果
Red   : 紅色
Cherry: 櫻桃
Yellow: 黃色
Banana: 香蕉
Meat  : 肉類
Beef  : 牛肉
Pork  : 豬肉

三、實(shí)現(xiàn)
1、毗鄰目錄模式(adjacency list model)
這種模式我們經(jīng)常用到，很多的教程和書(shū)中也介紹過(guò)。我們通過(guò)給每個(gè)節(jié)點(diǎn)增加一個(gè)屬性 parent 來(lái)表示這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)從而將整個(gè)樹(shù)狀結(jié)構(gòu)通過(guò)平面的表描述出來(lái)。根據(jù)這個(gè)原則，例子中的數(shù)據(jù)可以轉(zhuǎn)化成如下的表：
以下是代碼：
復(fù)制代碼 代碼如下:
+-----------------------+
|   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的一個(gè)子節(jié)點(diǎn)，Green是Fruit的一個(gè)子節(jié)點(diǎn)。而根節(jié)點(diǎn)'Food'沒(méi)有父節(jié)點(diǎn)。 為了簡(jiǎn)單地描述這個(gè)問(wèn)題，這個(gè)例子中只用了name來(lái)表示一個(gè)記錄。 在實(shí)際的數(shù)據(jù)庫(kù)中，你需要用數(shù)字的id來(lái)標(biāo)示每個(gè)節(jié)點(diǎn)，數(shù)據(jù)庫(kù)的表結(jié)構(gòu)大概應(yīng)該像這樣：id, parent_id, name, descrīption。
有了這樣的表我們就可以通過(guò)數(shù)據(jù)庫(kù)保存整個(gè)多級(jí)樹(shù)狀結(jié)構(gòu)了。
顯示多級(jí)樹(shù)，如果我們需要顯示這樣的一個(gè)多級(jí)結(jié)構(gòu)需要一個(gè)遞歸函數(shù)。
以下是代碼：
復(fù)制代碼 代碼如下:
<?php
// $parent is the parent of the children we want to see
// $level is increased when we go deeper into the tree,
//        used to display a nice indented tree
function display_children($parent, $level) {
    // 獲得一個(gè) 父節(jié)點(diǎn) $parent 的所有子節(jié)點(diǎn)
    $result = mysql_query("
        SELECT name
        FROM tree
        WHERE parent = '" . $parent . "'
        ;"
    );
    // 顯示每個(gè)子節(jié)點(diǎn)
    while ($row = mysql_fetch_array($result)) {
        // 縮進(jìn)顯示節(jié)點(diǎn)名稱
        echo str_repeat('  ', $level) . $row['name'] . "/n";
        //再次調(diào)用這個(gè)函數(shù)顯示子節(jié)點(diǎn)的子節(jié)點(diǎn)
        display_children($row['name'], $level+1);
    }
}
?>

對(duì)整個(gè)結(jié)構(gòu)的根節(jié)點(diǎn)（Food）使用這個(gè)函數(shù)就可以打印出整個(gè)多級(jí)樹(shù)結(jié)構(gòu)，由于Food是根節(jié)點(diǎn)它的父節(jié)點(diǎn)是空的，所以這樣調(diào)用: display_children('',0)。將顯示整個(gè)樹(shù)的內(nèi)容：
復(fù)制代碼 代碼如下:
Food
    Fruit
        Red
            Cherry
        Yellow
            Banana
    Meat
        Beef
        Pork

如果你只想顯示整個(gè)結(jié)構(gòu)中的一部分，比如說(shuō)水果部分，就可以這樣調(diào)用：display_children('Fruit',0);
幾乎使用同樣的方法我們可以知道從根節(jié)點(diǎn)到任意節(jié)點(diǎn)的路徑。比如 Cherry 的路徑是　"Food >; Fruit >; Red"。 為了得到這樣的一個(gè)路徑我們需要從最深的一級(jí)"Cherry"開(kāi)始， 查詢得到它的父節(jié)點(diǎn)"Red"把它添加到路徑中，然后我們?cè)俨樵僐ed的父節(jié)點(diǎn)并把它也添加到路徑中，以此類推直到最高層的"Food",以下是代碼：
復(fù)制代碼 代碼如下:
<?php
// $node 是那個(gè)最深的節(jié)點(diǎn)
function get_path($node) {
    // 查詢這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
    $result = mysql_query("
        SELECT parent
        FROM tree
        WHERE name = '" . $node ."'
        ;"
    );
    $row = mysql_fetch_array($result);
    // 用一個(gè)數(shù)組保存路徑
    $path = array();
    // 如果不是根節(jié)點(diǎn)則繼續(xù)向上查詢
    // (根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn))
    if ($row['parent'] != '') {
        // the last part of the path to $node, is the name
        // of the parent of $node
        $path[] = $row['parent'];
        // we should add the path to the parent of this node
        // to the path
        $path = array_merge(get_path($row['parent']), $path);
    }
    // return the path
    return $path;
}
?>;

如果對(duì)"Cherry"使用這個(gè)函數(shù)：print_r(get_path('Cherry'))，就會(huì)得到這樣的一個(gè)數(shù)組了：
復(fù)制代碼 代碼如下:
Array (
    [0] => Food
    [1] => Fruit
    [2] => Red
)

接下來(lái)如何把它打印成你希望的格式，就是你的事情了。
缺點(diǎn)：
這種方法很簡(jiǎn)單，容易理解，好上手。但是也有一些缺點(diǎn)。主要是因?yàn)檫\(yùn)行速度很慢，由于得到每個(gè)節(jié)點(diǎn)都需要進(jìn)行數(shù)據(jù)庫(kù)查詢，數(shù)據(jù)量大的時(shí)候要進(jìn)行很多查詢才能完成一個(gè)樹(shù)。另外由于要進(jìn)行遞歸運(yùn)算，遞歸的每一級(jí)都需要占用一些內(nèi)存所以在空間利用上效率也比較低。

2、預(yù)排序遍歷樹(shù)算法
現(xiàn)在讓我們看一看另外一種不使用遞歸計(jì)算，更加快速的方法，這就是預(yù)排序遍歷樹(shù)算法(modified preorder tree traversal algorithm)
這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由于這種方法不使用遞歸查詢算法，有更高的查詢效率。

我們首先將多級(jí)數(shù)據(jù)按照下面的方式畫(huà)在紙上，在根節(jié)點(diǎn)Food的左側(cè)寫(xiě)上 1 然后沿著這個(gè)樹(shù)繼續(xù)向下 在 Fruit 的左側(cè)寫(xiě)上 2 然后繼續(xù)前進(jìn)，沿著整個(gè)樹(shù)的邊緣給每一個(gè)節(jié)點(diǎn)都標(biāo)上左側(cè)和右側(cè)的數(shù)字。最后一個(gè)數(shù)字是標(biāo)在Food 右側(cè)的 18。在下面的這張圖中你可以看到整個(gè)標(biāo)好了數(shù)字的多級(jí)結(jié)構(gòu)。（沒(méi)有看懂？用你的手指指著數(shù)字從1數(shù)到18就明白怎么回事了。還不明白，再數(shù)一遍，注意移動(dòng)你的手指）。
這些數(shù)字標(biāo)明了各個(gè)節(jié)點(diǎn)之間的關(guān)系，"Red"的號(hào)是3和6，它是 "Food" 1-18 的子孫節(jié)點(diǎn)。 同樣，我們可以看到 所有左值大于2和右值小于11的節(jié)點(diǎn) 都是"Fruit" 2-11 的子孫節(jié)點(diǎn)
以下是代碼：
復(fù)制代碼 代碼如下:
                         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

這樣整個(gè)樹(shù)狀結(jié)構(gòu)可以通過(guò)左右值來(lái)存儲(chǔ)到數(shù)據(jù)庫(kù)中。繼續(xù)之前，我們看一看下面整理過(guò)的數(shù)據(jù)表。
以下是代碼：
復(fù)制代碼 代碼如下:
+----------+------------+-----+-----+
|  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"來(lái)表示左右字段。 另外這種結(jié)構(gòu)中不再需要"parent"字段來(lái)表示樹(shù)狀結(jié)構(gòu)。也就是 說(shuō)下面這樣的表結(jié)構(gòu)就足夠了。
以下是代碼：
復(fù)制代碼 代碼如下:
+------------+-----+-----+
|    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ù)庫(kù)中獲取數(shù)據(jù)了，例如我們需要得到"Fruit"項(xiàng)下的所有所有節(jié)點(diǎn)就可以這樣寫(xiě)查詢語(yǔ)句：
復(fù)制代碼 代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

這個(gè)查詢得到了以下的結(jié)果。
以下是代碼：
復(fù)制代碼 代碼如下:
+------------+-----+-----+
|    name    | lft | rgt |
+------------+-----+-----+
|    Fruit   | 2   | 11  |
|    Red     | 3   |  6  |
|    Cherry  | 4   |  5  |
|    Yellow  | 7   | 10  |
|    Banana  | 8   |  9  |
+------------+-----+-----+

看到了吧，只要一個(gè)查詢就可以得到所有這些節(jié)點(diǎn)。為了能夠像上面的遞歸函數(shù)那樣顯示整個(gè)樹(shù)狀結(jié)構(gòu)，我們還需要對(duì)這樣的查詢進(jìn)行排序。用節(jié)點(diǎn)的左值進(jìn)行排序：
復(fù)制代碼 代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

剩下的問(wèn)題如何顯示層級(jí)的縮進(jìn)了。
以下是代碼：
復(fù)制代碼 代碼如下:
<?php
function display_tree($root) {
    // 得到根節(jié)點(diǎn)的左右值
    $result = mysql_query("
        SELECT lft, rgt
        FROM tree
        WHERE name = '" . $root . "'
        ;"
    );
    $row = mysql_fetch_array($result);
    // 準(zhǔn)備一個(gè)空的右值堆棧
    $right = array();
    // 獲得根基點(diǎn)的所有子孫節(jié)點(diǎn)
    $result = mysql_query("
        SELECT name, lft, rgt
        FROM tree
        WHERE lft BETWEEN '" . $row['lft'] . "' AND '" . $row['rgt'] ."'
        ORDER BY lft ASC
        ;"
    );
    // 顯示每一行
    while ($row = mysql_fetch_array($result)) {
        // only check stack if there is one
        if (count($right) > 0) {
            // 檢查我們是否應(yīng)該將節(jié)點(diǎn)移出堆棧
            while ($right[count($right) - 1] < $row['rgt']) {
                array_pop($right);
            }
        }
        // 縮進(jìn)顯示節(jié)點(diǎn)的名稱
        echo str_repeat('  ',count($right)) . $row['name'] . "/n";
        // 將這個(gè)節(jié)點(diǎn)加入到堆棧中
        $right[] = $row['rgt'];
    }
}
?>

如果你運(yùn)行一下以上的函數(shù)就會(huì)得到和遞歸函數(shù)一樣的結(jié)果。只是我們的這個(gè)新的函數(shù)可能會(huì)更快一些，因?yàn)橹挥?次數(shù)據(jù)庫(kù)查詢。
要獲知一個(gè)節(jié)點(diǎn)的路徑就更簡(jiǎn)單了，如果我們想知道Cherry 的路徑就利用它的左右值4和5來(lái)做一個(gè)查詢。
復(fù)制代碼 代碼如下:
SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;

這樣就會(huì)得到以下的結(jié)果：
以下是代碼：
復(fù)制代碼 代碼如下:
+------------+
|    name    |
+------------+
|    Food    |
|    Fruit   |
|    Red     |
+------------+

那么某個(gè)節(jié)點(diǎn)到底有多少子孫節(jié)點(diǎn)呢？很簡(jiǎn)單，子孫總數(shù)=(右值-左值-1)/2
復(fù)制代碼 代碼如下:
descendants = (right