快捷導(dǎo)航

mysql 無(wú)限級(jí)分類(lèi)實(shí)現(xiàn)思路

更新時(shí)間：2011年08月14日 23:25:57 作者：

關(guān)于該問(wèn)題，暫時(shí)自己還沒(méi)有深入研究，在網(wǎng)上找到幾種解決方案，各有優(yōu)缺點(diǎn)。

第一種方案：
使用遞歸算法，也是使用頻率最多的，大部分開(kāi)源程序也是這么處理，不過(guò)一般都只用到四級(jí)分類(lèi)。這種算法的數(shù)據(jù)庫(kù)結(jié)構(gòu)設(shè)計(jì)最為簡(jiǎn)單。category表中一個(gè)字段id，一個(gè)字段fid(父id)。這樣可以根據(jù)WHERE id = fid來(lái)判斷上一級(jí)內(nèi)容，運(yùn)用遞歸至最頂層。
分析：通過(guò)這種數(shù)據(jù)庫(kù)設(shè)計(jì)出的無(wú)限級(jí)，可以說(shuō)讀取的時(shí)候相當(dāng)費(fèi)勁，所以大部分的程序最多3-4級(jí)分類(lèi)，這就足以滿足需求，從而一次性讀出所有的數(shù)據(jù)，再對(duì)得到數(shù)組或者對(duì)象進(jìn)行遞歸。本身負(fù)荷還是沒(méi)太大問(wèn)題。但是如果分類(lèi)到更多級(jí)，那是不可取的辦法。
這樣看來(lái)這種分類(lèi)有個(gè)好處，就是增刪改的時(shí)候輕松了…然而就二級(jí)分類(lèi)而言，采用這種算法就應(yīng)該算最優(yōu)先了。

第二種方案：
設(shè)置fid字段類(lèi)型為varchar，將父類(lèi)id都集中在這個(gè)字段里，用符號(hào)隔開(kāi)，比如：1,3,6
這樣可以比較容易得到各上級(jí)分類(lèi)的ID，而且在查詢(xún)分類(lèi)下的信息的時(shí)候，
可以使用：SELECT * FROM category WHERE pid LIKE “1,3%”。

分析：相比于遞歸算法，在讀取數(shù)據(jù)方面優(yōu)勢(shì)非常大，但是若查找該分類(lèi)的所有父分類(lèi) 或者子分類(lèi) 查詢(xún)的效率也不是很高，至少也要二次query，從某種意義看上，個(gè)人覺(jué)得不太符合數(shù)據(jù)庫(kù)范式的設(shè)計(jì)。倘若遞增到無(wú)限級(jí)，還需考慮字段是否達(dá)到要求，而且在修改分類(lèi)和轉(zhuǎn)移分類(lèi)的時(shí)候操作將非常麻煩。
暫時(shí)，在自己項(xiàng)目中用的就是類(lèi)似第二種方案的解決辦法。就該方案在我的項(xiàng)目中存在這樣的問(wèn)題，如果當(dāng)所有數(shù)據(jù)記錄達(dá)到上萬(wàn)甚至10W以上后，一次性將所以分類(lèi)，有序分級(jí)的現(xiàn)實(shí)出來(lái)，效率很低。極有可能是項(xiàng)目處理數(shù)據(jù)代碼效率低帶來(lái)的?，F(xiàn)在正在改良。
第三種方案：
　　無(wú)限級(jí)分類(lèi)----改進(jìn)前序遍歷樹(shù)
那么理想中的樹(shù)型結(jié)構(gòu)應(yīng)具備哪些特點(diǎn)呢？數(shù)據(jù)存儲(chǔ)冗余小、直觀性強(qiáng)；方便返回整個(gè)樹(shù)型結(jié)構(gòu)數(shù)據(jù)；可以很輕松的返回某一子樹(shù)（方便分層加載）；快整獲以某節(jié)點(diǎn)的祖譜路徑；插入、刪除、移動(dòng)節(jié)點(diǎn)效率高等等。帶著這些需求我查找了很多資料，發(fā)現(xiàn)了一種理想的樹(shù)型結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)及操作算法，改進(jìn)的前序遍歷樹(shù)模型（The Nested Set Model）。
原理：
我們先把樹(shù)按照水平方式擺開(kāi)。從根節(jié)點(diǎn)開(kāi)始（“Food”），然后他的左邊寫(xiě)上1。然后按照樹(shù)的順序（從上到下）給“Fruit”的左邊寫(xiě)上2。這樣，你沿著樹(shù)的邊界走啊走（這就是“遍歷”），然后同時(shí)在每個(gè)節(jié)點(diǎn)的左邊和右邊寫(xiě)上數(shù)字。最后，我們回到了根節(jié)點(diǎn)“Food”在右邊寫(xiě)上18。下面是標(biāo)上了數(shù)字的樹(shù)，同時(shí)把遍歷的順序用箭頭標(biāo)出來(lái)了。

