我們經(jīng)常需要在關(guān)系型數(shù)據(jù)庫中保存一些樹狀結(jié)構(gòu)數(shù)據(jù)，比如分類、菜單、論壇帖子樹狀回復(fù)等。常用的方法有兩種：

1. 領(lǐng)接表的方式；

2. 預(yù)排序遍歷樹方式；

假設(shè)樹狀結(jié)構(gòu)如下圖：

領(lǐng)接表方式

主要依賴于一個 parent 字段，用于指向上級節(jié)點，將相鄰的上下級節(jié)點連接起來，id 為自動遞增自動，parent_id 為上級節(jié)點的 id。一目了然，“Java”是“Language”的子節(jié)點。

我們要顯示樹，php 代碼也可以很直觀，代碼如下：
復(fù)制代碼 代碼如下:
<?php
/**
 * 獲取父節(jié)點下的所有子節(jié)點
 *
 * @since 2011-05-18
 *
 * @param $parent_id 父節(jié)點 id，0 則顯示整個樹結(jié)構(gòu)。
 * @param $level 當(dāng)前節(jié)點所處的層級，用于縮進(jìn)顯示節(jié)點。
 * @return void
 */
function show_children ($parent_id = 0, $level = 0)
{
    // 獲取父節(jié)點下的所有子節(jié)點
    $result = mysql_query('SELECT id, name FROM tree WHERE parent_id=' . intval($parent_id));
    // 顯示每個子節(jié)點
    while ($row = mysql_fetch_array($result)) {
        // 縮進(jìn)顯示
        echo '<div style="margin-left:' . ($level * 12) . 'px">' . $row['name'] . '</div>';
        // 遞歸調(diào)用當(dāng)前函數(shù)，顯示再下一級的子節(jié)點
        show_children($row['id'], $level + 1);
    }
}
?>

想要顯示整個樹結(jié)構(gòu)，調(diào)用 show_children()。想要顯示“Database”子樹，則調(diào)用 show_children(2)，因為“Database”的 id 是 2。

還有一個經(jīng)常用到的功能是獲取節(jié)點路徑，即給出一個節(jié)點，返回從根節(jié)點到當(dāng)前節(jié)點的路徑。用函數(shù)實現(xiàn)如下：
復(fù)制代碼 代碼如下:
<?php
/**
 * @param $id 需要獲取路徑的當(dāng)前節(jié)點的 id。
 * @return array
 */
function get_path($id)
{
    // 獲取當(dāng)前節(jié)點的父節(jié)點 id 和當(dāng)前節(jié)點名
    $result = mysql_query('SELECT parent_id, name FROM tree WHERE id='.intval($id));
    $row = mysql_fetch_array($result);
    // 使用此數(shù)組保存路徑
    $path = array();
    // 將當(dāng)前節(jié)點名保存進(jìn)路徑數(shù)組中
    $path[] = $row['name'];
    // 如果父節(jié)點非 0，即非根節(jié)點，則進(jìn)行遞歸調(diào)用獲取父節(jié)點的路徑
    if ($row['parent_id']) {
        // 遞歸調(diào)用，獲取父節(jié)點的路徑，并且合并到當(dāng)前路徑數(shù)組的其它元素前邊
        $path = array_merge(get_path($row['parent_id']), $path);
    }
    return $path;
}
?>

想要獲取“MySQL 5.0”的路徑，調(diào)用 get_path(4)，4 即是這個節(jié)點的 id。

領(lǐng)接表方式的優(yōu)點在于容易理解，代碼也比較簡單明了。缺點則是遞歸中的 SQL 查詢會導(dǎo)致負(fù)載變大，特別是需要處理比較大型的樹狀結(jié)構(gòu)的時候，查詢語句會隨著層級的增加而增加，WEB 應(yīng)用的瓶頸基本都在數(shù)據(jù)庫方面，所以這是一個比較致命的缺點，直接導(dǎo)致樹結(jié)構(gòu)的擴(kuò)展困難重重。

排序遍歷樹方式

現(xiàn)在我們來聊聊第二種方式─預(yù)排序遍歷樹方式（即通常所說的 MPTT，Modified Preorder Tree Traversal）。此算法是在第一種方式的基礎(chǔ)之上，給每個節(jié)點增加一個左、右數(shù)字，用于標(biāo)識節(jié)點的遍歷順序，如下圖所示：

從根節(jié)點開始左邊為 1，然后下一個節(jié)點的左邊為 2，以此類推，到最低層節(jié)點之后，最低層節(jié)點的右邊為其左邊的數(shù)字加 1。順著這些節(jié)點，我們可以很容易地遍歷完整個樹。根據(jù)上圖，我們對數(shù)據(jù)表做一些改變，增加兩個字段，lft 和 rgt 用于存儲左右數(shù)字（由于 left 和 right 是 MySQL 的保留字，所以我們改用簡寫）。表中各行的內(nèi)容也就變成了：

接下來看看顯示樹/子樹是多么簡單，只需要一條 SQL 語句即可，比如顯示“Database”子樹，則需要獲取到“Database”的左右數(shù)字，左為 2，右為 11，那么 SQL 語句是：

復(fù)制代碼 代碼如下:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

