幾篇關(guān)于無(wú)限分類(lèi)算法的文章第4/5頁(yè)
標(biāo)題:基于嵌套模型的無(wú)限級(jí)分類(lèi)
http://bbs.dvbbs.net/dispbbs.asp?boardID=1&ID=1272297
根據(jù)國(guó)外的: Nested Set Model of Trees
http://searchoracle.techtarget.com/tip/1,289483,sid13_gci537290,00.html
http://www.dbmsmag.com/9603d06.html
我覺(jué)得奇怪的是，這個(gè)SQL來(lái)實(shí)現(xiàn)樹(shù)的算法早在1996、1999年就提出了，而為什么在國(guó)內(nèi)的ASP系統(tǒng)中都沒(méi)有見(jiàn)過(guò)用此來(lái)實(shí)現(xiàn)的？其實(shí)此算法的無(wú)限級(jí)才是真正是“無(wú)限”即結(jié)點(diǎn)數(shù)目可以達(dá)2^32=4G個(gè)（只局限于lft和rgt的取值范圍），而且更新樹(shù)的時(shí)候，只需要維護(hù)lft和rgt兩個(gè)字段的整型數(shù)據(jù)（要知道整型數(shù)據(jù)的運(yùn)算速度是最快的）。
而目前國(guó)內(nèi)大家都是用的一個(gè)字符串字段來(lái)保存結(jié)點(diǎn)的路徑，SQL對(duì)可索引字符串的長(zhǎng)度是有限（Access:255,MSSQL:8000），但如果用備注類(lèi)型來(lái)做的話(huà)，就根本沒(méi)得什么索引和效率可言了。
演示測(cè)試地址:
http://www.lxasp.com/Test_NestedTree.asp
'數(shù)據(jù)表如下:
'CREATE TABLE [TreeNode] (
' [tn_id] [int] IDENTITY (1, 1) NOT NULL ,
' [tn_name] [nvarchar] (50) NULL ,
' [tn_lft] [int] NULL ,
' [tn_rgt] [int] NULL ,
' CONSTRAINT [PK_TreeNode] PRIMARY KEY CLUSTERED
' (
' [tn_id]
' ) ON [PRIMARY]
') ON [PRIMARY]
'GO
Public startime,endtime,conn,connstr,rs,sql,sqlcount
startime=Timer()
sqlcount=0
Set conn = Server.CreateObject("ADODB.Connection")
connstr="Provider=Microsoft.Jet.OLEDB.4.0;Data Source=" & Server.MapPath("test.mdb")
conn.Open connstr
'############################################################
'* 名稱(chēng): 插入結(jié)點(diǎn)到樹(shù)
'* 說(shuō)明:
'* 日期: 2006-09-20 作者: pkmaster
'############################################################
Function InsertNew(Parent_ID , NewName)
Dim p_lft,p_rgt
SQL = "SELECT * FROM TreeNode WHERE tn_id="&Parent_ID
Set rs=Server.CreateObject("ADODB.Recordset")
rs.Open SQL,conn,1,3 '11 for Read '13 for Write
sqlcount=sqlcount+1
If rs.EOF And rs.BOF Then
'不存在Parent_ID，則出錯(cuò)
Else
rs.MoveFirst
p_lft=rs("tn_lft")
p_rgt=rs("tn_rgt")
conn.Execute "UPDATE TreeNode SET tn_rgt=tn_rgt+2 WHERE tn_rgt>" & CStr(p_rgt-1)
sqlcount=sqlcount+1
conn.Execute "UPDATE TreeNode SET tn_lft=tn_lft+2 WHERE tn_lft>" & CStr(p_rgt-1)
sqlcount=sqlcount+1
rs.AddNew
rs("tn_lft")=p_rgt
rs("tn_rgt")=p_rgt+1
rs("tn_name")=NewName
rs.Update
InsertNew=p_rgt+1
End If
rs.Close
Set rs = Nothing
End Function
'############################################################
'* 名稱(chēng): 顯示整棵樹(shù)
'* 說(shuō)明:
'* 日期: 2006-09-20 作者: pkmaster
'############################################################
Function ShowTree()
Dim stackd,stkpos,STACKMAX
Dim i,j
i=0
j=0
STACKMAX=100
stkpos=0
SQL = "SELECT * FROM TreeNode ORDER BY tn_lft ASC"
Set rs=Server.CreateObject("ADODB.Recordset")
rs.Open SQL,conn,1,1 '11 for Read '13 for Write
sqlcount=sqlcount+1
If rs.EOF And rs.BOF Then
Else
ReDim stackd(0,STACKMAX)
rs.MoveFirst
Do Until rs.EOF
If stkpos=0 Then
'至少要有一個(gè)結(jié)點(diǎn)，如果是網(wǎng)站，那么就以該網(wǎng)站的名稱(chēng)作為根結(jié)點(diǎn)
Response.Write rs("tn_name") & vbCrLf
End If
If stkpos>0 Then
'出棧
Do While stackd(0,stkpos-1)<rs("tn_rgt")
stkpos=stkpos-1
Loop
Response.Write Space(stkpos*4) & "(" & rs("tn_id") & ")" & rs("tn_name") & vbCrLf
End If
'進(jìn)棧
stkpos=stkpos+1
If stkpos-1>STACKMAX Then ReDim Preserve stackd(0,stkpos-1+STACKMAX)
stackd(0,stkpos-1)=rs("tn_rgt")
rs.MoveNext
Loop
End If
rs.Close
Set rs = Nothing
End Function
'############################################################
'* 名稱(chēng): 刪除結(jié)點(diǎn)以及它的子樹(shù)
'* 說(shuō)明:
'* 日期: 2006-09-20 作者: pkmaster
'############################################################
Function DeleteNode(NodeID)
Dim lft,rgt,diff
SQL = "SELECT * FROM TreeNode WHERE tn_id="&NodeID
Set rs=Server.CreateObject("ADODB.Recordset")
rs.Open SQL,conn,1,1 '11 for Read '13 for Write
sqlcount=sqlcount+1
If rs.EOF And rs.BOF Then
Exit Function
Else
rs.MoveFirst
lft=rs("tn_lft")
rgt=rs("tn_rgt")
End If
rs.Close
Set rs = Nothing
diff=rgt-lft+1
conn.Execute "DELETE FROM TreeNode WHERE tn_lft>=" & lft & " AND tn_rgt<= " & rgt & " "
conn.Execute "UPDATE TreeNode SET tn_lft=tn_lft-" & diff & " WHERE tn_lft>" & lft & " "
conn.Execute "UPDATE TreeNode SET tn_rgt=tn_rgt-" & diff & " WHERE tn_rgt>=" & rgt & " "
End Function
'############################################################
'* 名稱(chēng): 獲得某結(jié)點(diǎn)的路徑
'* 說(shuō)明:
'* 日期: 2006-09-20 作者: pkmaster
'############################################################
Function GetNodePath(NodeID)
Dim lft,rgt
GetNodePath=""
SQL = "SELECT A.tn_name,A.tn_lft,A.tn_rgt FROM TreeNode A ,TreeNode B WHERE (A.tn_lft<=B.tn_lft) AND (A.tn_rgt>=B.tn_rgt) AND B.tn_id=" & NodeID & " ORDER BY A.tn_lft"
Set rs=Server.CreateObject("ADODB.Recordset")
rs.Open SQL,conn,1,1 '11 for Read '13 for Write
sqlcount=sqlcount+1
If rs.EOF And rs.BOF Then
Else
rs.MoveFirst
Do Until rs.EOF
Response.Write rs(0).Value & "\"
rs.MoveNext
Loop
End If
rs.Close
Set rs = Nothing
End Function
'############################################################
'* 名稱(chēng): 獲得某結(jié)點(diǎn)的直屬子結(jié)點(diǎn)
'* 說(shuō)明:
'* 日期: 2006-09-20 作者: pkmaster
'############################################################
Function GetChildNodes(RootID)
Dim tmpview
'如果為了提速，可以將下面的SQL語(yǔ)句作為視圖
tmpview="SELECT a.tn_id AS pnt_id, a.tn_name AS pnt_name, b.tn_id AS sub_id, b.tn_name AS sub_name, b.tn_lft, b.tn_rgt " & _
"FROM TreeNode AS a, TreeNode AS b " & _
"WHERE b.tn_lft BETWEEN a.tn_lft AND a.tn_rgt AND NOT EXISTS " & _
"(SELECT * FROM TreeNode AS c " & _
"WHERE c.tn_lft BETWEEN a.tn_lft AND a.tn_rgt " & _
"AND b.tn_lft BETWEEN c.tn_lft AND c.tn_rgt " & _
"AND c.tn_id NOT IN (a.tn_id,b.tn_id) ) "
SQL="SELECT DISTINCT s1.sub_id,s1.sub_name " & _
"FROM (" & tmpview & ") as s1,(" & tmpview & ") as s2,TreeNode as o1 " & _
"WHERE s1.pnt_id=o1.tn_id " & _
"AND s2.pnt_id=s1.pnt_id " & _
"AND s1.sub_id<>s2.sub_id " & _
"AND s2.tn_lft <= s1.tn_lft " & _
"AND o1.tn_id=" & RootID & " "
Set rs=Server.CreateObject("ADODB.Recordset")
rs.Open SQL,conn,1,1
sqlcount=sqlcount+1
If rs.EOF And rs.BOF Then
Else
rs.MoveFirst
Do Until rs.EOF
Response.Write "(" & rs(0) & ")" & rs(1) & vbCrLf
rs.MoveNext
Loop
End If
rs.Close
Set rs = Nothing
End Function
以下是代碼：
CODE:[Copy to clipboard]<?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;
}
?>;
當(dāng)然這個(gè)函數(shù)是一個(gè)遞歸函數(shù)，我們需要從根節(jié)點(diǎn)開(kāi)始運(yùn)行這個(gè)函數(shù)來(lái)重建一個(gè)帶有左右值的樹(shù)
rebuild_tree('Food',1);
這個(gè)函數(shù)看上去有些復(fù)雜，但是它的作用和手工對(duì)表進(jìn)行編號(hào)一樣，就是將立體多層結(jié)構(gòu)的轉(zhuǎn)換成一個(gè)帶有左右值的數(shù)據(jù)表。
那么對(duì)于這樣的結(jié)構(gòu)我們?cè)撊绾卧黾樱潞蛣h除一個(gè)節(jié)點(diǎn)呢？
增加一個(gè)節(jié)點(diǎn)一般有兩種方法：
第一種，保留原有的name 和parent結(jié)構(gòu)，用老方法向數(shù)據(jù)中添加數(shù)據(jù)，每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對(duì)整個(gè)結(jié)構(gòu)重新進(jìn)行一次編號(hào)。
第二種，效率更高的辦法是改變所有位于新節(jié)點(diǎn)右側(cè)的數(shù)值。舉例來(lái)說(shuō)：我們想增加一種新的水果"Strawberry"（草莓）它將成為"Red"節(jié)點(diǎn)的最后一個(gè)子節(jié)點(diǎn)。首先我們需要為它騰出一些空間。"Red"的右值應(yīng)當(dāng)從6改成8，"Yellow 7-10 "的左右值則應(yīng)當(dāng)改成 9-12。 依次類(lèi)推我們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節(jié)點(diǎn) （5 是"Red"最后一個(gè)子節(jié)點(diǎn)的右值） 加上2。 所以我們這樣進(jìn)行數(shù)據(jù)庫(kù)操作：
UPDATE tree SET rgt=rgt+2 WHERE rgt>;5;
UPDATE tree SET lft=lft+2 WHERE lft>;5;
這樣就為新插入的值騰出了空間，現(xiàn)在可以在騰出的空間里建立一個(gè)新的數(shù)據(jù)節(jié)點(diǎn)了， 它的左右值分別是6和7
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
再做一次查詢(xún)看看吧！怎么樣？很快吧。
好了，現(xiàn)在你可以用兩種不同的方法設(shè)計(jì)你的多級(jí)數(shù)據(jù)庫(kù)結(jié)構(gòu)了，采用何種方式完全取決于你個(gè)人的判斷，但是對(duì)于層次多數(shù)量大的結(jié)構(gòu)我更喜歡第二種方法。如果查詢(xún)量較小但是需要頻繁添加和更新的數(shù)據(jù)，則第一種方法更為簡(jiǎn)便。
另外，如果數(shù)據(jù)庫(kù)支持的話(huà) 你還可以將rebuild_tree()和 騰出空間的操作寫(xiě)成數(shù)據(jù)庫(kù)端的觸發(fā)器函數(shù)， 在插入和更新的時(shí)候自動(dòng)執(zhí)行， 這樣可以得到更好的運(yùn)行效率， 而且你添加新節(jié)點(diǎn)的SQL語(yǔ)句會(huì)變得更加簡(jiǎn)單。
- 解析左右值無(wú)限分類(lèi)的實(shí)現(xiàn)算法
- 解析thinkphp的左右值無(wú)限分類(lèi)
- php無(wú)限分類(lèi)且支持輸出樹(shù)狀圖的詳細(xì)介紹
- 利用php遞歸實(shí)現(xiàn)無(wú)限分類(lèi) 格式化數(shù)組的詳解
- PHP無(wú)限分類(lèi)(樹(shù)形類(lèi))的深入分析
- 基于php無(wú)限分類(lèi)的深入理解
- 比較簡(jiǎn)單實(shí)用的PHP無(wú)限分類(lèi)源碼分享(思路不錯(cuò))
- PHP 無(wú)限分類(lèi)三種方式 非函數(shù)的遞歸調(diào)用！
- PHP無(wú)限分類(lèi)代碼，支持?jǐn)?shù)組格式化、直接輸出菜單兩種方式
- 一個(gè)很簡(jiǎn)單的無(wú)限分類(lèi)樹(shù)實(shí)現(xiàn)代碼
- php遞歸實(shí)現(xiàn)無(wú)限分類(lèi)生成下拉列表的函數(shù)
- php用數(shù)組返回?zé)o限分類(lèi)的列表數(shù)據(jù)的代碼
- 刪除無(wú)限分類(lèi)并同時(shí)刪除它下面的所有子分類(lèi)的方法
- php 無(wú)限分類(lèi)的樹(shù)類(lèi)代碼
- asp.net 無(wú)限分類(lèi)
- 自己前幾天寫(xiě)的無(wú)限分類(lèi)類(lèi)
- 帖幾個(gè)PHP的無(wú)限分類(lèi)實(shí)現(xiàn)想法~
- PHP 循環(huán)刪除無(wú)限分類(lèi)子節(jié)點(diǎn)的實(shí)現(xiàn)代碼
相關(guān)文章
php設(shè)計(jì)模式 Chain Of Responsibility (職責(zé)鏈模式)
為解除請(qǐng)求的發(fā)送者和接收者之間的耦合,而使用多個(gè)對(duì)象都用機(jī)會(huì)處理這個(gè)請(qǐng)求,將這些對(duì)象連成一條鏈,并沿著這條鏈傳遞該請(qǐng)求,直到有一個(gè)對(duì)象處理它2011-06-06
PHP計(jì)算指定日期所在周的開(kāi)始和結(jié)束日期的方法
這篇文章主要介紹了PHP計(jì)算指定日期所在周的開(kāi)始和結(jié)束日期的方法,涉及php操作日期時(shí)間的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
這篇文章主要介紹了php ImageMagick windows下安裝教程,本文詳細(xì)講解了windows下安裝ImageMagick的步驟、包括下載、安裝、擴(kuò)展安裝、測(cè)試等步驟,需要的朋友可以參考下2015-01-01
這篇文章主要介紹了PHP解壓ZIP文件到指定文件夾的方法,結(jié)合實(shí)例形式分析了php實(shí)現(xiàn)的zip操作類(lèi)及相應(yīng)使用技巧,需要的朋友可以參考下2016-11-11
本文主要給大家介紹的是php5.3引入的PHP匿名函數(shù)，也就是閉包（Closure），以及閉包的作用，非常詳細(xì)，這里推薦給有需要的小伙伴們。2016-02-02
圖文詳解phpstorm配置Xdebug進(jìn)行調(diào)試PHP教程
這篇文章主要為大家詳細(xì)的介紹了phpstorm配置Xdebug進(jìn)行調(diào)試PHP教程 ，感興趣的小伙伴們可以參考一下2016-06-06
PHP使用PDO創(chuàng)建MySQL數(shù)據(jù)庫(kù)、表及插入多條數(shù)據(jù)操作示例
這篇文章主要介紹了PHP使用PDO創(chuàng)建MySQL數(shù)據(jù)庫(kù)、表及插入多條數(shù)據(jù)操作,結(jié)合實(shí)例形式總結(jié)分析了php基于pdo的mysql數(shù)據(jù)庫(kù)創(chuàng)建、數(shù)據(jù)表創(chuàng)建以及多條數(shù)據(jù)插入操作相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-05-05
PHP實(shí)現(xiàn)鏈?zhǔn)讲僮鞯娜N方法詳解
這篇文章主要介紹了PHP實(shí)現(xiàn)鏈?zhǔn)讲僮鞯娜N方法,結(jié)合實(shí)例形式分析了php鏈?zhǔn)讲僮鞯南嚓P(guān)實(shí)現(xiàn)技巧與使用注意事項(xiàng),需要的朋友可以參考下2017-11-11
PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù)解析
這篇文章主要介紹了PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù)解析,本文用代碼實(shí)例講解了PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù),需要的朋友可以參考下2014-10-10
php采集中國(guó)代理服務(wù)器網(wǎng)的方法
這篇文章主要介紹了php采集中國(guó)代理服務(wù)器網(wǎng)的方法,涉及php采集的相關(guān)使用技巧,需要的朋友可以參考下2015-06-06