我們稱(chēng)這些數(shù)字為左值和右值（如，“Food”的左值是1，右值是18）。正如你所見(jiàn)，這些數(shù)字按時(shí)了每個(gè)節(jié)點(diǎn)之間的關(guān)系。因?yàn)椤癛ed”有3和6兩個(gè)值，所以，它是有擁有1-18值的“Food”節(jié)點(diǎn)的后續(xù)。同樣的，我們可以推斷所有左值大于2并且右值小于11的節(jié)點(diǎn)，都是有2-11的“Fruit” 節(jié)點(diǎn)的后續(xù)。這樣，樹(shù)的結(jié)構(gòu)就通過(guò)左值和右值儲(chǔ)存下來(lái)了。這種數(shù)遍整棵樹(shù)算節(jié)點(diǎn)的方法叫做“改進(jìn)前序遍歷樹(shù)”算法。

表結(jié)構(gòu)設(shè)計(jì)：

那么我們?cè)鯓硬拍芡ㄟ^(guò)一個(gè)SQL語(yǔ)句把所有的分類(lèi)都查詢(xún)出來(lái)呢，而且要求如果是子類(lèi)的話前面要打幾個(gè)空格以表現(xiàn)是子分類(lèi)。要想查詢(xún)出所有分類(lèi)很好辦：SELECT * FROM category WHERE lft>1 AND lft<18 ORDER BY lft這樣的話所有的分類(lèi)都出來(lái)了，但是誰(shuí)是誰(shuí)的子類(lèi)卻分不清，那么怎么辦呢?我們仔細(xì)看圖不難發(fā)現(xiàn)如果相鄰的兩條記錄的右值第一條的右值比第二條的大那么就是他的父類(lèi)，比如food的右值是18而fruit的右值是11 那么food是fruit的父類(lèi)，但是又要考慮到多級(jí)目錄。于是有了這樣的設(shè)計(jì)，我們用一個(gè)數(shù)組來(lái)存儲(chǔ)上一條記錄的右值，再把它和本條記錄的右值比較，如果前者比后者小，說(shuō)明不是父子關(guān)系，就用array_pop彈出數(shù)組，否則就保留，之后根據(jù)數(shù)組的大小來(lái)打印空格。這樣就解決了這個(gè)問(wèn)題。代碼如下
表結(jié)構(gòu)：

復(fù)制代碼代碼如下:

 
-- 
-- 表的結(jié)構(gòu) `category` 
-- 
CREATE TABLE IF NOT EXISTS `category` ( 
`id` int(11) NOT NULL AUTO_INCREMENT, 
`type` int(11) NOT NULL COMMENT '1為文章類(lèi)型2為產(chǎn)品類(lèi)型3為下載類(lèi)型', 
`title` varchar(50) NOT NULL, 
`lft` int(11) NOT NULL, 
`rgt` int(11) NOT NULL, 
`lorder` int(11) NOT NULL COMMENT '排序', 
`create_time` int(11) NOT NULL, 
PRIMARY KEY (`id`) 
) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=10 ; 
-- 
-- 導(dǎo)出表中的數(shù)據(jù) `category` 
-- 
INSERT INTO `category` (`id`, `type`, `title`, `lft`, `rgt`, `lorder`, `create_time`) VALUES 
(1, 1, '頂級(jí)欄目', 1, 18, 1, 1261964806), 
(2, 1, '公司簡(jiǎn)介', 14, 17, 50, 1264586212), 
(3, 1, '新聞', 12, 13, 50, 1264586226), 
(4, 2, '公司產(chǎn)品', 10, 11, 50, 1264586249), 
(5, 1, '榮譽(yù)資質(zhì)', 8, 9, 50, 1264586270), 
(6, 3, '資料下載', 6, 7, 50, 1264586295), 
(7, 1, '人才招聘', 4, 5, 50, 1264586314), 
(8, 1, '留言板', 2, 3, 50, 1264586884), 
(9, 1, '總裁', 15, 16, 50, 1267771951); 

