樹狀結構是應用最廣的資料結構之一:族譜、企業組織、檔案系統、頁表、資料庫索引,背後都是樹。伴隨 Internet 的普及,樹也大量出現在瀏覽器/伺服器(B/S)架構的系統裡。
現行網路上的樹大致分兩類。靜態樹到處可見、實作簡單,卻無法反映節點變化;動態樹能增刪改節點,但多半不支援拖曳調整結構與排序,而且每次操作都要重刷整頁,維護起來相當痛苦。本文提出一套以 Ajax 為基礎、可動態載入節點的通用方案:採 J2EE 多層架構,節點資料存資料庫,以 XML 呈現交給 JavaScript 解析,支援無刷新增刪改與拖曳排序。
Ajax 這個名詞由 Jesse James Garrett 提出。它並不是新語言或新技術,而是既有技術的重新組合:以 XHTML 與 CSS 做標準化呈現;用 DOM 實現動態顯示與互動;用 XML 與 XSLT 交換及處理資料;用 XMLHttpRequest 進行異步資料讀取;最後以 JavaScript 把一切綁在一起。
它的工作原理等於在使用者與伺服器之間插入一層引擎,讓操作與回應變成非同步。並非所有請求都往伺服器跑——像資料驗證、資料處理這類工作交給 Ajax 引擎在客戶端完成,只有確實需要新資料時才代為送出請求。如此把伺服器的負擔分流到使用者端閒置的運算能力上,伺服器與頻寬壓力自然下降。
圖 1 未使用 Ajax(a)與使用 Ajax(b)的 Web 應用比較
傳統的 Model 1 開發模型把商業邏輯、伺服器處理與 HTML 混在同一頁,小案子開發很快,但流程一改就得動到多處,邏輯與呈現高度耦合,程式無法 reuse。Model 2 則是 MVC(Model-View-Controller)在 Web 上的落地:Model 負責商業邏輯,View 是呈現層頁面,Controller 掌控處理流程,三者各自獨立又能互動重用。
本方案採 J2EE 多層架構並結合 Struts,把表示層、商業邏輯層與資料層拆開:表示層只管樹的外觀,商業邏輯層負責樹的產生與變化並全模組化實作(不在頁面內嵌伺服器程式碼以降低耦合),模型層負責資料的儲存與表示。
視覺上模仿 Windows 檔案總管的資料夾樣式,每個節點的 DHTML 需要包含位置、前導圖示、樣式與針對該節點的操作,另外還要準備一些連接線用的前導圖。
表 1 樹節點的前導圖示樣式表
非葉節點用一個 DIV 容器包住圖示與文字。DIV 是 DHTML 的基礎,可以透過腳本操作它的屬性,例如改 style.display 來控制子節點的展開與隱藏:
<div id="mParentID">
<img align="center" border="0" onclick="nodeExpand('leafid')"
name="m1Tree" src="Tplus.gif" />
<img align="center" border="0" name="m1Folder" src="folderClosed.gif" />
計算機學院
</div>
葉節點沒有子節點,直接輸出即可。點擊節點前的「+/-」圖示時,靠 display 屬性切換(none 隱藏、block 顯示),同時替換加減號與資料夾圖:
if (expandChild.style.display == "none") {
this.Loading(parentObject); // 判斷該分支是否已載入
expandChild.style.display = "block";
parentObject.src = (para2 == "last") ? "Lminus.gif" : "Tminus.gif";
expandFolder.src = "folderOpen.gif";
} else {
expandChild.style.display = "none";
parentObject.src = (para2 == "last") ? "Lplus.gif" : "Tplus.gif";
expandFolder.src = "folderClosed.gif";
}
節點變化以資料庫為載體記錄。必要欄位包含節點編號(CLASSID)、節點描述(ClassName)與父節點編號(ParentId);再補上類別代碼(ClassCode)、節點層級(ClassLevel)、是否為葉節點(Terminated)等輔助欄位。
圖 3 樹形資料表結構示意圖
記憶體中走訪樹的時間複雜度是 O(n),但資料一旦進了資料庫,就只能靠 SQL 取用;一次抓太多資料不但耗資源,使用者等待也更久。因此最理想的做法是「讓資料庫直接吐出已排序的樹」。
關鍵在於字串排序走的是字典序。設計類別代碼為多層字串(例如 AAABBBCCC),從根往下每層增加一段,且子節點代碼以前綴方式繼承父節點代碼:AAA 的子節點是 AAAAAA、AAAAAB,AAAAAB 的子節點則是 AAAAABAAA、AAAAABAAB。同一層依建立順序編號,每段寬度依實際需求決定(AAA~ZZZ 即 26³ 個節點,不夠再追加一個字元)。只要下 select * from tree_class order by classcode,就能一次取得完整的先序樹。
節點量龐大時不該一次抓完,改採動態載入:每次點擊「+」先判斷子節點是否已載入,若否才透過 XMLHttpRequest 異步請求 select * from tree_class where parent = ? order by classcode。
dhtmlTree.prototype.Loading = function (pObject) {
if (((pObject.XMLload == 0) && (this.XMLsource)) && (!this.XMLloading)) {
pObject.XMLload = 1;
this.loadXML(this.XMLsource + getUrlSymbol(this.XMLsource)
+ "id=" + escape(pObject.id));
}
}
dhtmlXMLObject.prototype.loadXML = function (url) {
try {
this.xmlDoc = new XMLHttpRequest();
this.xmlDoc.open("GET", url, true); // true:異步
this.xmlDoc.send(null);
} catch (e) {
this.xmlDoc = new ActiveXObject("Microsoft.XMLHTTP"); // IE
this.xmlDoc.open("GET", url, true);
this.xmlDoc.send(null);
}
return this.xmlDoc.responseXML;
}
每次只取同一個 ParentId 下的子節點序列,封裝成 XML 的樹狀結構,例如:
<tree id="0">
<leaf child="1" name="國防科技大學" id="1"
im0="leaf.gif" im1="folderOpen.gif" im2="folderClosed.gif" />
</tree>
交給 JavaScript 的 insertItem() 解析並組出 HTML:child 為 1 表示有子節點;im0 是無子節點時的圖示,im1、im2 則是展開與收合狀態的圖示,因此圖示完全可以在產生 XML 時自訂。
資料庫回傳的是有序先序樹,XML 則是完整的樹狀文件,所以只要從根節點開始走訪一次,就能把整棵樹還原。
dhtmlXMLObject.prototype.constructTree = function () {
var node = this.XMLLoader.getXMLTopNode("tree");
var parentId = node.getAttribute("id");
for (var i = 0; i < node.childNodes.length; i++) {
if (node.childNodes[i].nodeType == 1 &&
node.childNodes[i].tagName == "leaf") {
var name = node.childNodes[i].getAttribute("text");
var temp = dhtmlObject.a0Find(parentId); // 取得父節點
temp.XMLload = 1; // 已載入
dhtmlObject.insertItem(parentId, cId, name, im0, im1, im2, chd);
dhtmlObject.addDragger = this; // 設定可拖曳
}
}
}
刪除最簡單,用 delete from tree_class where classcode like '前綴%' 就能連子節點一起清掉。新增分三種情況:前插與後插需要遞迴更新類別代碼,插入子節點則只要找出同層最大的類別代碼加一。拖曳改結構時,把被拖節點的 ParentId 改成目標節點的 CLASSID 即可:update tree_class set parentId = 目標 where classid = 來源。
樹的儲存有二元表與鏈表兩種,走訪有深度與廣度兩種,複雜度都是 O(n)。用二元表時,記憶體中可靠陣列索引直接定位父節點與兄弟節點;但從資料庫讀進記憶體後,若無法用索引定位,每找一個節點就得走訪一遍(O(n/2)),n 個節點排序整體就退化為 O(n²/2)——這正是一般 B/S 樹元件效能低落的主因。本方案以字典序編號讓資料庫直接吐出有序樹,客戶端只需線性走訪生成畫面,複雜度回到 O(n)。
本文討論了以 Ajax 實作動態樹的完整方案:支援無刷新維護節點、支援拖曳調整結構與排序;節點資訊落在資料庫,具备良好的通用性;以 XML 描述節點,任何符合預定 XML 格式的資料都能用這棵樹呈現。該方案已實際應用於數字迎新系統與老百姓大藥房資訊系統。