一種大型動態目錄樹的構建及管理方法

趙曉峰

（信息工程大學洛陽校區，河南洛陽 471003）

0 引言

現實世界當中，樹目錄的組織結構應用非常廣泛，例如：一個單位的組織機構、一個國家的行政區劃、學科分類、武器裝備分類、文件組織結構等，一個信息系統的開發更離不開目錄樹的構建及管理，尤其是當組織結構非常龐大的時候，如果設計不好，效率會非常影響信息系統的正常使用，主要表現在：第一、構建一棵完整的目錄樹需要花費相當長的時間；第二、加載和顯示目錄樹的時間也比較長；第三、當該目錄樹需要修改的節點比較多時，逐一進行維護，效率會比較低；第四、當一棵樹的層級和節點數量特別大時，加載的時間會相當長，嚴重影響用戶體驗；第五、樹節點的查詢存在一定的難度[1]。針對上述幾點問題，結合作者自身的開發體驗，提出了一種大型目錄樹的構建及管理方法。全文的結構安排如下：第一節為樹目錄的數據庫設計；第二節為樹節點的編碼規則設計；第三節為大型目錄樹的快速構建與遍歷；第四節為大型目錄樹的動態管理；第五節為大型目錄樹的快速加載與顯示；最后一節為小結。

1 樹的數據庫設計

在信息管理系統中，樹目錄的存儲一般是依托SQL數據庫進行的，由于本文主要針對傳統C/S和B/S信息管理系統中的樹目錄開發設計，樹的數據庫設計同樣基于SQL 數據庫，在此基礎上，結合實際開發有所優化。樹目錄的存儲一般通過建立一張二維的關系表來表示，表字段至少包含以下三個：Node_id、Node_name、Parent_id，通過這三個字段的記錄內容就可以完整地表示一棵樹，但該樹沒有表示出同一層級下的節點順序關系，因此，需要增加一個字段Node_no來表示節點的顯示順序，同時也有利于優化程序開發[2-3]。

為了便于實現程序對整個樹形組織結構以及對歸屬于樹節點的實體信息進行動態管理，需建立另外兩張表，下面以武器裝備分類樹為例進行說明。

首先通過表1定義武器裝備分類樹的根名稱和根代碼，然后根據表1 定義好的根名稱和根代碼在表2初始化時生成第一條節點數據，即根節點數據，其父節點代碼定義為-1，節點序號定義為0，而后逐次生成其他節點及其子節點數據，表3則是具體的武器裝備實體信息，通過類別代碼與表2進行關聯。這里的關鍵在于樹結構表的構建，算法設計見下文。

表1 樹名稱表

表2 樹結構表

表3 實體信息表

2 樹節點編碼規則

良好的編碼規則對樹組織結構的管理至關重要，通過編碼能夠基本反映出各節點之間的層級關系和先后關系[4]，而后通過良好的程序設計進行數據的批量維護，既支持通過系統界面的方式對目錄樹進行管理，也可批量導出至Excel 表方便人工進行校對和管理，修改完成后再導入至信息管理系統中。

下面以組織機構為例進行說明，樹節點編碼規則如下表所示：

上表中的“Z”為樹根節點代碼，每多出一個層級，在其后加“-”符號，并以數字1順序編號，節點編碼中有多少個“-”就代表該節點屬于多少級的節點，最后一位數字代表該節點在對應層級中的顯示位置，例如“Z-1-2-1-1-1”屬于第五級的第一個節點。利用XMind思維導圖軟件可以設計目錄樹數據，然后導出表4或表5形式的Excel表，再根據上述的編碼設計方式，寫入數據庫表中完成樹的構建。

表4 組織機構目錄樹Excel表形式1

表5 組織機構目錄樹Excel表形式2

3 目錄樹的快速構建與遍歷

有了目錄樹的數據庫表設計和樹節點編碼規則作基礎，接下來就是如何通過程序算法實現目錄樹的快速構建與遍歷。通常情況下，初始的時候一般通過導入Excel 表的方式進行樹節點的批量寫入，以此來完成整個目錄樹的構建，這樣比較快速高效，避免逐個進行樹節點的添加和維護，尤其是當樹節點數量比較大時更加實用。

