我們經常需要在關系型數據庫中保存一些樹狀結構數據，比如分類、菜單、論壇帖子樹狀回復等。常用的方法有兩種：
1. 領接表的方式；
2. 預排序遍歷樹方式；
假設樹狀結構如下圖：
領接表方式
主要依賴于一個 parent 字段，用于指向上級節點，將相鄰的上下級節點連接起來，id 為自動遞增自動，parent_id 為上級節點的 id。一目了然，“Java”是“Language”的子節點。
我們要顯示樹，PHP 代碼也可以很直觀，代碼如下：
<?php
/**
* 獲取父節點下的所有子節點
*
* @since 2011-05-18
*
* @param $parent_id 父節點 id，0 則顯示整個樹結構。
* @param $level 當前節點所處的層級，用于縮進顯示節點。
* @return void
*/
function show_children ($parent_id = 0, $level = 0)
{
// 獲取父節點下的所有子節點
$result = mysql_query('SELECT id, name FROM tree WHERE parent_id=' . intval($parent_id));
// 顯示每個子節點
while ($row = mysql_fetch_array($result)) {
// 縮進顯示
echo '<div style="margin-left:' . ($level * 12) . 'px">' . $row['name'] . '</div>';
// 遞歸調用當前函數，顯示再下一級的子節點
show_children($row['id'], $level + 1);
}
}
?>
想要顯示整個樹結構，調用 show_children()。想要顯示“Database”子樹，則調用 show_children(2)，因為“Database”的 id 是 2。
還有一個經常用到的功能是獲取節點路徑，即給出一個節點，返回從根節點到當前節點的路徑。用函數實現如下：
<?php
/**
* @param $id 需要獲取路徑的當前節點的 id。
* @return array
*/
function get_path($id)
{
// 獲取當前節點的父節點 id 和當前節點名
$result = mysql_query('SELECT parent_id, name FROM tree WHERE id='.intval($id));
$row = mysql_fetch_array($result);
// 使用此數組保存路徑
$path = array();
// 將當前節點名保存進路徑數組中
$path[] = $row['name'];
// 如果父節點非 0，即非根節點，則進行遞歸調用獲取父節點的路徑
if ($row['parent_id']) {
// 遞歸調用，獲取父節點的路徑，并且合并到當前路徑數組的其它元素前邊
$path = array_merge(get_path($row['parent_id']), $path);
}
return $path;
}
?>
想要獲取“MySQL 5.0”的路徑，調用 get_path(4)，4 即是這個節點的 id。
領接表方式的優點在于容易理解，代碼也比較簡單明了。缺點則是遞歸中的 SQL 查詢會導致負載變大，特別是需要處理比較大型的樹狀結構的時候，查詢語句會隨著層級的增加而增加，WEB 應用的瓶頸基本都在數據庫方面，所以這是一個比較致命的缺點，直接導致樹結構的擴展困難重重。
排序遍歷樹方式
現在我們來聊聊第二種方式─預排序遍歷樹方式（即通常所說的 MPTT，Modified Preorder Tree Traversal）。此算法是在第一種方式的基礎之上，給每個節點增加一個左、右數字，用于標識節點的遍歷順序，如下圖所示：
從根節點開始左邊為 1，然后下一個節點的左邊為 2，以此類推，到最低層節點之后，最低層節點的右邊為其左邊的數字加 1。順著這些節點，我們可以很容易地遍歷完整個樹。根據上圖，我們對數據表做一些改變，增加兩個字段，lft 和 rgt 用于存儲左右數字（由于 left 和 right 是 MySQL 的保留字，所以我們改用簡寫）。表中各行的內容也就變成了：
接下來看看顯示樹/子樹是多么簡單，只需要一條 SQL 語句即可，比如顯示“Database”子樹，則需要獲取到“Database”的左右數字，左為 2，右為 11，那么 SQL 語句是：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
SQL 語句是簡單了，但我們所希望的縮進顯示卻是個問題。什么時候應該顯示縮進？縮進多少單位？解決這個問題，需要使用堆棧，即后進先出（LIFO），每到一個節點，將其右邊的數字壓入堆棧中。我們知道，所有節點右邊的值都比其父節點右邊的值小，那么將當前節點右邊的值和堆棧最上邊的右邊值進行比較，如果當前節點比堆棧最上邊的值小，表示當前堆棧里邊剩下的都是父節點了，這時可以顯示縮進，堆棧的元素數量即是縮進深度。PHP 代碼實現如下：
<?php
/**
* @param $root_id 需要顯示的樹/子樹根節點 id。
*/
function show_tree($root_id = 1)
{
// 獲取當前根節點的左右數值
$result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($root_id));
$row = mysql_fetch_array($result);
// 堆棧，存儲節點右邊的值，用于顯示縮進
$stack = array();
// 獲取 $root_id 節點的所有子孫節點
$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)) {
if (count($stack)>0) { //僅當堆棧非空的時候檢測
// 如果當前節點右邊的值比堆棧最上邊的值大，則移除堆棧最上邊的值，因為這個值對應的節點不是當前節點的父節點
while ($row['rgt'] > $stack[count($stack)-1]) {
array_pop($stack);
} //while 循環結束之后，堆棧里邊只剩下當前節點的父節點了
}
// 現在可以顯示縮進了
echo '<div style="margin-left:'.(count($stack)*12).'px">'.$row['name'].'</div>';
// 將當前的節點壓入堆棧里邊，為循環后邊的節點縮進顯示做好準備
array_push($stack, $row['rgt']);
}
}
?>
獲取整個樹調用 show_tree()，獲取“Database”子樹調用show_tree(2)。在這個函數中，我們總算不需要用到遞歸了，呵呵。
接下來是顯示從根節點到某節點的路徑，這比起領接表方式來說也簡單了很多，只需要一句 SQL 就行，不用遞歸 比如獲取“ORACLE”這個節點的路徑，其左右值分別是 7 和 10，則 SQL 語句為：
SELECT name FROM tree WHERE lft <= 7 AND rgt >= 10 ORDER BY lft ASC;
PHP 函數實現如下：
<?php
/**
* @param $node_id 需要獲取路徑的節點 id
*/
function get_path2($node_id) {
// 獲取當前節點的左右值
$result = mysql_query('SELECT lft, rgt FROM tree WHERE id='.intval($node_id));
$row = mysql_fetch_array($result);
// 獲取路徑中的所有節點
$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;
}
?>
顯示樹和路徑都沒問題了，現在需要了解一下如何插入一個節點。插入新節點之前，首先要給這個節點騰出空位來，假設我們現在要在“ORACLE 9i”這個節點右邊增加一個“ORACLE 10”，則騰位的 SQL 語句如下（“ORACLE 9i”的右邊值為 9）：
UPDATE tree SET rgt=rgt+2 WHERE rgt>9;
UPDATE tree SET lft=lft+2 WHERE lft>9;
位置空出來了，開始插入新節點吧：
INSERT INTO tree SET lft=10, rgt=11, name='ORACLE 10';
調用 show_tree() 看看結果對不對 具體的 PHP 實現代碼這里就不寫了。
現在總結一下預排序遍歷樹方式的優缺點。缺點是算法比較抽象，不容易理解，增加節點的時候雖然只用了幾條 SQL 語句，但可能會需要更新很多記錄，從而造成阻塞。優點是樹的構造，路徑獲取方面性能都比領接表方式好很多。也就是說，這個算法犧牲了一些寫的性能來換取讀的性能，在 WEB 應用中，讀數據庫的比例遠大于寫數據庫的比例，所以預排序遍歷樹方式比領接表方式更加受歡迎，更加實用，很多應用中都能看到 MPTT 的影子，通常所用的表里都有字段 lft 和 rgt。
