景 民， 萬其明， 韓志軍， 楊艷萍

（1.61001部隊(duì)，北京 100093；2.國防大學(xué) 信息作戰(zhàn)與指揮訓(xùn)練教研部，北京 100091；3.中山職業(yè)技術(shù)學(xué)院，廣東 中山 528404；4.海軍裝備研究院，北京 100036）

樹形顯示（TreeView）很適合表現(xiàn)具有分支和層次聯(lián)系的數(shù)據(jù)，如操作系統(tǒng)中的目錄樹，信息系統(tǒng)的行政區(qū)劃導(dǎo)航樹，安全控制系統(tǒng)中的訪問權(quán)限樹等，因此在系統(tǒng)開發(fā)中，經(jīng)常使用樹形結(jié)構(gòu)來顯示和存儲層次數(shù)據(jù)。樹形結(jié)構(gòu)的算法和實(shí)現(xiàn)也是計算機(jī)工程的一個研究熱點(diǎn)：文獻(xiàn)［1］比較了在內(nèi)存中生成目錄樹的2種算法的效率，結(jié)論是深度優(yōu)先算法（Depth－First Algorithm，簡稱DFA）比 直 接 插 入 算 法 （Insert－into－Tree Algorithm，簡稱ITA）在給定試驗(yàn)中效率高2～3倍；文獻(xiàn)［2］提出了一種生成目錄樹的快速算法，該算法以先根遍歷（preorder traversal）順序預(yù)先將目錄數(shù)據(jù)存入數(shù)據(jù)庫中，然后支持對數(shù)據(jù)庫一次訪問快速生成目錄樹；文獻(xiàn)［3］提出一種在 Web中生成動態(tài)目錄樹的方法，實(shí)現(xiàn)了在Web中樹形顯示，利用鏈表預(yù)先將數(shù)據(jù)庫中的目錄數(shù)據(jù)讀入內(nèi)存，并采用ITA算法完成目錄樹的生成；文獻(xiàn)［4］介紹了一種窗體編程工具提供的TreeView控件，并演示了利用該控件讀取數(shù)據(jù)庫中的目錄樹結(jié)構(gòu)；文獻(xiàn)［5］介紹了ASP.NET中提供的TreeView控件，采取先根順序預(yù)先將目錄數(shù)據(jù)存在數(shù)據(jù)庫，并采用DFA算法實(shí)現(xiàn)了動態(tài)目錄樹的生成。

本文以某大型通用檔案文獻(xiàn)系統(tǒng)（DAG）的開發(fā)為背景，重點(diǎn)研究了基于數(shù)據(jù)庫的動態(tài)Web角色權(quán)限樹的設(shè)計和實(shí)現(xiàn)，如圖1所示。DAG系統(tǒng)管理檔案全宗有上百種，但測試用戶11111111僅能看到其中3個全宗的文書檔案信息和部分科技檔案和專門檔案。該用戶擁有的檔案樹結(jié)點(diǎn)達(dá)到100個左右，而對于管理員級別的超級用戶，擁有的檔案樹結(jié)點(diǎn)規(guī)模可以達(dá)到105左右。當(dāng)前在Web上快速顯示具有大量結(jié)點(diǎn)的動態(tài)樹是比較困難的，如何高效管理這些層次數(shù)據(jù)也是一項(xiàng)困難的任務(wù)。本文的研究目的旨在解決以上問題，涉及的關(guān)鍵技術(shù)主要包括：① 實(shí)現(xiàn)基于Web的樹形顯示組件；② 實(shí)現(xiàn)用戶權(quán)限樹與數(shù)據(jù)表結(jié)構(gòu)的動態(tài)對應(yīng)；③ 基于數(shù)據(jù)庫快速生成權(quán)限樹的算法［6］。

圖1 DAG的Web展現(xiàn)系統(tǒng)某授權(quán)用戶的檔案樹視圖

1 Web樹形顯示組件的實(shí)現(xiàn)

