一種大型動(dòng)態(tài)目錄樹(shù)的構(gòu)建及管理方法

趙曉峰

（信息工程大學(xué)洛陽(yáng)校區(qū)，河南洛陽(yáng) 471003）

0 引言

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

1 樹(shù)的數(shù)據(jù)庫(kù)設(shè)計(jì)

在信息管理系統(tǒng)中，樹(shù)目錄的存儲(chǔ)一般是依托SQL數(shù)據(jù)庫(kù)進(jìn)行的，由于本文主要針對(duì)傳統(tǒng)C/S和B/S信息管理系統(tǒng)中的樹(shù)目錄開(kāi)發(fā)設(shè)計(jì)，樹(shù)的數(shù)據(jù)庫(kù)設(shè)計(jì)同樣基于SQL 數(shù)據(jù)庫(kù)，在此基礎(chǔ)上，結(jié)合實(shí)際開(kāi)發(fā)有所優(yōu)化。樹(shù)目錄的存儲(chǔ)一般通過(guò)建立一張二維的關(guān)系表來(lái)表示，表字段至少包含以下三個(gè)：Node_id、Node_name、Parent_id，通過(guò)這三個(gè)字段的記錄內(nèi)容就可以完整地表示一棵樹(shù)，但該樹(shù)沒(méi)有表示出同一層級(jí)下的節(jié)點(diǎn)順序關(guān)系，因此，需要增加一個(gè)字段Node_no來(lái)表示節(jié)點(diǎn)的顯示順序，同時(shí)也有利于優(yōu)化程序開(kāi)發(fā)[2-3]。

為了便于實(shí)現(xiàn)程序?qū)φ麄€(gè)樹(shù)形組織結(jié)構(gòu)以及對(duì)歸屬于樹(shù)節(jié)點(diǎn)的實(shí)體信息進(jìn)行動(dòng)態(tài)管理，需建立另外兩張表，下面以武器裝備分類樹(shù)為例進(jìn)行說(shuō)明。

首先通過(guò)表1定義武器裝備分類樹(shù)的根名稱和根代碼，然后根據(jù)表1 定義好的根名稱和根代碼在表2初始化時(shí)生成第一條節(jié)點(diǎn)數(shù)據(jù)，即根節(jié)點(diǎn)數(shù)據(jù)，其父節(jié)點(diǎn)代碼定義為-1，節(jié)點(diǎn)序號(hào)定義為0，而后逐次生成其他節(jié)點(diǎn)及其子節(jié)點(diǎn)數(shù)據(jù)，表3則是具體的武器裝備實(shí)體信息，通過(guò)類別代碼與表2進(jìn)行關(guān)聯(lián)。這里的關(guān)鍵在于樹(shù)結(jié)構(gòu)表的構(gòu)建，算法設(shè)計(jì)見(jiàn)下文。

表1 樹(shù)名稱表

表2 樹(shù)結(jié)構(gòu)表

表3 實(shí)體信息表

2 樹(shù)節(jié)點(diǎn)編碼規(guī)則

良好的編碼規(guī)則對(duì)樹(shù)組織結(jié)構(gòu)的管理至關(guān)重要，通過(guò)編碼能夠基本反映出各節(jié)點(diǎn)之間的層級(jí)關(guān)系和先后關(guān)系[4]，而后通過(guò)良好的程序設(shè)計(jì)進(jìn)行數(shù)據(jù)的批量維護(hù)，既支持通過(guò)系統(tǒng)界面的方式對(duì)目錄樹(shù)進(jìn)行管理，也可批量導(dǎo)出至Excel 表方便人工進(jìn)行校對(duì)和管理，修改完成后再導(dǎo)入至信息管理系統(tǒng)中。

下面以組織機(jī)構(gòu)為例進(jìn)行說(shuō)明，樹(shù)節(jié)點(diǎn)編碼規(guī)則如下表所示：

上表中的“Z”為樹(shù)根節(jié)點(diǎn)代碼，每多出一個(gè)層級(jí)，在其后加“-”符號(hào)，并以數(shù)字1順序編號(hào)，節(jié)點(diǎn)編碼中有多少個(gè)“-”就代表該節(jié)點(diǎn)屬于多少級(jí)的節(jié)點(diǎn)，最后一位數(shù)字代表該節(jié)點(diǎn)在對(duì)應(yīng)層級(jí)中的顯示位置，例如“Z-1-2-1-1-1”屬于第五級(jí)的第一個(gè)節(jié)點(diǎn)。利用XMind思維導(dǎo)圖軟件可以設(shè)計(jì)目錄樹(shù)數(shù)據(jù)，然后導(dǎo)出表4或表5形式的Excel表，再根據(jù)上述的編碼設(shè)計(jì)方式，寫入數(shù)據(jù)庫(kù)表中完成樹(shù)的構(gòu)建。

表4 組織機(jī)構(gòu)目錄樹(shù)Excel表形式1

表5 組織機(jī)構(gòu)目錄樹(shù)Excel表形式2

3 目錄樹(shù)的快速構(gòu)建與遍歷

有了目錄樹(shù)的數(shù)據(jù)庫(kù)表設(shè)計(jì)和樹(shù)節(jié)點(diǎn)編碼規(guī)則作基礎(chǔ)，接下來(lái)就是如何通過(guò)程序算法實(shí)現(xiàn)目錄樹(shù)的快速構(gòu)建與遍歷。通常情況下，初始的時(shí)候一般通過(guò)導(dǎo)入Excel 表的方式進(jìn)行樹(shù)節(jié)點(diǎn)的批量寫入，以此來(lái)完成整個(gè)目錄樹(shù)的構(gòu)建，這樣比較快速高效，避免逐個(gè)進(jìn)行樹(shù)節(jié)點(diǎn)的添加和維護(hù)，尤其是當(dāng)樹(shù)節(jié)點(diǎn)數(shù)量比較大時(shí)更加實(shí)用。

