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

最新評論