目前很多應(yīng)用開發(fā)工具，如Visual Studio、Delphi、PB等，都提供了TreeView控件，在窗體應(yīng)用程序中使用TreeView控件的應(yīng)用已相當(dāng)成熟，然而開發(fā)Web程序時實(shí)現(xiàn)樹形顯示還比較困難［5］。雖然已有廠商提供了基于 Web的Tree－View控件，如 Microsoft提供了 ASP.NET［5］技術(shù)，文獻(xiàn)［7］在Delphi的較高版本中提供了IntraWeb技術(shù)，但使用它們的代價是必須部署龐大的.NET Framework類庫，或者需要開發(fā)專門的服務(wù)支持進(jìn)程，這些都對服務(wù)器的性能和配置提出了更高要求，而且影響到Web應(yīng)用的跨平臺部署和訪問，這些限制增加了開發(fā)基于Web的樹形顯示的困難。在DAG系統(tǒng)的開發(fā)中，由于硬件保密設(shè)備的兼容要求，也限定了只能選擇先前比較成熟的Web開發(fā)技術(shù)，因此沒有現(xiàn)成的Tree－View控件可用，需要手工編寫用于Web的樹形顯示控件。

JavaScript是Web上的一種功能強(qiáng)大的基于對象的腳本編程語言，它既可以直接應(yīng)用于客戶端的HTML文檔以獲得交互動態(tài)效果，還可以嵌入ASP、JSP或PHP中運(yùn)行于Web服務(wù)器端，因而JavaScript具有廣泛的適用性和跨平臺性，獲得絕大多數(shù)瀏覽器的支持［8］。文獻(xiàn)［3］即采用了JavaScript實(shí)現(xiàn)了用于Web的樹形顯示，但由于其采用了JavaScript和HTML混合編程方式，并沒有實(shí)現(xiàn)JavaScript的行為代碼與HTML的格式代碼的分離，而且實(shí)現(xiàn)的樹形顯示功能也較簡單。DAG的Web展現(xiàn)系統(tǒng)利用JavaScript實(shí)現(xiàn)一個功能完善且應(yīng)用簡單的樹形顯示組件WebTreeView，其主要特點(diǎn)如下：

（1）利用基于對象的事件驅(qū)動模型實(shí)現(xiàn)了樹形顯示組件的類封裝。組件實(shí)現(xiàn)代碼統(tǒng)一保存在腳本文件web－tree－view.js中，使JavaScript的事件邏輯代碼與HTML的格式代碼分開，增強(qiáng)了程序可理解性和代碼復(fù)用性。

（2）WebTreeView組件提供了豐富的屬性和方法。組件主要包括2個對象：Web－Tree－View和Web－Tree－Node，前者用于顯示一棵完整的Web樹，后者實(shí)現(xiàn)了一個完整的樹結(jié)點(diǎn)功能。

（3）WebTreeView組件應(yīng)用非常方便。由于實(shí)現(xiàn)了類封裝，可以方便地在HTML中對樹對象進(jìn)行調(diào)用和操作，其應(yīng)用示例代碼和顯示效果，如圖2所示。

圖2 WebTreeView組件在HTML中的調(diào)用代碼及相應(yīng)的Web顯示效果

2 權(quán)限樹與數(shù)據(jù)表結(jié)構(gòu)的動態(tài)對應(yīng)

本節(jié)解決對眾多用戶的動態(tài)訪問權(quán)限的分配和管理問題。設(shè)計權(quán)限樹結(jié)構(gòu)比目錄樹復(fù)雜，因?yàn)镈AG系統(tǒng)每個用戶將對應(yīng)一棵具有相當(dāng)規(guī)模結(jié)點(diǎn)的目錄樹（授權(quán)檔案樹），假設(shè)每個用戶的檔案樹平均包含500個結(jié)點(diǎn)，系統(tǒng)支持10 000個用戶，將所有用戶的結(jié)點(diǎn)信息都存儲在一個表中將達(dá)到500×104的記錄規(guī)模。DAG系統(tǒng)設(shè)計了用戶表User－Table、角色表Role－Table和檔案樹權(quán)限表Tree－Table，數(shù)據(jù)表設(shè)計如圖3所示。DAG系統(tǒng)引入角色概念，用來連接用戶和檔案樹，既有效降低了數(shù)據(jù)規(guī)模，又簡化了授權(quán)過程。Tree－Table的主要屬性包括 Node－ID、Node－Text、Parent－ID、Node－Level等，利用這些屬性可以重構(gòu)一棵樹。圖3所示只是構(gòu)建角色權(quán)限樹的一些關(guān)鍵字段，其他一些附加信息并未在圖中顯示。