首先給出通過Excel表導入方式快速構建目錄樹的算法偽代碼描述：

4 目錄樹的動態管理

目錄樹的動態管理主要包括添加樹節點、刪除樹節點、通過名稱精確或模糊查詢樹節點、導入全部或部分目錄樹、導出Excel 表等操作。添加和刪除樹節點操作比較簡單，導入全部目錄樹的操作在上文中已做說明，導入部分目錄樹的操作與其相同，設計該功能的目的是適應數據量特別大時，多人分別進行子目錄樹編輯，最后再分別導入完成目錄樹構建。

這里，主要對模糊查詢樹節點和導出樹目錄Excel 文件分別進行算法說明，首先給出模糊查詢樹節點算法執行步驟，如下：

第1 步：定義用于存放模糊查詢結果的DataTable，列信息包括nodeid、nodename 和parentid，記為nodeTable；

第2 步：定義用于檢查重復數據的idList，存放查詢結果中的nodeid；

第3步：定義按nodename進行模糊查詢的SQL語句，將執行結果返回至DataSet；

第4步：遍歷DataSet，循環執行步驟5、6；

第5步：獲取每行的節點數據，添加至nodeTable，添加nodeid至idList中；

第6 步：獲取該節點的所有父節點數據，如果nodeid 在idList 中不存在，則添加父節點數據至nodeTable，添加nodeid至idList中；

第7步：對nodeTable按nodeid升序排序；

第8步：將nodeTable通過哈希表構建的方式加入目錄樹顯示控件TreeView1。

接下來是導出樹目錄Excel 文件算法執行步驟描述：

第1 步：定義用于存放目錄樹所有節點的List＜TreeNode＞，記為nodeList；

第2 步：從TreeView1 根節點開始，遍歷得到所有子節點，逐個添加至nodeList中；

第3步：遍歷nodeList，循環執行步驟4、5、6；

第4 步：獲 取nodeList 中 的TreeNode，定 義 棧stack，并將TreeNode的父節點全部壓棧；

第5 步：對stack 中的全部節點進行循環出棧操作，每個節點名稱用“ ”分割連接；

第6步：按行寫入輸出的Excel文件中。

5 目錄樹的快速加載與顯示

當目錄樹節點特別多的時候，加載顯示的時間會比較長，尤其是節點在10萬以上的大型目錄樹，嚴重影響用戶體驗。這時主要的處理方式就是初始時并不完全加載所有節點，而是在逐層展開時再加載其子節點，每點擊一個“+”號，僅加載該節點的下一級所有節點，這樣采用需要時再加載的方式，將顯示時間分散到了各點擊展開事件，能夠大大改善用戶體驗。算法設計的思路很簡單，主要是進行巧妙的編程，目錄樹的加載和展開事件程序設計流程描述如下。

頁面或窗體初始化時，執行如下步驟：

第1步：樹顯示控件TreeView1添加根節點；

第2步：為了便于點擊“+”展開，判斷根節點的子節點是否為空，如果不空，添加一個空的TreeNode；

第3步：關閉TreeView1的所有節點。

點擊“+”進行節點展開事件時，執行如下步驟：

第1步：首先獲取當前選擇節點的nodeid，然后到數據庫表中查詢該節點的下一級子節點，結果返回至DataTable；

第2步：清除之前加載的空節點；

第3步：遍歷DataTable，循環執行步驟4、5；

第4 步：獲取每行數據，生成TreeNode，記為cNode，往當前節點上逐個添加cNode；

第5 步：判斷cNode 的子節點是否為空，如果不空，添加一個空的TreeNode。

6 結束語

本文著重從實踐角度對動態目錄樹的構建及管理方法進行闡述，所提出的方法已應用到多個信息管理系統中，通用性較強。目錄樹的節點數量級在20萬以上時，加載和查詢的速度均在毫秒級，尤其是目錄樹的構建可以采用多人按模板編輯Excel構建目錄子樹，而后再分別導入系統的方式，大大節省了構建時間。