1. 引言
網絡信息中心技術資料繁雜，網絡系統規模龐大，設備種類眾多，線路連接關系復雜。技術資料管理系統對所有設備包括服務器、終端、線路、網絡設備等技術資料進行匯總管理，既能為用戶提供更好的服務保障，又能為網絡管理員提供更好的管理功能，因此成為網絡信息中心網絡管理的基礎系統。
在處理各方向的線路或設備故障時，技術資料管理系統可以協助網絡管理員查詢線路或設備連接情況。網絡設備連接情況呈現出來的是一種錯綜復雜的樹狀層次結構，如何在數據庫中將該樹狀層次結構高效直觀的表示出來則是技術資料管理系統的技術要點之一。
樹狀層次結構在數據庫中不僅難以存儲表示，而且將存儲在數據庫里的樹狀層次關系還原也是個難題。目前，樹狀層次結構在數據庫中的表示存在幾種模式。
1.1 adjacency模式
我們最熟悉的表示樹狀層次結構的辦法是adjacency模式，因當前記錄表示節點的父節點也存儲在同一記錄下的相鄰列而得名。假設某員工組織結構表OrgChart如表1所示。顯然，該模式對于尋找某節點的父節點或者同級節點都比較容易實現，然而當需要列出樹狀結構的多層時卻比較低效和困難。
emp boss
'Albert' 'NULL'
'Bert' 'Albert'
'Chuck' 'Albert'
'Donna' 'Chuck'
'Eddie' 'Chuck'
'Fred' 'Chuck'
表1 adjacency模式下員工組織結構表OrgChart
1.2nested set模式
Joe Celko's提出的nested set模式下員工組織結構表OrgChart將轉化為TreeTable產生該表格的SQL語句為：
CREATE TABLE TreeTable
(emp CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt) );
該模式下節點的lft和rgt的算法采用一種預排序的往返樹算法來表示；
I．根節點的lft = 1, rgt = 2 * (SELECT COUNT(*) FROM TreeTable);
II．葉子節點總是滿足lft + 1 = rgt;
III．子節點lft始終大于父節點lft，rgt始終小于父節點rgt，依此類推；
在該算法下表一的組織關系用將會轉化為如圖1所示的樹狀結構。

Albert(1,12)
/ \
/ \
Bert(2,3) Chuck(4,11)
/ ︳ \
/ ︳ \
Donna(5,6) Eddle(7,8) Fred(9,10)

圖1 nested set模式下的員工組織結構樹狀圖

nested set模式盡管能高效且簡單地找出樹層次或子樹層次，但是對于增加、刪除或移動節點等簡單操作都需要對所有的節點進行改動，甚至連尋找父節點或子節點都需要三個自連接和一個子查詢，在這種情況下表現出嚴重的低效性和復雜性。因此在借鑒兩種模式的基礎上，我們在技術資料管理系統中提出了一種新的高效和直觀的樹狀結構表示模式。
2. 設備連接關系在數據庫中的樹狀層次結構實現
假設我們在技術資料管理系統的數據庫中用表EquipConnectTree來表示設備的連接關系樹狀層次結構，我們從常規的adjacency模式結構來逐步推導出本文所述的樹狀層次結構模式，因此表EquipConnectTree的數據是從adjacency模式下的設備連接關系表EquipConnectList轉化而來。

EquipID PortID ParentEquipID ParentPortID
1001 省略 NULL 省略
1002 省略 1001 省略
1003 省略 1002 省略
1004 省略 1003 省略
1005 省略 1003 省略
1006 省略 1003 省略
表2 設備連接關系表EquipConnectList

假設在adjacency模式下設備連接關系表EquipConnectList中的記錄如表2所示，則設備的連接關系樹狀層次結構表EquipConnectTree中數據的產生包括以下步驟：
①根據EquipConnectList填充EquipConnectTree的EquipmentID字段：每一個EquipmentID將代表樹狀連接圖中的一個設備節點，Node（節點號）字段將自動設置。
其SQL語句為：Insert INTO EquipConnectTree(EquipmentID) SELECT EquipId FROM EquipConnectList。執行完畢后表EquipConnectTree的狀態如表3所示。