利用這3個表就可以實(shí)現(xiàn)用戶與角色，角色和權(quán)限樹之間的動態(tài)對應(yīng)，由于權(quán)限樹不像一般的靜態(tài)目錄樹，權(quán)限樹需要經(jīng)常進(jìn)行授權(quán)調(diào)整，所以該表要經(jīng)常進(jìn)行插入、刪除和更新操作，使得表中的記錄不可能保持一種固定的順序，因此文獻(xiàn)［2，5］采取的預(yù)先按先根順序在數(shù)據(jù)庫中存儲數(shù)據(jù)的做法在此無法適用。本文采取這種表設(shè)計結(jié)構(gòu)既支持Web中樹形顯示隨數(shù)據(jù)表內(nèi)容動態(tài)生成，也支持?jǐn)?shù)據(jù)表記錄的動態(tài)改變，是一種支持完全動態(tài)的設(shè)計結(jié)構(gòu)。

圖3 DAG系統(tǒng)中動態(tài)權(quán)限樹的數(shù)據(jù)表設(shè)計結(jié)構(gòu)

3 權(quán)限樹快速生成算法

3.1 算法A1與分析

通常在數(shù)據(jù)庫中讀取記錄生成樹結(jié)構(gòu)的算法A1如下：

／／算法所涉及記錄都是屬于某一固定的角色，即Role－ID為一固定值。

（1）取出該Role－ID下所有記錄中Node－Level的最大值M。

（2）n：＝0，從表中取出Node－Level＝0的結(jié)點(diǎn)，作為根生成樹T。

（3）n：＝n＋1，對于T中Level＝n－1的每個結(jié)點(diǎn)，從表中讀取其子結(jié)點(diǎn)，按Node－ID升序依次添加到T中的相應(yīng)位置。

（4）重復(fù)步驟（3），直到n＝M－1，樹T生成完畢。

算法A1采取了一種層次優(yōu)先法（Breadth First Search，簡稱BFS），BFS是最簡單的樹遍歷算法之一［9］。算法A1是一種“父結(jié)點(diǎn)找子結(jié)點(diǎn)”的算法，預(yù)先生成父節(jié)點(diǎn)，然后根據(jù)父結(jié)點(diǎn)再到數(shù)據(jù)庫中找出該結(jié)點(diǎn)的子結(jié)點(diǎn)。下面分析算法A1的效率，由于這段算法涉及多次數(shù)據(jù)庫中查詢?nèi)プx取記錄，一般讀取本地的數(shù)據(jù)庫需要進(jìn)行磁盤的I／O操作，時間比內(nèi)存操作費(fèi)時，讀取網(wǎng)絡(luò)數(shù)據(jù)庫還涉及建立網(wǎng)絡(luò)連接等時間開銷，更加費(fèi)時，一般一次磁盤I／O操作是一次內(nèi)存操作時間的105倍左右，所以分析既包括內(nèi)存操作又包括磁盤操作算法效率時，內(nèi)存操作的時間基本可以忽略不計，因此可以把磁盤I／O次數(shù)作為衡量算法時間效率的指標(biāo)。

假設(shè)樹T是一個m層的完全n叉數(shù)，則共需要的I／O次數(shù)N為：

所以，算法A1是一個時間開銷隨著n和m成指數(shù)增長的算法，當(dāng)n和m比較小時，比如m、n都為3時，N為5次；m、n都等于4時，N為22次；m、n都等于5時，N已經(jīng)超過100次；m、n都為6時，N已超過1 000次；而當(dāng)m、n各等于10時，N便超過了109次。假設(shè)一次數(shù)據(jù)庫訪問時間為1s，當(dāng)樹的層數(shù)和叉數(shù)各為5時，所需時間就超過了100s，因此當(dāng)生成的樹超過一定規(guī)模，高昂的時間開銷就令算法A1失去了實(shí)用價值。

在實(shí)際的系統(tǒng)實(shí)現(xiàn)中，可以針對算法A1時間開銷大的弊端進(jìn)行改進(jìn)和優(yōu)化，如系統(tǒng)初次運(yùn)行時只生成部分樹結(jié)點(diǎn)，比如只生成樹的一級結(jié)點(diǎn)，待用戶需要點(diǎn)擊展開某個結(jié)點(diǎn)的時候，再去訪問一次數(shù)據(jù)庫將該結(jié)點(diǎn)下面的結(jié)點(diǎn)生成出來，通常一次數(shù)據(jù)庫訪問的時間是秒級，對于幾秒的等待時間用戶并不會覺得慢，這也是很多系統(tǒng)采用的一種實(shí)際做法。然后這種一次僅生成部分樹的折中做法，雖然解決了用戶等待時間過長的問題，卻滿足不了展開全部結(jié)點(diǎn)的需求，比如有時某些查詢和統(tǒng)計功能需要一次生成整棵樹。

