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