Node ParentNode EquipmentID Depth Lineage
100 NULL 1001 NULL NULL
101 NULL 1002 NULL NULL
102 NULL 1003 NULL NULL
103 NULL 1004 NULL NULL
104 NULL 1005 NULL NULL
105 NULL 1006 NULL NULL






表3 設備的連接關系樹狀層次結構表EquipConnectTree

②設置EquipConnectTree 表中每個Node（節點）的ParentNode（父節點編號）。
其SQL語句為：UPDATE T SET T.ParentNode=P.Node FROM EquipConnectTree T INNER JOIN EquipConnectList L ON T.EquipmentID=L.EmployeeID INNER JOIN EquipConnectList UP ON L.ParentEquipID=UP.EquipID INNER JOIN EquipConnectTree P ON UP. EquipID =P.EquipmentID。
執行完畢后表EquipConnectTree的狀態如表4所示。

Node ParentNode EquipmentID Depth Lineage
100 NULL 1001 NULL NULL
101 100 1002 NULL NULL
102 101 1003 NULL NULL
103 102 1004 NULL NULL
104 102 1005 NULL NULL
105 102 1006 NULL NULL
表4 設備的連接關系樹狀層次結構表EquipConnectTree

③下面我們將要尋找樹的根，即最頂層節點，這就是沒有ParentNode（NULL）的那個節點，我們將該節點的Lineage（譜系）字段設為“/”，Depth（深度）設為0。
其SQL語句為：UPDATE EquipConnectTree SET Lineage='/', Depth=0 WHERE ParentNode Is Null。
④上一步做完后，我們可以立即更新根節點的直接子節點。
其SQL語句為：UPDATE T SET T.Depth = P.Depth + 1, T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode)) + '/' FROM EquipConnectTree AS T INNER JOIN EquipConnectTree AS P ON (T.ParentNode=P.Node) WHERE P.Depth>=0 AND P.Lineage Is Not Null AND T.Depth Is Null
⑤實際上，我們可以用一個循環把樹中的所有的子孫節點遍歷一遍，從而把樹中所有記錄的Depth字段和Lineage字段的值確定下來。
其SQL語句為：WHILE EXISTS (SELECT * FROM EquipConnectTree WHERE Depth Is Null) UPDATE T SET T.depth = P.Depth + 1, T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode)) + '/' FROM EquipConnectTree AS T INNER JOIN EquipConnectTree AS P ON (T.ParentNode=P.Node) WHERE P.Depth>=0 AND P.Lineage Is Not Null AND T.Depth Is Null。
最終的結果如表5所示。

Node ParentNode EquipmentID Depth Lineage
100 NULL 1001 0 /
101 100 1002 1 /100/
102 101 1003 2 /100/101/
103 102 1004 3 /100/101/102/
104 102 1005 3 /100/101/102/
105 102 1006 3 /100/101/102
表5 EquipConnectTree最后狀態

我們看到，對于每一個節點，其Lineage字段保存了它完整的譜系。在該表中尋找某一設備節點的上層設備節點，或者上層的上層設備節點變得非常簡單，甚至描述整個樹狀視圖也只需一條SELECT語句：SELECT Space(T.Depth*2) + E.EquippmentName AS Name FROM EquippmentInfo E INNER JOIN EquipConnectTree T ON E.EquippmentID=T.EquippmentID ORDER BY T.Lineage + Ltrim(Str(T.Node))。
3. 結束語
采用該樹狀層次結構的實現模式，無論是要尋找某網絡設備如交換機的上面若干層節點或者下面若干層節點都非常簡單，而且對于增加、刪除或者改動網絡設備節點也非常容易實現，與adjacency模式或nested set模式相比，其效率的提高非常顯著，在該數據庫模式的基礎上實現的技術資料管理系統其結構簡單清晰，具有更強的可用性和可維護性。

參考文獻
[1] Rob Volk. More Trees & Hierarchies in SQL.Dec 2002
[2] Eugene Lepekhin..Trees in SQL databases. May 2004
[3] Joe Celko. Tree nested set model. Jun 2006<