幾篇關(guān)于無限分類算法的文章第2/5頁
http://www.nirvanastudio.org/php/hierarchical-data-database.html
中文翻譯
在數(shù)據(jù)庫中存儲層次數(shù)據(jù)
作者:Gijs Van Tulder
翻譯:ShiningRay @ NirvanaStudio
無論你要構(gòu)建自己的論壇,在你的網(wǎng)站上發(fā)布消息還是書寫自己的cms [1]程序,你都會遇到要在數(shù)據(jù)庫中存儲層次數(shù)據(jù)的情況。同時,除非你使用一種像XML [2]的數(shù)據(jù)庫,否則關(guān)系數(shù)據(jù)庫中的表都不是層次結(jié)構(gòu)的,他們只是一個平坦的列表。所以你必須找到一種把層次數(shù)據(jù)庫轉(zhuǎn)化的方法。
存儲樹形結(jié)構(gòu)是一個很常見的問題,他有好幾種解決方案。主要有兩種方法:鄰接列表模型和改進前序遍歷樹算法
在本文中,我們將探討這兩種保存層次數(shù)據(jù)的方法。我將舉一個在線食品店樹形圖的例子。這個食品店通過類別、顏色和品種來組織食品。樹形圖如下:
本文包含了一些代碼的例子來演示如何保存和獲取數(shù)據(jù)。我選擇PHP [3]來寫例子,因為我常用這個語言,而且很多人也都使用或者知道這個語言。你可以很方便地把它們翻譯成你自己用的語言。
鄰接列表模型(The Adjacency List Model)
我們要嘗試的第一個——也是最優(yōu)美的——方法稱為“鄰接列表模型”或稱為“遞歸方法”。它是一個很優(yōu)雅的方法因為你只需要一個簡單的方法來在你的樹中進行迭代。在我們的食品店中,鄰接列表的表格如下:
如你所見,對每個節(jié)點保存一個“父”節(jié)點。我們可以看到“Pear [4]”是“Green”的一個子節(jié)點,而后者又是“Fruit”的子節(jié)點,如此類推。根節(jié)點,“Food”,則他的父節(jié)點沒有值。為了簡單,我只用了“title”值來標識每個節(jié)點。當然,在實際的數(shù)據(jù)庫中,你要使用數(shù)字的ID。
顯示樹
現(xiàn)在我們已經(jīng)把樹放入數(shù)據(jù)庫中了,得寫一個顯示函數(shù)了。這個函數(shù)將從根節(jié)點開始——沒有父節(jié)點的節(jié)點——同時要顯示這個節(jié)點所有的子節(jié)點。對于這些子節(jié)點,函數(shù)也要獲取并顯示這個子節(jié)點的子節(jié)點。然后,對于他們的子節(jié)點,函數(shù)還要再顯示所有的子節(jié)點,然后依次類推。
也許你已經(jīng)注意到了,這種函數(shù)的描述,有一種普遍的模式。我們可以簡單地只寫一個函數(shù),用來獲得特定節(jié)點的子節(jié)點。這個函數(shù)然后要對每個子節(jié)點調(diào)用自身來再次顯示他們的子節(jié)點。這就是“遞歸”機制,因此稱這種方法叫“遞歸方法”。
<?php
// $parent 是我們要查看的子節(jié)點的父節(jié)點
// $level 會隨著我們深入樹的結(jié)構(gòu)而不斷增加,
// 用來顯示一個清晰的縮進格式
function display_children($parent, $level) {
// 獲取$parent的全部子節(jié)點
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
// 顯示每個節(jié)點
while ($row = mysql_fetch_array($result)) {
// 縮進并顯示他的子節(jié)點的標題
echo str_repeat(' ',$level).$row['title']."\n";
// 再次調(diào)用這個函數(shù)來顯著這個子節(jié)點的子節(jié)點
display_children($row['title'], $level+1);
}
}
?>
要實現(xiàn)整個樹,我們只要調(diào)用函數(shù)時用一個空字符串作為$parent
和$level = 0: display_children('',0);
函數(shù)返回了我們的食品店的樹狀圖如下:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
注意如果你只想看一個子樹,你可以告訴函數(shù)從另一個節(jié)點開始。例如,要顯示“Fruit”子樹,你只要display_children('Fruit',0);
The Path to a Node節(jié)點的路徑
利用差不多的函數(shù),我們也可以查詢某個節(jié)點的路徑如果你只知道這個節(jié)點的名字或者ID。例如,“Cherry”的路徑是“Food”>“Fruit”>“Red”。要獲得這個路徑,我們的函數(shù)要獲得這個路徑,這個函數(shù)必須從最深的層次開始:“Cheery”。但后查找這個節(jié)點的父節(jié)點,并添加到路徑中。在我們的例子中,這個父節(jié)點是“Red”。如果我們知道“Red”是“Cherry”的父節(jié)點。
<?php
// $node 是我們要查找路徑的那個節(jié)點的名字
function get_path($node) {
// 查找這個節(jié)點的父節(jié)點
$result = mysql_query('SELECT parent FROM tree '.
'WHERE title="'.$node.'";');
$row = mysql_fetch_array($result);
// 在這個array [5] 中保存數(shù)組
$path = array();
// 如果 $node 不是根節(jié)點,那么繼續(xù)
if ($row['parent']!='') {
// $node 的路徑的最后一部分是$node父節(jié)點的名稱
$path[] = $row['parent'];
// 我們要添加這個節(jié)點的父節(jié)點的路徑到現(xiàn)在這個路徑
$path = array_merge(get_path($row['parent']), $path);
}
// 返回路徑
return $path;
}
?>
這個函數(shù)現(xiàn)在返回了指定節(jié)點的路徑。他把路徑作為數(shù)組返回,這樣我們可以使用print_r(get_path('Cherry'));
來顯示,其結(jié)果是:
Array
(
[0] => Food
[1] => Fruit
[2] => Red
)
不足
正如我們所見,這確實是一個很好的方法。他很容易理解,同時代碼也很簡單。但是鄰接列表模型的缺點在哪里呢?在大多數(shù)編程語言中,他運行很慢,效率很差。這主要是“遞歸”造成的。我們每次查詢節(jié)點都要訪問數(shù)據(jù)庫。
每次數(shù)據(jù)庫查詢都要花費一些時間,這讓函數(shù)處理龐大的樹時會十分慢。
造成這個函數(shù)不是太快的第二個原因可能是你使用的語言。不像Lisp這類語言,大多數(shù)語言不是針對遞歸函數(shù)設(shè)計的。對于每個節(jié)點,函數(shù)都要調(diào)用他自己,產(chǎn)生新的實例。這樣,對于一個4層的樹,你可能同時要運行4個函數(shù)副本。對于每個函數(shù)都要占用一塊內(nèi)存并且需要一定的時間初始化,這樣處理大樹時遞歸就很慢了。
改進前序遍歷樹
現(xiàn)在,讓我們看另一種存儲樹的方法。遞歸可能會很慢,所以我們就盡量不使用遞歸函數(shù)。我們也想盡量減少數(shù)據(jù)庫查詢的次數(shù)。最好是每次只需要查詢一次。
我們先把樹按照水平方式擺開。從根節(jié)點開始(“Food”),然后他的左邊寫上1。然后按照樹的順序(從上到下)給“Fruit”的左邊寫上2。這樣,你沿著樹的邊界走啊走(這就是“遍歷”),然后同時在每個節(jié)點的左邊和右邊寫上數(shù)字。最后,我們回到了根節(jié)點“Food”在右邊寫上18。下面是標上了數(shù)字的樹,同時把遍歷的順序用箭頭標出來了。
我們稱這些數(shù)字為左值和右值(如,“Food”的左值是1,右值是18)。正如你所見,這些數(shù)字按時了每個節(jié)點之間的關(guān)系。因為“Red”有3和6兩個值,所以,它是有擁有1-18值的“Food”節(jié)點的后續(xù)。同樣的,我們可以推斷所有左值大于2并且右值小于11的節(jié)點,都是有2-11的“Food”節(jié)點的后續(xù)。這樣,樹的結(jié)構(gòu)就通過左值和右值儲存下來了。這種數(shù)遍整棵樹算節(jié)點的方法叫做“改進前序遍歷樹”算法。
在繼續(xù)前,我們先看看我們的表格里的這些值:
注意單詞“l(fā)eft”和“right”在SQL中有特殊的含義。因此,我們只能用“l(fā)ft”和“rgt”來表示這兩個列。(譯注——其實Mysql中可以用“`”來表示,如“`left`”,MSSQL中可以用“[]”括出,如“[left]”,這樣就不會和關(guān)鍵詞沖突了。)同樣注意這里我們已經(jīng)不需要“parent”列了。我們只需要使用lft和rgt就可以存儲樹的結(jié)構(gòu)。
獲取樹
如果你要通過左值和右值來顯示這個樹的話,你要首先標識出你要獲取的那些節(jié)點。例如,如果你想獲得“Fruit”子樹,你要選擇那些左值在2到11的節(jié)點。用SQL語句表達:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
這個會返回:
好吧,現(xiàn)在整個樹都在一個查詢中了。現(xiàn)在就要像前面的遞歸函數(shù)那樣顯示這個樹,我們要加入一個ORDER BY子句在這個查詢中。如果你從表中添加和刪除行,你的表可能就順序不對了,我們因此需要按照他們的左值來進行排序。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
就只剩下縮進的問題了。
要顯示樹狀結(jié)構(gòu),子節(jié)點應(yīng)該比他們的父節(jié)點稍微縮進一些。我們可以通過保存一個右值的一個棧。每次你從一個節(jié)點的子節(jié)點開始時,你把這個節(jié)點的右值添加到棧中。你也知道子節(jié)點的右值都比父節(jié)點的右值小,這樣通過比較當前節(jié)點和棧中的前一個節(jié)點的右值,你可以判斷你是不是在顯示這個父節(jié)點的子節(jié)點。當你顯示完這個節(jié)點,你就要把他的右值從棧中刪除。要獲得當前節(jié)點的層數(shù),只要數(shù)一下棧中的元素。
<?php
function display_tree($root) {
// 獲得$root節(jié)點的左邊和右邊的值
$result = mysql_query('SELECT lft, rgt FROM tree '.
'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);
// 以一個空的$right棧開始
$right = array();
// 現(xiàn)在,獲得$root節(jié)點的所有后序
$result = mysql_query('SELECT title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');
// 顯示每一行
while ($row = mysql_fetch_array($result)) {
// 檢查棧里面有沒有元素
if (count($right)>0) {
// 檢查我們是否需要從棧中刪除一個節(jié)點
while ($right[count($right)-1]<$row['rgt']) {
array_pop($right);
}
}
// 顯示縮進的節(jié)點標題
echo str_repeat(' ',count($right)).$row['title']."\n";
// 把這個節(jié)點添加到棧中
$right[] = $row['rgt'];
}
}
?>
如果運行這段代碼,你可以獲得和上一部分討論的遞歸函數(shù)一樣的結(jié)果。而這個函數(shù)可能會更快一點:他不采用遞歸而且只是用了兩個查詢
節(jié)點的路徑
有了新的算法,我們還要另找一種新的方法來獲得指定節(jié)點的路徑。這樣,我們就需要這個節(jié)點的祖先的一個列表。
由于新的表結(jié)構(gòu),這不需要花太多功夫。你可以看一下,例如,4-5的“Cherry”節(jié)點,你會發(fā)現(xiàn)祖先的左值都小于4,同時右值都大于5。這樣,我們就可以使用下面這個查詢:
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
注意,就像前面的查詢一樣,我們必須使用一個ORDER BY子句來對節(jié)點排序。這個查詢將返回:
+-------+
| title |
+-------+
| Food |
| Fruit |
| Red |
+-------+
我們現(xiàn)在只要把各行連起來,就可以得到“Cherry”的路徑了。
有多少個后續(xù)節(jié)點?How Many Descendants
如果你給我一個節(jié)點的左值和右值,我就可以告訴你他有多少個后續(xù)節(jié)點,只要利用一點點數(shù)學知識。
因為每個后續(xù)節(jié)點依次會對這個節(jié)點的右值增加2,所以后續(xù)節(jié)點的數(shù)量可以這樣計算:
descendants = (right – left - 1) / 2
利用這個簡單的公式,我可以立刻告訴你2-11的“Fruit”節(jié)點有4個后續(xù)節(jié)點,8-9的“Banana”節(jié)點只是1個子節(jié)點,而不是父節(jié)點。
自動化樹遍歷
現(xiàn)在你對這個表做一些事情,我們應(yīng)該學習如何自動的建立表了。這是一個不錯的練習,首先用一個小的樹,我們也需要一個腳本來幫我們完成對節(jié)點的計數(shù)。
讓我們先寫一個腳本用來把一個鄰接列表轉(zhuǎn)換成前序遍歷樹表格。
<?php
function rebuild_tree($parent, $left) {
// 這個節(jié)點的右值是左值加1
$right = $left+1;
// 獲得這個節(jié)點的所有子節(jié)點
$result = mysql_query('SELECT title FROM tree '.
'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result)) {
// 對當前節(jié)點的每個子節(jié)點遞歸執(zhí)行這個函數(shù)
// $right 是當前的右值,它會被rebuild_tree函數(shù)增加
$right = rebuild_tree($row['title'], $right);
}
// 我們得到了左值,同時現(xiàn)在我們已經(jīng)處理這個節(jié)點我們知道右值的子節(jié)點
mysql_query('UPDATE tree SET lft='.$left.', rgt='.
$right.' WHERE title="'.$parent.'";');
// 返回該節(jié)點的右值+1
return $right+1;
}
?>
這是一個遞歸函數(shù)。你要從rebuild_tree('Food',1);
開始,這個函數(shù)就會獲取所有的“Food”節(jié)點的子節(jié)點。
如果沒有子節(jié)點,他就直接設(shè)置它的左值和右值。左值已經(jīng)給出了,1,右值則是左值加1。如果有子節(jié)點,函數(shù)重復并且返回最后一個右值。這個右值用來作為“Food”的右值。
遞歸讓這個函數(shù)有點復雜難于理解。然而,這個函數(shù)確實得到了同樣的結(jié)果。他沿著樹走,添加每一個他看見的節(jié)點。你運行了這個函數(shù)之后,你會發(fā)現(xiàn)左值和右值和預(yù)期的是一樣的(一個快速檢驗的方法:根節(jié)點的右值應(yīng)該是節(jié)點數(shù)量的兩倍)。
添加一個節(jié)點
我們?nèi)绾谓o這棵樹添加一個節(jié)點?有兩種方式:在表中保留“parent”列并且重新運行rebuild_tree()
函數(shù)——一個很簡單但卻不是很優(yōu)雅的函數(shù);或者你可以更新所有新節(jié)點右邊的節(jié)點的左值和右值。
第一個想法比較簡單。你使用鄰接列表方法來更新,同時使用改進前序遍歷樹來查詢。如果你想添加一個新的節(jié)點,你只需要把節(jié)點插入表格,并且設(shè)置好parent列。然后,你只需要重新運行rebuild_tree()
函數(shù)。這做起來很簡單,但是對大的樹效率不高。
第二種添加和刪除節(jié)點的方法是更新新節(jié)點右邊的所有節(jié)點。讓我們看一下例子。我們要添加一種新的水果——“Strawberry”,作為“Red”的最后一個子節(jié)點。首先,我們要騰出一個空間?!癛ed”的右值要從6變成8,7-10的“Yellow”節(jié)點要變成9-12,如此類推。更新“Red”節(jié)點意味著我們要把所有左值和右值大于5的節(jié)點加上2。
我們用一下查詢:
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
現(xiàn)在我們可以添加一個新的節(jié)點“Strawberry”來填補這個新的空間。這個節(jié)點左值為6右值為7。
INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';
如果我們運行display_tree()
函數(shù),我們將發(fā)現(xiàn)我們新的“Strawberry”節(jié)點已經(jīng)成功地插入了樹中:
Food
Fruit
Red
Cherry
Strawberry
Yellow
Banana
Meat
Beef
Pork
缺點
首先,改進前序遍歷樹算法看上去很難理解。它當然沒有鄰接列表方法簡單。然而,一旦你習慣了左值和右值這兩個屬性,他就會變得清晰起來,你可以用這個技術(shù)來完成臨街列表能完成的所有事情,同時改進前序遍歷樹算法更快。當然,更新樹需要很多查詢,要慢一點,但是取得節(jié)點卻可以只用一個查詢。
總結(jié)
你現(xiàn)在已經(jīng)對兩種在數(shù)據(jù)庫存儲樹方式熟悉了吧。雖然在我這兒改進前序遍歷樹算法性能更好,但是也許在你特殊的情況下鄰接列表方法可能表現(xiàn)更好一些。這個就留給你自己決定了
最后一點:就像我已經(jīng)說得我部推薦你使用節(jié)點的標題來引用這個節(jié)點。你應(yīng)該遵循數(shù)據(jù)庫標準化的基本規(guī)則。我沒有使用數(shù)字標識是因為用了之后例子就比較難讀。
進一步閱讀
數(shù)據(jù)庫指導 Joe Celko寫的更多關(guān)于SQL數(shù)據(jù)庫中的樹的問題:
http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html [6]
另外兩種處理層次數(shù)據(jù)的方法:
http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html [7]
Xindice, “本地XML數(shù)據(jù)庫”:
http://xml.apache.org/xindice/ [8]
遞歸的一個解釋:
http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html [9]
[1] /glossary.php?q=C#term_28
[2] /glossary.php?q=X#term_3
[3] /glossary.php?q=P#term_1
[4] /glossary.php?q=P#term_50
[5] /glossary.php?q=%23#term_72
[6] http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html
[7] http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
[8] http://xml.apache.org/xindice/
[9] http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html
- 解析左右值無限分類的實現(xiàn)算法
- 解析thinkphp的左右值無限分類
- php無限分類且支持輸出樹狀圖的詳細介紹
- 利用php遞歸實現(xiàn)無限分類 格式化數(shù)組的詳解
- PHP無限分類(樹形類)的深入分析
- 基于php無限分類的深入理解
- 比較簡單實用的PHP無限分類源碼分享(思路不錯)
- PHP 無限分類三種方式 非函數(shù)的遞歸調(diào)用!
- PHP無限分類代碼,支持數(shù)組格式化、直接輸出菜單兩種方式
- 一個很簡單的無限分類樹實現(xiàn)代碼
- php遞歸實現(xiàn)無限分類生成下拉列表的函數(shù)
- php用數(shù)組返回無限分類的列表數(shù)據(jù)的代碼
- 刪除無限分類并同時刪除它下面的所有子分類的方法
- php 無限分類的樹類代碼
- asp.net 無限分類
- 自己前幾天寫的無限分類類
- 帖幾個PHP的無限分類實現(xiàn)想法~
- PHP 循環(huán)刪除無限分類子節(jié)點的實現(xiàn)代碼
相關(guān)文章
php設(shè)計模式 Chain Of Responsibility (職責鏈模式)
為解除請求的發(fā)送者和接收者之間的耦合,而使用多個對象都用機會處理這個請求,將這些對象連成一條鏈,并沿著這條鏈傳遞該請求,直到有一個對象處理它2011-06-06圖文詳解phpstorm配置Xdebug進行調(diào)試PHP教程
這篇文章主要為大家詳細的介紹了phpstorm配置Xdebug進行調(diào)試PHP教程 ,感興趣的小伙伴們可以參考一下2016-06-06PHP使用PDO創(chuàng)建MySQL數(shù)據(jù)庫、表及插入多條數(shù)據(jù)操作示例
這篇文章主要介紹了PHP使用PDO創(chuàng)建MySQL數(shù)據(jù)庫、表及插入多條數(shù)據(jù)操作,結(jié)合實例形式總結(jié)分析了php基于pdo的mysql數(shù)據(jù)庫創(chuàng)建、數(shù)據(jù)表創(chuàng)建以及多條數(shù)據(jù)插入操作相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2019-05-05PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù)解析
這篇文章主要介紹了PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù)解析,本文用代碼實例講解了PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù),需要的朋友可以參考下2014-10-10