/** 
* 顯示樹(shù),把所有的節(jié)點(diǎn)都顯示出來(lái)。 
* 1、先得到根結(jié)點(diǎn)的左右值（默認(rèn)根節(jié)點(diǎn)的title為“頂級(jí)目錄”）。 
* 2、查詢(xún)左右值在根節(jié)點(diǎn)的左右值范圍內(nèi)的記錄，并且根據(jù)左值排序。 
* 3、如果本次記錄右值大于前次記錄的右值則為子分類(lèi)，輸出時(shí)候加空格。 
* @return array 
**/ 
function display_tree(){ 

//獲得root左邊和右邊的值 
$arr_lr = $this->category->where("title = '頂級(jí)欄目'")->find(); 
//print_r($arr_lr); 
if($arr_lr){ 
$right = array(); 
$arr_tree = $this->category->query("SELECT id, type, title, rgt FROM category WHERE lft >= ". $arr_lr['lft'] ." AND lft <=".$arr_lr['rgt']." ORDER BY lft"); 
foreach($arr_tree as $v){ 
if(count($right)){ 
while ($right[count($right) -1] < $v['rgt']){ 
array_pop($right); 
} 
} 
$title = $v['title']; 
if(count($right)){ 
$title = '|-'.$title; 
} 
$arr_list[] = array('id' => $v['id'], 'type' => $type, 'title' => str_repeat('&nbsp;&nbsp;', count($right)).$title, 'name' =>$v['title']); 
$right[] = $v['rgt']; 
} 
return $arr_list; 
} 
} 

好了只要這樣所有的分類(lèi)都可以一次性查詢(xún)出來(lái)了，而不用通過(guò)遞歸了。
下面的問(wèn)題是怎樣進(jìn)行插入、刪除和修改操作
插入:插入操作很簡(jiǎn)單找到其父節(jié)點(diǎn)，之后把左值和右值大于父節(jié)點(diǎn)左值的節(jié)點(diǎn)的左右值加上2，之后再插入本節(jié)點(diǎn)，左右值分別為父節(jié)點(diǎn)左值加一和加二，可以用一個(gè)存儲(chǔ)過(guò)程來(lái)操作：

復(fù)制代碼代碼如下:

 
CREATE PROCEDURE `category_insert_by_parent`(IN pid INT,IN title VARCHAR(20), IN type INT, IN l_order INT, IN pubtime INT) 
BEGIN 
DECLARE myLeft INT; 
SELECT lft into myLeft FROM category WHERE id= pid; 
UPDATE qy_category SET rgt = rgt + 2 WHERE rgt > myLeft; 
UPDATE qy_category SET lft = lft + 2 WHERE lft > myLeft; 
INSERT INTO qy_category(type, title, lft, rgt, lorder, create_time) VALUES(type ,title, myLeft + 1, myLeft + 2, l_order, pubtime); 
commit; 
END 

刪除操作：
刪除的原理：1.得到要?jiǎng)h除節(jié)點(diǎn)的左右值，并得到他們的差再加一，@mywidth = @rgt - @lft + 1;
2.刪除左右值在本節(jié)點(diǎn)之間的節(jié)點(diǎn)
3.修改條件為大于本節(jié)點(diǎn)右值的所有節(jié)點(diǎn)，操作為把他們的左右值都減去@mywidth
存儲(chǔ)過(guò)程如下：

復(fù)制代碼代碼如下:

 
CREATE PROCEDURE `category_delete_by_key`(IN id INT) 
BEGIN 
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1 
FROM category 
WHERE id = id; 
DELETE FROM category WHERE lft BETWEEN @myLeft AND @myRight; 
UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight; 
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight; 

修改：
要命的修改操作，本人看了很久也沒(méi)有看出什么規(guī)律出來(lái)，只要出此下策，先刪除再插入，只要調(diào)用上面2個(gè)存儲(chǔ)過(guò)程就可以了！
總結(jié)：查詢(xún)方便，但是增刪改操作有點(diǎn)繁瑣，但是一般分類(lèi)此類(lèi)操作不是很多，還是查詢(xún)用的多，再說(shuō)弄個(gè)存儲(chǔ)過(guò)程也方便！

　　上面第三種方案具體講解類(lèi)容是從http://home.phpchina.com/space.php?uid=45095&do=blog&id=184675拷貝過(guò)來(lái)，方便以后自己查看。暫時(shí)從各方面及理論上考慮偏向于第三方案。不過(guò)還沒(méi)有做過(guò)測(cè)試，到底效率怎么樣。
期待更好的解決方案！

您可能感興趣的文章: