幾篇關(guān)于無限分類算法的文章第4/5頁
標(biāo)題:基于嵌套模型的無限級分類
http://bbs.dvbbs.net/dispbbs.asp?boardID=1&ID=1272297
根據(jù)國外的: Nested Set Model of Trees
http://searchoracle.techtarget.com/tip/1,289483,sid13_gci537290,00.html
http://www.dbmsmag.com/9603d06.html
我覺得奇怪的是，這個SQL來實現(xiàn)樹的算法早在1996、1999年就提出了，而為什么在國內(nèi)的ASP系統(tǒng)中都沒有見過用此來實現(xiàn)的？其實此算法的無限級才是真正是“無限”即結(jié)點數(shù)目可以達2^32=4G個（只局限于lft和rgt的取值范圍），而且更新樹的時候，只需要維護lft和rgt兩個字段的整型數(shù)據(jù)（要知道整型數(shù)據(jù)的運算速度是最快的）。
而目前國內(nèi)大家都是用的一個字符串字段來保存結(jié)點的路徑，SQL對可索引字符串的長度是有限（Access:255,MSSQL:8000），但如果用備注類型來做的話，就根本沒得什么索引和效率可言了。
演示測試地址:
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
'############################################################
'* 名稱: 插入結(jié)點到樹
'* 說明:
'* 日期: 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，則出錯
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
'############################################################
'* 名稱: 顯示整棵樹
'* 說明:
'* 日期: 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
'至少要有一個結(jié)點，如果是網(wǎng)站，那么就以該網(wǎng)站的名稱作為根結(jié)點
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
'進棧
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
'############################################################
'* 名稱: 刪除結(jié)點以及它的子樹
'* 說明:
'* 日期: 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
'############################################################
'* 名稱: 獲得某結(jié)點的路徑
'* 說明:
'* 日期: 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
'############################################################
'* 名稱: 獲得某結(jié)點的直屬子結(jié)點
'* 說明:
'* 日期: 2006-09-20 作者: pkmaster
'############################################################
Function GetChildNodes(RootID)
Dim tmpview
'如果為了提速，可以將下面的SQL語句作為視圖
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)然這個函數(shù)是一個遞歸函數(shù)，我們需要從根節(jié)點開始運行這個函數(shù)來重建一個帶有左右值的樹
rebuild_tree('Food',1);
這個函數(shù)看上去有些復(fù)雜，但是它的作用和手工對表進行編號一樣，就是將立體多層結(jié)構(gòu)的轉(zhuǎn)換成一個帶有左右值的數(shù)據(jù)表。
那么對于這樣的結(jié)構(gòu)我們該如何增加，更新和刪除一個節(jié)點呢？
增加一個節(jié)點一般有兩種方法：
第一種，保留原有的name 和parent結(jié)構(gòu)，用老方法向數(shù)據(jù)中添加數(shù)據(jù)，每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對整個結(jié)構(gòu)重新進行一次編號。
第二種，效率更高的辦法是改變所有位于新節(jié)點右側(cè)的數(shù)值。舉例來說：我們想增加一種新的水果"Strawberry"（草莓）它將成為"Red"節(jié)點的最后一個子節(jié)點。首先我們需要為它騰出一些空間。"Red"的右值應(yīng)當(dāng)從6改成8，"Yellow 7-10 "的左右值則應(yīng)當(dāng)改成 9-12。 依次類推我們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節(jié)點 （5 是"Red"最后一個子節(jié)點的右值） 加上2。 所以我們這樣進行數(shù)據(jù)庫操作：
UPDATE tree SET rgt=rgt+2 WHERE rgt>;5;
UPDATE tree SET lft=lft+2 WHERE lft>;5;
這樣就為新插入的值騰出了空間，現(xiàn)在可以在騰出的空間里建立一個新的數(shù)據(jù)節(jié)點了， 它的左右值分別是6和7
INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
再做一次查詢看看吧！怎么樣？很快吧。
好了，現(xiàn)在你可以用兩種不同的方法設(shè)計你的多級數(shù)據(jù)庫結(jié)構(gòu)了，采用何種方式完全取決于你個人的判斷，但是對于層次多數(shù)量大的結(jié)構(gòu)我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數(shù)據(jù)，則第一種方法更為簡便。
另外，如果數(shù)據(jù)庫支持的話 你還可以將rebuild_tree()和 騰出空間的操作寫成數(shù)據(jù)庫端的觸發(fā)器函數(shù)， 在插入和更新的時候自動執(zhí)行， 這樣可以得到更好的運行效率， 而且你添加新節(jié)點的SQL語句會變得更加簡單。
- 解析左右值無限分類的實現(xiàn)算法
- 解析thinkphp的左右值無限分類
- php無限分類且支持輸出樹狀圖的詳細介紹
- 利用php遞歸實現(xiàn)無限分類 格式化數(shù)組的詳解
- PHP無限分類(樹形類)的深入分析
- 基于php無限分類的深入理解
- 比較簡單實用的PHP無限分類源碼分享(思路不錯)
- PHP 無限分類三種方式 非函數(shù)的遞歸調(diào)用！
- PHP無限分類代碼，支持?jǐn)?shù)組格式化、直接輸出菜單兩種方式
- 一個很簡單的無限分類樹實現(xiàn)代碼
- php遞歸實現(xiàn)無限分類生成下拉列表的函數(shù)
- php用數(shù)組返回?zé)o限分類的列表數(shù)據(jù)的代碼
- 刪除無限分類并同時刪除它下面的所有子分類的方法
- php 無限分類的樹類代碼
- asp.net 無限分類
- 自己前幾天寫的無限分類類
- 帖幾個PHP的無限分類實現(xiàn)想法~
- PHP 循環(huán)刪除無限分類子節(jié)點的實現(xiàn)代碼
相關(guān)文章
php設(shè)計模式 Chain Of Responsibility (職責(zé)鏈模式)
為解除請求的發(fā)送者和接收者之間的耦合,而使用多個對象都用機會處理這個請求,將這些對象連成一條鏈,并沿著這條鏈傳遞該請求,直到有一個對象處理它2011-06-06
這篇文章主要介紹了PHP計算指定日期所在周的開始和結(jié)束日期的方法,涉及php操作日期時間的技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-03-03
這篇文章主要介紹了php ImageMagick windows下安裝教程,本文詳細講解了windows下安裝ImageMagick的步驟、包括下載、安裝、擴展安裝、測試等步驟,需要的朋友可以參考下2015-01-01
這篇文章主要介紹了PHP解壓ZIP文件到指定文件夾的方法,結(jié)合實例形式分析了php實現(xiàn)的zip操作類及相應(yīng)使用技巧,需要的朋友可以參考下2016-11-11
本文主要給大家介紹的是php5.3引入的PHP匿名函數(shù)，也就是閉包（Closure），以及閉包的作用，非常詳細，這里推薦給有需要的小伙伴們。2016-02-02
圖文詳解phpstorm配置Xdebug進行調(diào)試PHP教程
這篇文章主要為大家詳細的介紹了phpstorm配置Xdebug進行調(diào)試PHP教程 ，感興趣的小伙伴們可以參考一下2016-06-06
PHP使用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-05
這篇文章主要介紹了PHP實現(xiàn)鏈?zhǔn)讲僮鞯娜N方法,結(jié)合實例形式分析了php鏈?zhǔn)讲僮鞯南嚓P(guān)實現(xiàn)技巧與使用注意事項,需要的朋友可以參考下2017-11-11
PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù)解析
這篇文章主要介紹了PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù)解析,本文用代碼實例講解了PHP中構(gòu)造函數(shù)和析構(gòu)函數(shù),需要的朋友可以參考下2014-10-10
這篇文章主要介紹了php采集中國代理服務(wù)器網(wǎng)的方法,涉及php采集的相關(guān)使用技巧,需要的朋友可以參考下2015-06-06