SQL 語句是簡單了，但我們所希望的縮進(jìn)顯示卻是個問題。什么時候應(yīng)該顯示縮進(jìn)？縮進(jìn)多少單位？解決這個問題，需要使用堆棧，即后進(jìn)先出（LIFO），每到一個節(jié)點，將其右邊的數(shù)字壓入堆棧中。我們知道，所有節(jié)點右邊的值都比其父節(jié)點右邊的值小，那么將當(dāng)前節(jié)點右邊的值和堆棧最上邊的右邊值進(jìn)行比較，如果當(dāng)前節(jié)點比堆棧最上邊的值小，表示當(dāng)前堆棧里邊剩下的都是父節(jié)點了，這時可以顯示縮進(jìn)，堆棧的元素數(shù)量即是縮進(jìn)深度。php 代碼實現(xiàn)如下：
復(fù)制代碼 代碼如下:
<?php
/**
 * @param $root_id 需要顯示的樹/子樹根節(jié)點 id。
 */
function show_tree($root_id = 1)
{
    // 獲取當(dāng)前根節(jié)點的左右數(shù)值
    $result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($root_id));
    $row = mysql_fetch_array($result);
    // 堆棧，存儲節(jié)點右邊的值，用于顯示縮進(jìn)
    $stack = array();
    // 獲取 $root_id 節(jié)點的所有子孫節(jié)點
    $result = mysql_query('SELECT name, lft, rgt FROM tree WHERE lft BETWEEN '.$row['lft'].' AND '.$row['rgt'].' ORDER BY lft ASC');
    // 顯示樹的每個節(jié)點
    while ($row = mysql_fetch_array($result)) {
        if (count($stack)>0) { //僅當(dāng)堆棧非空的時候檢測
            // 如果當(dāng)前節(jié)點右邊的值比堆棧最上邊的值大，則移除堆棧最上邊的值，因為這個值對應(yīng)的節(jié)點不是當(dāng)前節(jié)點的父節(jié)點
            while ($row['rgt'] > $stack[count($stack)-1]) {
                array_pop($stack);
            } //while 循環(huán)結(jié)束之后，堆棧里邊只剩下當(dāng)前節(jié)點的父節(jié)點了
        }
        // 現(xiàn)在可以顯示縮進(jìn)了
        echo '<div style="margin-left:'.(count($stack)*12).'px">'.$row['name'].'</div>';
        // 將當(dāng)前的節(jié)點壓入堆棧里邊，為循環(huán)后邊的節(jié)點縮進(jìn)顯示做好準(zhǔn)備
        array_push($stack, $row['rgt']);
    }
}
?>

獲取整個樹調(diào)用 show_tree()，獲取“Database”子樹調(diào)用show_tree(2)。在這個函數(shù)中，我們總算不需要用到遞歸了，呵呵。

接下來是顯示從根節(jié)點到某節(jié)點的路徑，這比起領(lǐng)接表方式來說也簡單了很多，只需要一句 SQL 就行，不用遞歸  比如獲取“ORACLE”這個節(jié)點的路徑，其左右值分別是 7 和 10，則 SQL 語句為：
復(fù)制代碼 代碼如下:
SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;

php 函數(shù)實現(xiàn)如下：

復(fù)制代碼 代碼如下:
<?php
/**
 * @param $node_id 需要獲取路徑的節(jié)點 id
 */
function get_path2($node_id) {
    // 獲取當(dāng)前節(jié)點的左右值
    $result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($node_id));
    $row = mysql_fetch_array($result);
    // 獲取路徑中的所有節(jié)點
    $result = mysql_query('SELECT name FROM tree WHERE lft <= '.$row['lft'].' AND rgt >= '.$row['rgt'].' ORDER BY lft ASC');
    $path = array();
    while ($row = mysql_fetch_array($result)) {
        $path[] = $row['name'];
    }
    return $path;
}
?>

顯示樹和路徑都沒問題了，現(xiàn)在需要了解一下如何插入一個節(jié)點。插入新節(jié)點之前，首先要給這個節(jié)點騰出空位來，假設(shè)我們現(xiàn)在要在“ORACLE 9i”這個節(jié)點右邊增加一個“ORACLE 10”，則騰位的 SQL 語句如下（“ORACLE 9i”的右邊值為 9）：

復(fù)制代碼 代碼如下:
UPDATE tree SET rgt=rgt+2 WHERE rgt>9;
UPDATE tree SET lft=lft+2 WHERE lft>9;

位置空出來了，開始插入新節(jié)點吧：
復(fù)制代碼 代碼如下:
INSERT INTO tree SET lft=10, rgt=11, name='ORACLE 10';

調(diào)用 show_tree() 看看結(jié)果對不對  具體的 php 實現(xiàn)代碼這里就不寫了。

現(xiàn)在總結(jié)一下預(yù)排序遍歷樹方式的優(yōu)缺點。缺點是算法比較抽象，不容易理解，增加節(jié)點的時候雖然只用了幾條 SQL 語句，但可能會需要更新很多記錄，從而造成阻塞。優(yōu)點是樹的構(gòu)造，路徑獲取方面性能都比領(lǐng)接表方式好很多。也就是說，這個算法犧牲了一些寫的性能來換取讀的性能，在 WEB 應(yīng)用中，讀數(shù)據(jù)庫的比例遠(yuǎn)大于寫數(shù)據(jù)庫的比例，所以預(yù)排序遍歷樹方式比領(lǐng)接表方式更加受歡迎，更加實用，很多應(yīng)用中都能看到 MPTT 的影子，通常所用的表里都有字段 lft 和 rgt。

php技術(shù)：PHP+Mysql樹型結(jié)構(gòu)（無限分類）數(shù)據(jù)庫設(shè)計的2種方式實例，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。