針對上述2種做法的不足，有些系統(tǒng)會采取一次將涉及的全部結(jié)點(diǎn)讀取到內(nèi)存中的線性表，然后再對線性表操作進(jìn)行樹的重構(gòu)，比如文獻(xiàn)［3］，這樣雖然可以加快樹的生成，但卻耗費(fèi)額外的內(nèi)存空間，降低了算法的空間效率。

算法A1之所以頻繁訪問數(shù)據(jù)庫，是因?yàn)樵跇渖傻倪^程中，當(dāng)生成了一個結(jié)點(diǎn)后，然后就為該結(jié)點(diǎn)到數(shù)據(jù)庫中找到它所有的子結(jié)點(diǎn)，這種父結(jié)點(diǎn)找子結(jié)點(diǎn)的做法決定了算法A1必須多次訪問數(shù)據(jù)庫，因?yàn)樽咏Y(jié)點(diǎn)還在數(shù)據(jù)庫的表中。如果將這個過程逆過來，在樹生成的時候，讓子結(jié)點(diǎn)主動找父結(jié)點(diǎn)，由于父結(jié)點(diǎn)已早于子結(jié)點(diǎn)在內(nèi)存中生成，子結(jié)點(diǎn)可以快速地在內(nèi)存中找到父結(jié)點(diǎn)，然后加入到內(nèi)存的樹中。子結(jié)點(diǎn)找父結(jié)點(diǎn)是在內(nèi)存中進(jìn)行，而父結(jié)點(diǎn)找子結(jié)點(diǎn)卻需要讀庫，這是兩者存在巨大時間差別的關(guān)鍵所在。

3.2 本文算法與分析

本文依據(jù)前面設(shè)計的動態(tài)數(shù)據(jù)表結(jié)構(gòu)，提出一種新算法A2，算法A2在不增加額外內(nèi)存空間的情況下，實(shí)現(xiàn)了對數(shù)據(jù)庫一次訪問快速生成全部樹結(jié)構(gòu)。

將算法A1的過程逆向，即“父結(jié)點(diǎn)找子結(jié)點(diǎn)”的過程改為“子結(jié)點(diǎn)找父結(jié)點(diǎn)”，就得到了算法A2，算法A2的實(shí)現(xiàn)也很簡單，共分為2步：

（1）在數(shù)據(jù)庫中按先根順序訪問Tree－Table中Role－ID為某一固定值的所有結(jié)點(diǎn)，在訪問每一個記錄時進(jìn)行步驟（2）。

（2）根據(jù)該記錄生成一個樹結(jié)點(diǎn)，按深度優(yōu)先算法（DFA）插入到樹T中。

第2步完全在內(nèi)存中進(jìn)行，而且采用了效率較高的 DFA 算法［1］，DFA 算法可參閱文獻(xiàn)［1，9］，在此不再贅述。

第1步是實(shí)現(xiàn)算法A2的關(guān)鍵，實(shí)現(xiàn)了對表Tree－Table的一次訪問，取出所需要的全部記錄，下面對該步實(shí)現(xiàn)過程進(jìn)行詳細(xì)說明。按先根順序返回結(jié)點(diǎn)記錄，第1條記錄代表根結(jié)點(diǎn)。要想在數(shù)據(jù)庫中得到這樣的記錄順序，最理想的情況是表中的記錄預(yù)先按這種順序保存，如文獻(xiàn)［2，5］就采用了這樣的做法。按序預(yù)先存儲記錄對于靜態(tài)的目錄樹結(jié)構(gòu)是可以的，但是對于動態(tài)的權(quán)限樹，由于經(jīng)常需要對權(quán)限進(jìn)行重新分配，造成Tree－Table的頻繁操作，使其不能保持一種固定的順序。一個很自然的想法是每次訪問前對表重新排序，然而對表重新排序是一個很耗時的過程，而且表Tree－Table存儲的不是一棵樹的記錄，而是所有權(quán)限樹森林的記錄，對森林排序代價更高。

