從喜悅村上轉載，以前也讀過此文，講述得還是比較清楚的。
產品分類，多層次的樹狀結構的論壇，郵件列表等許多地方我們都會遇到這樣的問題：如何儲存多層次結構的資料？
在PHP的應用中，提供後台資料儲存的通常是關係型資料庫，它能夠保存大量的數據，提供高效率的資料檢索和更新服務。然而關係型資料的基本形式是縱橫交錯的表，是一個平面的結構，如果要將多層次樹狀結構儲存在關係型資料庫中就需要進行合理的翻譯工作。接下來我會將自己的所見所聞和一些實用的經驗和大家探討。
層級結構的資料保存在平面的資料庫中基本上有兩種常用設計方法：
毗鄰目錄模式(adjacency list model)
預先排序遍歷樹演算法(modified preorder tree traversal algorithm)
我不是電腦專業的，也沒有學過什麼資料結構的東西，所以這兩個名字都是我自己按照字面的意思翻的，如果說錯了還請多多指教。
這兩個東西聽起來好像很嚇人，其實非常容易理解。這裡我用一個簡單食品目錄作為我們的範例資料。 我們的資料結構是這樣的:
Food
|
|---Fruit
| |
| |---Red
| | |
| | |--Cherry
| |
| |---Yellow
| |
| |--Banana
|
|---Meat
|
|--Beef
|
|--Pork
為了照顧那些英文一塌糊塗的PHP愛好者
Food:食物
Fruit:水果
Red:紅色
Cherry:櫻桃
Yellow:黃色
Banana:香蕉
Meat:肉類
Beef:牛肉
Pork:豬肉
毗鄰目錄模式(adjacency list model)
這種模式我們常用到，很多的教學和書中也介紹過。我們透過為每個節點增加一個屬性parent 來表示這個節點的父節點從而將整個樹狀結構透過平面的表格描述出來。根據這個原則，範例中的資料可以轉換成如下的表：
+-----------------------+
| parent | name |
+----------------------+
| | Food |
| Food | Fruit |
| Fruit | 綠 |
| Green | Pear |
| Fruit | Red |
| Red | Cherry |
| Fruit | Yellow |
| Yellow | Banana |
| Food | Meat |
| Meat | Beef |
| Meat | Pork |
+----------------------+
我們看到Pear 是Green的一個子節點，Green是Fruit的一個子節點。而根節點'Food'沒有父節點。 為了簡單地描述這個問題， 這個例子只用了name來表示一個記錄。 在實際的資料庫中，你需要用數字的id來標示每個節點，資料庫的表結構大概應該像這樣：id, parent_id, name, description。有了這樣的表我們就可以透過資料庫保存整個多層次樹狀結構了。
顯示多層次樹如果我們需要顯示這樣的一個多層次結構需要一個遞歸函數。
<?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)
{
// 取得一個父節點$parent 的所有子節點
$result = mysql_query('SELECT name FROM tree '.
'WHERE parent="'.$parent.'";');
// 顯示每個子節點
while ($row = mysql_fetch_array($result))
{
// 縮排顯示節點名稱
echo str_repeat(' ',$level).$row['name']."n";
//再次呼叫這個函數顯示子節點的子節點
display_children($row['name'], $level+1);
}
}
?>
對整個結構的根節點（Food）使用這個函數就可以列印出整個多層樹結構，由於Food是根節點它的父節點是空的，所以這樣呼叫: display_children('',0)。將顯示整個樹的內容：
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
如果你只想顯示整個結構中的一部分，比如說水果部分，就可以這樣呼叫：
display_children('Fruit',0);
幾乎使用相同的方法我們可以知道從根節點到任意節點的路徑。例如Cherry 的路徑是"Food > Fruit > Red"。 為了得到這樣的一個路徑我們需要從最深的一級"Cherry"開始， 查詢得到它的父節點"Red"把它添加到路徑中， 然後我們再查詢Red的父節點並把它也添加到路徑中，以此類推直到最高層的"Food"
<?php
// $node 是那個最深的節點
function get_path($node)
{
// 查詢這個節點的父節點
$result = mysql_query('SELECT parent FROM tree '.
'WHERE name="'.$node.'";');
$row = mysql_fetch_array($result);
// 用一個陣列儲存路徑
$path = array();
// 如果不是根節點則繼續向上查詢
// (根節點沒有父節點)
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;
}
?>
如果對"Cherry"使用這個函數：print_r(get_path('Cherry'))，就會得到這樣的一個陣列了：
Array
(
[0] => Food
[1] => Fruit
[2] => Red
)
接下來如何把它印成你希望的格式，就是你的事情了。
缺點：這種方法很簡單，容易理解，好上手。但是也有一些缺點。主要是因為運行速度很慢，由於得到每個節點都需要進行資料庫查詢，資料量大的時候要進行很多查詢才能完成一個樹。另外由於要進行遞歸運算，遞迴的每一級都需要佔用一些記憶體所以在空間利用上效率也比較低。
現在讓我們來看看另外一種不使用遞歸計算，更加快速的方法，這就是預排序遍歷樹算法(modified preorder tree traversal algorithm) 這種方法大家可能接觸的比較少，初次使用也不像上面的方法很容易理解，但是由於這種方法不使用遞歸查詢演算法，因此有更高的查詢效率。
我們先將多層次資料按照下面的方式畫在紙上，在根節點Food的左側寫上1 然後沿著這個樹繼續向下在Fruit 的左側寫上2 然後繼續前進，沿著整個樹的邊緣給每一個節點都標上左側和右側的數字。最後一個數字是標示在Food 右側的18。 在下面的這張圖中你可以看到整個標好了數字的多層結構。 （沒看懂？用你的手指指著數字從1數到18就明白怎麼回事了。還不明白，再數一遍，注意要移動你的手指）。
這些數字標示了各個節點之間的關係，"Red"的號碼是3和6，它是"Food" 1-18 的子孫節點。 同樣，我們可以看到所有左值大於2和右值小於11的節點都是"Fruit" 2-11 的子孫節點
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
這樣整個樹狀結構可以透過左右值來儲存到資料庫中。繼續之前，我們先來看看下面整理過的資料表。
+-----------------------+-----+-----+
| 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"來表示左右字段。 另外這種結構中不再需要"parent"欄位來表示樹狀結構。也就是說下面這樣的表結構就夠了。
+------------+-----+-----+
| 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 |
+------------+-----+-----+
好了我們現在可以從資料庫中取得資料了，例如我們需要得到"Fruit"項下的所有所有節點就可以這樣寫查詢語句： SELECT * FROM tree WHERE lft BETWEEN 2 AND 11; 這個查詢得到了以下的結果。
+------------+-----+-----+
| name | lft | rgt |
+------------+-----+-----+
| Fruit | 2 | 11 |
| Red | 3 | 6 |
| Cherry | 4 | 5 |
| Yellow | 7 | 10 |
| Banana | 8 | 9 |
+------------+-----+-----+
看到了吧，只要一個查詢就可以得到所有這些節點。為了能夠像上面的遞歸函數一樣顯示整個樹狀結構，我們還需要對這樣的查詢進行排序。以節點的左值排序：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
剩下的問題如何顯示層級的縮排了。
<?php
function display_tree($root)
{
// 得到根節點的左右值
$result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE name="'.$root.'";');
$row = mysql_fetch_array($result);
// 準備一個空的右值堆疊
$right = array();
// 取得根基點的所有子孫節點
$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)
{
// 檢查我們是否應該將節點移出堆疊
while ($right[count($right)-1]<$row['rgt'])
{
array_pop($right);
}
}
// 縮排顯示節點的名稱
echo str_repeat(' ',count($right)).$row['name']."n";
// 將這個節點加入到堆疊中
$right[] = $row['rgt'];
}
}
?>
如果你運行一下以上的函數就會得到和遞歸函數一樣的結果。只是我們的這個新的函數可能會更快一些，因為只有2次資料庫查詢。 要獲知一個節點的路徑就更簡單了，如果我們想知道Cherry 的路徑就利用它的左右值4和5來做一個查詢。
SELECT name FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
這樣就會得到以下的結果：
+------------+
| name |
+------------+
| Food |
| Fruit |
| Red |
+------------+
那麼某個節點到底有多少子孫節點呢？很簡單，子孫總數=(右值-左值-1)/2 descendants = (right – left - 1) / 2 不相信？自己算一算啦。用這個簡單的公式，我們可以很快的算出"Fruit 2-11"節點有4個子孫節點，而"Banana 8-9"節點沒有子孫節點，也就是說它不是一個父節點了。
很神奇吧？雖然我已經多次使用這個方法，但是每次這樣做的時候還是感到很神奇。
這的確是個很好的辦法，但是有什麼辦法可以幫我們建立這樣有左右值的資料表呢？這裡再介紹一個函數給大家，這個函數可以將name和parent結構的表自動轉換成有左右值的資料表。
<?php
function rebuild_tree($parent, $left) {
// the right value of this node is the left value + 1
$right = $left+1;
// get all children of this node
$result = mysql_query('SELECT name FROM tree '.
'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result)) {
// recursive execution of this function for each
// child of this node
// $right is the current right value, which is
// incremented by the rebuild_tree function
$right = rebuild_tree($row['name'], $right);
}
// we've got the left value, and now that we've processed
// the children of this node we also know the right value
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE name="'.$parent.'";');
// return the right value of this node + 1
return $right+1;
}
?>
當然這個函數是遞歸函數，我們需要從根節點開始執行這個函數來重建一個有左右值的樹
rebuild_tree('Food',1);
這個函數看起來有些複雜，但是它的作用和手工對錶進行編號一樣，就是將立體多層結構的轉換成一個帶有左右值的資料表。
那麼對於這樣的結構我們該如何增加，更新刪除一個節點呢？ 增加一個節點一般有兩種方法：
保留原有的name 和parent結構，用老方法向數據添加數據，每增加一條數據以後使用rebuild_tree函數對整個結構重新進行一次編號。
效率更高的辦法是改變所有位於新節點右側的數值。舉例來說：我們想增加一種新的水果"Strawberry"（草莓）它將成為"Red"節點的最後一個子節點。首先我們需要為它騰出一些空間。 "Red"的右邊值應從6改成8，"Yellow 7-10 "的左右值則應改成9-12。 依次類推我們可以得知，如果要給新的值騰出空間需要給所有左右值大於5的節點（5 是"Red"最後一個子節點的右值） 加上2。 所以我們這樣進行資料庫操作：
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
這樣就為新插入的值騰出了空間，現在可以在騰出的空間裡建立一個新的資料節點了， 它的左右值分別是6和7
INSERT INTO tree SET lft=6, rgt=7, name ='Strawberry';
再做一次查詢看看吧！怎麼樣？很快吧。
好了，現在你可以用兩種不同的方法設計你的多層資料庫結構了，採用何種方式完全取決於你個人的判斷，但是對於層次多數量大的結構我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數據，則第一種方法更為簡單。
另外，如果資料庫支援的話你還可以將rebuild_tree() 和騰出空間的操作寫成資料庫端的觸發器函數， 在插入和更新的時候自動執行， 這樣可以得到更好的運作效率， 而且你加入新節點的SQL語句會變得更簡單。
類別遞迴法
Posted by 訪客on 2004, May 31 - 9:18am.
我用類遞歸法寫了段程序，跟文章中的遞歸不完全一樣正準備移植到xoops 中:
http://dev.xoops.org/modules/xfmod/project/?ulink
已經出現內存溢出現像不過準備繼續採用遞歸法，只是需要繼續改進
希望有機會跟各位討論cms
» reply to this comment
還是兩種方法之比較
Posted by 訪客on 2004, March 17 - 8:30pm.
仔細研究了一下這篇文章，覺得受益非淺，但後來又想了想，覺得有一下問題（為了好記憶，毗鄰目錄模式我稱為遞歸的方法，預排序遍歷樹算法我稱為預排序樹的方法）：
1、兩種方法比較大的差別是遞歸是在查詢的時候要用到堆疊進行遞歸，預排序樹則是在更新節點時要進行半數（指所插入節點的後半部）節點的更新。雖然您也說了，如果節點多了，更新又頻繁，預排序樹效率會降低，採用遞歸會好些，而如果節點層次較多的話，首先遞歸會導致堆疊溢出，再者遞歸本身效率就不高，加上每一層遞歸都要操作資料庫，整體效果也不會理想。我目前的做法是一次性把資料全取出來，然後對數組進行遞歸操作，會好一些；再進一步改進的話，可以為每行記錄增加一個ROOT根節點（目前是只記錄相鄰的父節點） ，這樣在找分支樹時效率就會比較高了，更新樹的時候也是十分便捷的，應該是比較好的方式。
2.改進遞歸的方式，文章中在計算預排序樹節點的左右值的時候其實也用到了一種遍歷方式，透過數組替代堆疊，手工實現壓棧和彈出；這種方法如果引用到遞歸算法中，在進行遞歸的時候也用數組取代堆疊的話，也可以提高遞歸的效率的。
3.並發，如果考慮到並發的情況，尤其是更新樹的時候，預排序樹大面積更新節點資訊的方法需要額外注意採用加鎖和事務的機制保證資料一致性。
4.多根節點或多父節點的情況，在這種情況下，顯然就不是一個標準的二元樹或者多叉樹了，預排序樹演算法需要進行比較大的改進才能適應，而遞歸的方法則應用自如，所以在這種情況下，遞迴的適應性較強。這是當然的了，因為遞歸的方法就是鍊錶的一種形式，樹、圖都可以用鍊錶來表達，當然適應力強了。
5.直觀，如果不用程式操作，直接觀察資料庫中儲存的資料的話，顯然遞歸方式下儲存的資料比較直觀，而預排序樹的資料很難直接閱讀（針對層次關係來說），這在資料交換中是不是會有影響呢？
整體來說，我個人比較喜歡用遞歸的方法，但一直擔心遞歸對效率的影響，所幸還沒有接觸過規模較大的分類層次，遞歸用數組替代堆疊會是一種比較好的改進方法。而預排序樹不失為一種解決簡單樹的高效方法，用習慣了，也應該是非常出色的，尤其是它從葉子節點到根節點的反向查找非常方便。
Fwolf
www.fwolf.com
» reply to this comment
非常高興看到你的回复
Posted by shuke on 2004, March 18 - 5:47am.
非常高興你這麼認真的讀完這篇文章。這篇文章其實是原來發表在sitepoint.com上的，我把它翻譯了一下，希望給希望初學入門的朋友介紹一些方法，拋磚引玉。你的方法也很好，有機會我會試試看的。 （如果你有興趣的話，何不就上面的例子把你的方法和具體實現的代碼也寫成教程發出來吧，這樣大家就用更加實際的例子來模仿了）如果你對數據庫中保存多級結構有興趣研究的話，這裡還有兩個連結也很不錯可以當參考：
介紹了常見的4中方法一次查詢，數組排序的腳本我想你的腳本肯定比這個強。
另外我看到你也用drupal，它還有一個進階功能叫做分散式使用者驗證系統，只要在任何一個drupal的網站註冊以後就可以登入存取其它的drupal網站了。挺有意思的。
祝好！
» reply to this comment
用循環來建樹已經實現了
Posted by 訪客on 2004, March 25 - 10:10pm.
你上次提供的資料我已經都看過了，不過老實說，第一篇文章裡沒有太多新東西，或許是我沒看太明白吧，第二個居然是PHP3寫的，程序結構沒有細看，用到太多的函數交叉。
正好我在一個系統中用戶角色要用到分級，按照數組的思路就把遍歷寫了下來，沒有時間整理，先放到這裡你看看吧，數據庫用的是ADODB，程序是直接從系統中摘出來的，希望能夠描述得清楚，主要是利用了PHP強大的數組操作，用循環來進行遞歸。註記裡是一種相近的方法，只是處理結果的時機不同而已。
<?php
/**
* 顯示列表
* @access public
*/
function DispList()
{
//不縮排的顯示方式
// $this->mIsDispListIndex = true;
// echo('<p align="right"><a href="?action=new&part=role">增加新角色</a> </p>'); _fcksavedurl=""?action=new&part=role ">增加新角色</a> </p>');"
//
// $this->mListTitle = '使用者角色清單';
// $this->SetDataOption('list');
//
// $this->SetQueryTable( array($this->mTableUserRole) );
//
// //查詢順序
// $this->SetQueryOrder( 'asc', $this->mTableUserRole, 'sequence' );
//
// $this->Query('list');
// parent::DispList();
// //另一個顯示方式，用陣列當堆疊，A: 壓棧時存role，壓完就刪除source
// $this->CheckProperty('mrDb');
// $this->CheckProperty('mrSql');
// $this->mrSql->Select('role, title, parent');
// $this->mrSql->From($this->mTableUserRole);
// $this->mrSql->Orderby('parent, sequence');
// $this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
// if (0 < count($this->mRs))
// {
// $source = & $this->mRs->GetArray(); //數位索引
// $stack = array(''); //堆疊
// $stacki = array(-1); //和堆疊對應，記錄堆疊中資料在樹中的層次
// $target = array();
// while (0 < count($stack))
// {
// $item = array_shift($stack);
// $lev = array_shift($stacki);
// if (!empty($item))
// {
// //在這裡把加工過的資料放到target數組
// array_push($target, str_repeat(' ', $lev) . $item);
// //$s1 = str_repeat(' ', $lev) . $item;
// }
// $del = array(); //要從$source刪除的節點
// $ar = array(); //需要加入堆疊中的節點
// foreach ($source as $key=>$val)
// {
// //尋找符合的子節點
// if (empty($item))
// {
// $find = empty($source[$key]['parent']);
// }
// else
// {
// $find = ($item == $source[$key]['parent']);
// }
// if ($find)
// {
// array_unshift($ar, $source[$key]['role']);
// $del[] = $key;
// }
// }
// foreach ($ar as $val)
// {
// array_unshift($stack, $val);
// array_unshift($stacki, $lev + 1);
// }
// foreach ($del as $val)
// {
// unset($source[$val]);
// }
// echo(implode(', ', $stack) . '<br />' . implode(', ', $stacki) . '<br />' . implode(', ', $target) . '< br /><br />');
// }
// debug_array();
// }
// else
// {
// echo('<center>沒有檢索到資料</center>');
// }
//另一個顯示方式，用陣列當堆疊，B: 壓棧時存數組索引，出棧並使用完後再刪除source
$this->CheckProperty('mrDb');
$this->CheckProperty('mrSql');
$this->mrSql->Select('role, title, parent');
$this->mrSql->From($this->mTableUserRole);
$this->mrSql->Orderby('parent, sequence');
$this->mRs = $this->mrDb->Execute($this->mrSql->Sql());
if (!empty($this->mRs) && !$this->mRs->EOF)
{
$source = & $this->mRs->GetArray(); //數位索引
$stack = array(-1); //堆疊
$stacki = array(-1); //和堆疊對應，記錄堆疊中資料在樹中的層次
$target = array();
while (0 < count($stack))
{
$item = array_shift($stack);
$lev = array_shift($stacki);
if (-1 != $item)
{
//在這裡把加工過的資料放到target數組
$s1 = str_repeat(' ', $lev) . '<a href="?action=disp&part=role&role=' . $source[$item]['role'] . '">' . $source[$item] ['title'] . '</a>';
$s2 = '<a href="?action=edit&part=role&role=' . $source[$item]['role'] . '">編輯</a> <a href="?action=delete&part=role&role= ' . $source[$item]['role'] . '">刪除</a>';
array_push($target, array($s1, $s2));
}
$del = array(); //要從$source刪除的節點
$ar = array(); //需要加入堆疊中的節點
foreach ($source as $key=>$val)
{
//尋找符合的子節點
if (-1 == $item)
{
$find = empty($source[$key]['parent']);
}
else
{
$find = ($source[$item]['role'] == $source[$key]['parent']);
}
if ($find)
{
array_unshift($ar, $key);
}
}
foreach ($ar as $val)
{
array_unshift($stack, $val);
array_unshift($stacki, $lev + 1);
}
//從source中刪除
unset($source[$item]);
//echo(implode(', ', $stack) . '<br />' . implode(', ', $stacki) . '<br />' . implode(', ', $target) . '< br /><br />');
}
//輸出
echo('<p align="right"><a href="?action=new&part=role">增加新角色</a> </p>');
array_unshift($target, array('角色', '操作'));
$this->CheckProperty('mrLt');
$this->mrLt->SetData($target);
$this->mrLt->mListTitle = '使用者角色清單';
$this->mrLt->mIsDispIndex = false;
$this->mrLt->Disp();
}
else
{
echo('<center>沒有檢索到資料</center>');
}
} // end of function DispList
?>