首先給出通過(guò)Excel表導(dǎo)入方式快速構(gòu)建目錄樹(shù)的算法偽代碼描述：

4 目錄樹(shù)的動(dòng)態(tài)管理

目錄樹(shù)的動(dòng)態(tài)管理主要包括添加樹(shù)節(jié)點(diǎn)、刪除樹(shù)節(jié)點(diǎn)、通過(guò)名稱精確或模糊查詢樹(shù)節(jié)點(diǎn)、導(dǎo)入全部或部分目錄樹(shù)、導(dǎo)出Excel 表等操作。添加和刪除樹(shù)節(jié)點(diǎn)操作比較簡(jiǎn)單，導(dǎo)入全部目錄樹(shù)的操作在上文中已做說(shuō)明，導(dǎo)入部分目錄樹(shù)的操作與其相同，設(shè)計(jì)該功能的目的是適應(yīng)數(shù)據(jù)量特別大時(shí)，多人分別進(jìn)行子目錄樹(shù)編輯，最后再分別導(dǎo)入完成目錄樹(shù)構(gòu)建。

這里，主要對(duì)模糊查詢樹(shù)節(jié)點(diǎn)和導(dǎo)出樹(shù)目錄Excel 文件分別進(jìn)行算法說(shuō)明，首先給出模糊查詢樹(shù)節(jié)點(diǎn)算法執(zhí)行步驟，如下：

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

第2 步：定義用于檢查重復(fù)數(shù)據(jù)的idList，存放查詢結(jié)果中的nodeid；

第3步：定義按nodename進(jìn)行模糊查詢的SQL語(yǔ)句，將執(zhí)行結(jié)果返回至DataSet；

第4步：遍歷DataSet，循環(huán)執(zhí)行步驟5、6；

第5步：獲取每行的節(jié)點(diǎn)數(shù)據(jù)，添加至nodeTable，添加nodeid至idList中；

第6 步：獲取該節(jié)點(diǎn)的所有父節(jié)點(diǎn)數(shù)據(jù)，如果nodeid 在idList 中不存在，則添加父節(jié)點(diǎn)數(shù)據(jù)至nodeTable，添加nodeid至idList中；

第7步：對(duì)nodeTable按nodeid升序排序；

第8步：將nodeTable通過(guò)哈希表構(gòu)建的方式加入目錄樹(shù)顯示控件TreeView1。

接下來(lái)是導(dǎo)出樹(shù)目錄Excel 文件算法執(zhí)行步驟描述：

第1 步：定義用于存放目錄樹(shù)所有節(jié)點(diǎn)的List＜TreeNode＞，記為nodeList；

第2 步：從TreeView1 根節(jié)點(diǎn)開(kāi)始，遍歷得到所有子節(jié)點(diǎn)，逐個(gè)添加至nodeList中；

第3步：遍歷nodeList，循環(huán)執(zhí)行步驟4、5、6；

第4 步：獲 取nodeList 中 的TreeNode，定 義 棧stack，并將TreeNode的父節(jié)點(diǎn)全部壓棧；

第5 步：對(duì)stack 中的全部節(jié)點(diǎn)進(jìn)行循環(huán)出棧操作，每個(gè)節(jié)點(diǎn)名稱用“ ”分割連接；

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

5 目錄樹(shù)的快速加載與顯示

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

頁(yè)面或窗體初始化時(shí)，執(zhí)行如下步驟：

第1步：樹(shù)顯示控件TreeView1添加根節(jié)點(diǎn)；

第2步：為了便于點(diǎn)擊“+”展開(kāi)，判斷根節(jié)點(diǎn)的子節(jié)點(diǎn)是否為空，如果不空，添加一個(gè)空的TreeNode；

第3步：關(guān)閉TreeView1的所有節(jié)點(diǎn)。

點(diǎn)擊“+”進(jìn)行節(jié)點(diǎn)展開(kāi)事件時(shí)，執(zhí)行如下步驟：

第1步：首先獲取當(dāng)前選擇節(jié)點(diǎn)的nodeid，然后到數(shù)據(jù)庫(kù)表中查詢?cè)摴?jié)點(diǎn)的下一級(jí)子節(jié)點(diǎn)，結(jié)果返回至DataTable；

第2步：清除之前加載的空節(jié)點(diǎn)；

第3步：遍歷DataTable，循環(huán)執(zhí)行步驟4、5；

第4 步：獲取每行數(shù)據(jù)，生成TreeNode，記為cNode，往當(dāng)前節(jié)點(diǎn)上逐個(gè)添加cNode；

第5 步：判斷cNode 的子節(jié)點(diǎn)是否為空，如果不空，添加一個(gè)空的TreeNode。

6 結(jié)束語(yǔ)

本文著重從實(shí)踐角度對(duì)動(dòng)態(tài)目錄樹(shù)的構(gòu)建及管理方法進(jìn)行闡述，所提出的方法已應(yīng)用到多個(gè)信息管理系統(tǒng)中，通用性較強(qiáng)。目錄樹(shù)的節(jié)點(diǎn)數(shù)量級(jí)在20萬(wàn)以上時(shí)，加載和查詢的速度均在毫秒級(jí)，尤其是目錄樹(shù)的構(gòu)建可以采用多人按模板編輯Excel構(gòu)建目錄子樹(shù)，而后再分別導(dǎo)入系統(tǒng)的方式，大大節(jié)省了構(gòu)建時(shí)間。