一個可行的辦法是按先根順序建立一個該角色下的所有結(jié)點(diǎn)的臨時視圖V－t，當(dāng)完成第1步對V－t的訪問后，再刪去該臨時視圖，由此在不增加額外空間的條件下，完成了第1步實(shí)現(xiàn)。其實(shí)還存在可以優(yōu)化的余地，如果對SQL語言非常熟悉的話，就會發(fā)現(xiàn)某些數(shù)據(jù)庫可以支持按樹序訪問層次數(shù)據(jù)：

Select＊ FromTree－Table Where Role－ID＝0Connect By Prior Node－ID＝Parent－IDStart With Node－ID＝RootID，

其中，加黑的是SQL語言的關(guān)鍵字；RootID是根節(jié)點(diǎn)的序號，該查詢將按先根順序返回數(shù)據(jù)記錄，這條Select語句是符合SQL92標(biāo)準(zhǔn)的一條語句，可被Oracle支持。

圖4顯示了采用本文方法，生成n層n叉樹時（達(dá)到測試結(jié)點(diǎn)個數(shù)即停止生成）結(jié)點(diǎn)個數(shù)與所用時間的關(guān)系。

圖4 生成權(quán)限樹t與lg M的擬合曲線

從圖4中可以看出時間t與樹結(jié)點(diǎn)規(guī)模的對數(shù)lg M基本成一種曲線增長關(guān)系，是一種在一定范圍內(nèi)的緩慢增長曲線。

4 結(jié)束語

開發(fā)高效的系統(tǒng)經(jīng)常需要綜合優(yōu)化技術(shù)，本文利用JavaScript語言將樹形的生成和顯示交由客戶端瀏覽器完成，將按先根順序查詢的工作交給后臺數(shù)據(jù)庫系統(tǒng)完成，將數(shù)據(jù)記錄讀出并轉(zhuǎn)化為生成樹結(jié)構(gòu)的腳本交由Web服務(wù)器完成，合理劃分了三者之間的負(fù)載，將交互通信和互相等待的開銷減至最低；同時在每一個計算單元內(nèi)部，也努力改進(jìn)數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計，提高了系統(tǒng)運(yùn)行效率。本文提出的基于數(shù)據(jù)庫的動態(tài)Web權(quán)限樹生成方法是一種兼顧時間和空間效率的高效方法，在DAG的Web展現(xiàn)系統(tǒng)中取得了滿意的應(yīng)用效果，幾秒時間內(nèi)便可生成上千結(jié)點(diǎn)規(guī)模動態(tài)權(quán)限樹。

系統(tǒng)性能的綜合優(yōu)化，需要對系統(tǒng)進(jìn)行全面的把握，需要良好的數(shù)據(jù)結(jié)構(gòu)設(shè)計和充分挖掘后臺數(shù)據(jù)庫的查詢優(yōu)化潛力，更需要在Web服務(wù)層采用高效的算法，并為客戶端分配合理的負(fù)載，這些措施都體現(xiàn)了計算機(jī)科學(xué)中的權(quán)衡（trade－off）思想，因此系統(tǒng)研發(fā)既需要進(jìn)行理論研究，也需要積累工程經(jīng)驗(yàn)。

［1］韓 衛(wèi)，宋立明.快速構(gòu)建目錄樹的算法研究［J］.科學(xué)技術(shù)與工程，2009，9（20）：6208－6210.

［2］陳德軍，馬英哲，周祖德.一種動態(tài)目錄樹快速生成算法［J］.武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2008，32（1）：40－42.

［3］張玉芳，胡向前，熊忠陽.在JSP中使用遞歸算法生成目錄樹［J］.計算機(jī)工程與設(shè)計，2005，26（1）：44－46.

［4］周滇蘇，曹 維.動態(tài)目錄樹生成方法探討［J］.裝甲兵裝備技術(shù)研究，2004（3）：37－41.

［5］周炎濤，陳賢謀.ASP.NET中TreeView控件與數(shù)據(jù)庫結(jié)合創(chuàng)建動態(tài)目錄樹［J］.航空計算技術(shù)，2004，34（2）：25－27.

［6］胡學(xué)鋼，王東波，吳共慶.一種基于層次樹的高效密度聚類算法［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2008，31（2）：187－190，195.

［7］董立達(dá)，權(quán)重民，問鴻濱.Delphi7Web開發(fā)與應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，2003：1－50.

［8］阮文江.Java Script程序設(shè)計基礎(chǔ)教程［M］.北京：人民郵電出版社，2004：50－100.

［9］Cormen T H.算法導(dǎo)論［M］.潘金貴，譯.北京：機(jī)械工業(yè)出版社，2011：531.