您所在位置：主题：[原创]基于嵌套模型的无限级分类
pk4321
[专家分：690] 发布于 2006-09-23 22:25:00
根据国外的: Nested Set Model of Trees
http://searchoracle.techtarget.com/tip/1,289483,sid13_gci537290,00.html
http://www.dbmsmag.com/9603d06.html
我觉得奇怪的是，这个SQL来实现树的算法早在1996、1999年就提出了，而为什么在国内的ASP系统中都没有见过用此来实现的？其实此算法的无限级才是真正是“无限”即结点数目可以达2^32=4G个（只局限于lft和rgt的取值范围），而且更新树的时候，只需要维护lft和rgt两个字段的整型数据（要知道整型数据的运算速度是最快的）。
而目前国内大家都是用的一个字符串字段来保存结点的路径，SQL对可索引字符串的长度是有限（Access:255,MSSQL:8000），但如果用备注类型来做的话，就根本没得什么索引和效率可言了。
[quote]
演示测试地址:
http://www.lxasp.com/Test_NestedTree.asp
[/quote]
部分关键代码:
[quote]
[color=#008000]'数据表如下:
'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
[/color][color=#008000]'* 名称: 插入结点到树
'* 日期: 2006-09-20 作者: pkmaster
[/color][color=#0000FF]Function [/color][color=#000000]InsertNew(Parent_ID , NewName)
[/color][color=#0000FF]Dim [/color][color=#000000]p_lft,p_rgt
SQL = [/color][color=#800000]"SELECT * FROM TreeNode WHERE tn_id="[/color][color=#000000]&Parent_ID
[/color][color=#0000FF]Set [/color][color=#000000]rs=Server.CreateObject([/color][color=#800000]"ADODB.Recordset"[/color][color=#000000])
rs.Open SQL,conn,[/color][color=#800080]1[/color][color=#000000],[/color][color=#800080]3 [/color][color=#008000]'11 for Read '13 for Write
[/color][color=#000000]sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#0000FF]If [/color][color=#000000]rs.EOF [/color][color=#0000FF]And [/color][color=#000000]rs.BOF [/color][color=#0000FF]Then
[/color][color=#008000]'不存在Parent_ID，则出错
[/color][color=#0000FF]Else
[/color][color=#000000]rs.MoveFirst
p_lft=rs([/color][color=#800000]"tn_lft"[/color][color=#000000])
p_rgt=rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])
conn.Execute [/color][color=#800000]"UPDATE TreeNode SET tn_rgt=tn_rgt+2 WHERE tn_rgt>" [/color][color=#000000]& CStr(p_rgt-[/color][color=#800080]1[/color][color=#000000])
sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#000000]conn.Execute [/color][color=#800000]"UPDATE TreeNode SET tn_lft=tn_lft+2 WHERE tn_lft>" [/color][color=#000000]& CStr(p_rgt-[/color][color=#800080]1[/color][color=#000000])
sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#000000]rs.AddNew
rs([/color][color=#800000]"tn_lft"[/color][color=#000000])=p_rgt
rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])=p_rgt+[/color][color=#800080]1
[/color][color=#000000]rs([/color][color=#800000]"tn_name"[/color][color=#000000])=NewName
rs.Update
InsertNew=p_rgt+[/color][color=#800080]1
[/color][color=#0000FF]End If
[/color][color=#000000]rs.Close
[/color][color=#0000FF]Set [/color][color=#000000]rs = [/color][color=#0000FF]Nothing
End Function
[/color][color=#008000]'* 名称: 显示整棵树
'* 日期: 2006-09-20 作者: pkmaster
[/color][color=#0000FF]Function [/color][color=#000000]ShowTree()
[/color][color=#0000FF]Dim [/color][color=#000000]stackd,stkpos,STACKMAX
[/color][color=#0000FF]Dim [/color][color=#000000]i,j
i=[/color][color=#800080]0
[/color][color=#000000]j=[/color][color=#800080]0
[/color][color=#000000]STACKMAX=[/color][color=#800080]100
[/color][color=#000000]stkpos=[/color][color=#800080]0
[/color][color=#000000]SQL = [/color][color=#800000]"SELECT * FROM TreeNode ORDER BY tn_lft ASC"
[/color][color=#0000FF]Set [/color][color=#000000]rs=Server.CreateObject([/color][color=#800000]"ADODB.Recordset"[/color][color=#000000])
rs.Open SQL,conn,[/color][color=#800080]1[/color][color=#000000],[/color][color=#800080]1 [/color][color=#008000]'11 for Read '13 for Write
[/color][color=#000000]sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#0000FF]If [/color][color=#000000]rs.EOF [/color][color=#0000FF]And [/color][color=#000000]rs.BOF [/color][color=#0000FF]Then
Else
ReDim [/color][color=#000000]stackd([/color][color=#800080]0[/color][color=#000000],STACKMAX)
rs.MoveFirst
[/color][color=#0000FF]Do Until [/color][color=#000000]rs.EOF
[/color][color=#0000FF]If [/color][color=#000000]stkpos=[/color][color=#800080]0 [/color][color=#0000FF]Then
[/color][color=#008000]'至少要有一个结点，如果是网站，那么就以该网站的名称作为根结点
[/color][color=#000000]Response.Write rs([/color][color=#800000]"tn_name"[/color][color=#000000]) & vbCrLf
[/color][color=#0000FF]End If
If [/color][color=#000000]stkpos>[/color][color=#800080]0 [/color][color=#0000FF]Then
[/color][color=#008000]'出栈
[/color][color=#0000FF]Do While [/color][color=#000000]stackd([/color][color=#800080]0[/color][color=#000000],stkpos-[/color][color=#800080]1[/color][color=#000000])<rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])
stkpos=stkpos-[/color][color=#800080]1
[/color][color=#0000FF]Loop
[/color][color=#000000]Response.Write Space(stkpos*[/color][color=#800080]4[/color][color=#000000]) & [/color][color=#800000]"(" [/color][color=#000000]& rs([/color][color=#800000]"tn_id"[/color][color=#000000]) & [/color][color=#800000]")" [/color][color=#000000]& rs([/color][color=#800000]"tn_name"[/color][color=#000000]) & vbCrLf
[/color][color=#0000FF]End If
[/color][color=#008000]'进栈
[/color][color=#000000]stkpos=stkpos+[/color][color=#800080]1
[/color][color=#0000FF]If [/color][color=#000000]stkpos-[/color][color=#800080]1[/color][color=#000000]>STACKMAX [/color][color=#0000FF]Then ReDim Preserve [/color][color=#000000]stackd([/color][color=#800080]0[/color][color=#000000],stkpos-[/color][color=#800080]1+[/color][color=#000000]STACKMAX)
stackd([/color][color=#800080]0[/color][color=#000000],stkpos-[/color][color=#800080]1[/color][color=#000000])=rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])
rs.MoveNext
[/color][color=#0000FF]Loop
End If
[/color][color=#000000]rs.Close
[/color][color=#0000FF]Set [/color][color=#000000]rs = [/color][color=#0000FF]Nothing
End Function
[/color][/quote]
http://searchoracle.techtarget.com/tip/1,289483,sid13_gci537290,00.html
http://www.dbmsmag.com/9603d06.html
我觉得奇怪的是，这个SQL来实现树的算法早在1996、1999年就提出了，而为什么在国内的ASP系统中都没有见过用此来实现的？其实此算法的无限级才是真正是“无限”即结点数目可以达2^32=4G个（只局限于lft和rgt的取值范围），而且更新树的时候，只需要维护lft和rgt两个字段的整型数据（要知道整型数据的运算速度是最快的）。
而目前国内大家都是用的一个字符串字段来保存结点的路径，SQL对可索引字符串的长度是有限（Access:255,MSSQL:8000），但如果用备注类型来做的话，就根本没得什么索引和效率可言了。
[quote]
演示测试地址:
http://www.lxasp.com/Test_NestedTree.asp
[/quote]
部分关键代码:
[quote]
[color=#008000]'数据表如下:
'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
[/color][color=#008000]'* 名称: 插入结点到树
'* 日期: 2006-09-20 作者: pkmaster
[/color][color=#0000FF]Function [/color][color=#000000]InsertNew(Parent_ID , NewName)
[/color][color=#0000FF]Dim [/color][color=#000000]p_lft,p_rgt
SQL = [/color][color=#800000]"SELECT * FROM TreeNode WHERE tn_id="[/color][color=#000000]&Parent_ID
[/color][color=#0000FF]Set [/color][color=#000000]rs=Server.CreateObject([/color][color=#800000]"ADODB.Recordset"[/color][color=#000000])
rs.Open SQL,conn,[/color][color=#800080]1[/color][color=#000000],[/color][color=#800080]3 [/color][color=#008000]'11 for Read '13 for Write
[/color][color=#000000]sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#0000FF]If [/color][color=#000000]rs.EOF [/color][color=#0000FF]And [/color][color=#000000]rs.BOF [/color][color=#0000FF]Then
[/color][color=#008000]'不存在Parent_ID，则出错
[/color][color=#0000FF]Else
[/color][color=#000000]rs.MoveFirst
p_lft=rs([/color][color=#800000]"tn_lft"[/color][color=#000000])
p_rgt=rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])
conn.Execute [/color][color=#800000]"UPDATE TreeNode SET tn_rgt=tn_rgt+2 WHERE tn_rgt>" [/color][color=#000000]& CStr(p_rgt-[/color][color=#800080]1[/color][color=#000000])
sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#000000]conn.Execute [/color][color=#800000]"UPDATE TreeNode SET tn_lft=tn_lft+2 WHERE tn_lft>" [/color][color=#000000]& CStr(p_rgt-[/color][color=#800080]1[/color][color=#000000])
sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#000000]rs.AddNew
rs([/color][color=#800000]"tn_lft"[/color][color=#000000])=p_rgt
rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])=p_rgt+[/color][color=#800080]1
[/color][color=#000000]rs([/color][color=#800000]"tn_name"[/color][color=#000000])=NewName
rs.Update
InsertNew=p_rgt+[/color][color=#800080]1
[/color][color=#0000FF]End If
[/color][color=#000000]rs.Close
[/color][color=#0000FF]Set [/color][color=#000000]rs = [/color][color=#0000FF]Nothing
End Function
[/color][color=#008000]'* 名称: 显示整棵树
'* 日期: 2006-09-20 作者: pkmaster
[/color][color=#0000FF]Function [/color][color=#000000]ShowTree()
[/color][color=#0000FF]Dim [/color][color=#000000]stackd,stkpos,STACKMAX
[/color][color=#0000FF]Dim [/color][color=#000000]i,j
i=[/color][color=#800080]0
[/color][color=#000000]j=[/color][color=#800080]0
[/color][color=#000000]STACKMAX=[/color][color=#800080]100
[/color][color=#000000]stkpos=[/color][color=#800080]0
[/color][color=#000000]SQL = [/color][color=#800000]"SELECT * FROM TreeNode ORDER BY tn_lft ASC"
[/color][color=#0000FF]Set [/color][color=#000000]rs=Server.CreateObject([/color][color=#800000]"ADODB.Recordset"[/color][color=#000000])
rs.Open SQL,conn,[/color][color=#800080]1[/color][color=#000000],[/color][color=#800080]1 [/color][color=#008000]'11 for Read '13 for Write
[/color][color=#000000]sqlcount=sqlcount+[/color][color=#800080]1
[/color][color=#0000FF]If [/color][color=#000000]rs.EOF [/color][color=#0000FF]And [/color][color=#000000]rs.BOF [/color][color=#0000FF]Then
Else
ReDim [/color][color=#000000]stackd([/color][color=#800080]0[/color][color=#000000],STACKMAX)
rs.MoveFirst
[/color][color=#0000FF]Do Until [/color][color=#000000]rs.EOF
[/color][color=#0000FF]If [/color][color=#000000]stkpos=[/color][color=#800080]0 [/color][color=#0000FF]Then
[/color][color=#008000]'至少要有一个结点，如果是网站，那么就以该网站的名称作为根结点
[/color][color=#000000]Response.Write rs([/color][color=#800000]"tn_name"[/color][color=#000000]) & vbCrLf
[/color][color=#0000FF]End If
If [/color][color=#000000]stkpos>[/color][color=#800080]0 [/color][color=#0000FF]Then
[/color][color=#008000]'出栈
[/color][color=#0000FF]Do While [/color][color=#000000]stackd([/color][color=#800080]0[/color][color=#000000],stkpos-[/color][color=#800080]1[/color][color=#000000])<rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])
stkpos=stkpos-[/color][color=#800080]1
[/color][color=#0000FF]Loop
[/color][color=#000000]Response.Write Space(stkpos*[/color][color=#800080]4[/color][color=#000000]) & [/color][color=#800000]"(" [/color][color=#000000]& rs([/color][color=#800000]"tn_id"[/color][color=#000000]) & [/color][color=#800000]")" [/color][color=#000000]& rs([/color][color=#800000]"tn_name"[/color][color=#000000]) & vbCrLf
[/color][color=#0000FF]End If
[/color][color=#008000]'进栈
[/color][color=#000000]stkpos=stkpos+[/color][color=#800080]1
[/color][color=#0000FF]If [/color][color=#000000]stkpos-[/color][color=#800080]1[/color][color=#000000]>STACKMAX [/color][color=#0000FF]Then ReDim Preserve [/color][color=#000000]stackd([/color][color=#800080]0[/color][color=#000000],stkpos-[/color][color=#800080]1+[/color][color=#000000]STACKMAX)
stackd([/color][color=#800080]0[/color][color=#000000],stkpos-[/color][color=#800080]1[/color][color=#000000])=rs([/color][color=#800000]"tn_rgt"[/color][color=#000000])
rs.MoveNext
[/color][color=#0000FF]Loop
End If
[/color][color=#000000]rs.Close
[/color][color=#0000FF]Set [/color][color=#000000]rs = [/color][color=#0000FF]Nothing
End Function
[/color][/quote]