DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> XML學習教程 >> XML詳解
XML 查詢技術為何成為研究焦點:從索引結構說起
編輯:XML詳解     

在 Web 世界裡,XML(可擴展標記語言)早已不是什麼新鮮事物。它語法自描述、跨平台、易於擴展,因此被大量採用於資料交換與系統整合的場合。伴隨網際網路的普及,以及電子商務、Web 服務等應用的成熟,越來越多的企業資料以 XML 的形式存在與流通。資料格式一旦佔據主流,隨之而來的問題就是「怎麼存、怎麼查」——XML 資料的管理技術,特別是查詢技術,於是被推到了研究的前台。

XML 的長處與它的痛處

和傳統的關聯式資料相比,XML 的優點不勝枚舉:結構清晰、可嵌套、允許半結構化的表達。但它也有一個相當致命的弱點——效率。

關聯式資料表裡,欄位名稱只出現一次,剩下的全是資料列;而 XML 檔案中,元素名稱會隨著每一份文件反覆出現,標籤本身佔去的空間往往比真正的內容還多。標籤重複不僅讓檔案膨脹,也直接拖累查詢:查詢引擎必須走過大量與資料無關的標記結構。要補回這段差距,最直接的手段就是為 XML 建立索引。

標準塵埃落定之後

2007 年 1 月 23 日,W3C 將 XPath 2.0 與 XQuery 1.0 正式定為推薦標準,結束了此前各家查詢語言各自為政的局面。有了共同的規格,實作就有了解是的比較基準。此後除了傳統資料庫廠商,學術界與研究機構也相繼提出各自的 XPath/XQuery 實作方案,文獻中可見者不下十餘種:有的採用不同的儲存模型,有的設計了不同的查詢演算法,優化思路也各有側重。

在這樣的背景下,達夢資料庫公司依自身產品路線,也提出了屬於自己的 XML 查詢引擎模型。引擎開發的過程中,一個反覆被驗證的結論是:索引結構的良窳,往往比查詢演算法本身更能決定最終效能。因此,在深入比較既有資料庫產品索引技術之後,為該引擎設計一套合理的索引結構,成為讓引擎發揮應有性能的關鍵一步。

索引為什麼不能省

XML 相關研究大致分為兩條路。一條是原生 XML 資料庫:資料與中介資料都以 XML 結構表示,不受底層採用物件模型或關聯模型的影響。另一條是 XML 與關聯資料庫之間的相互轉換,藉成熟關聯技術來處理 XML 資料。由於後者更貼近現實需求,長久以來一直是研究重心。

不論走哪條路,索引都是繞不開的一環。若完全不為 XML 文件建立索引結構,任何一次查詢都可能退化成對整棵文件樹的遍歷;當資料集規模上升,這種開銷很快就變得無法接受。索引的理論價值與實用價值,正體現在這裡。

傳統索引技術經過長期積累已相當成熟,但它們關心的核心問題是「依值定位記錄」,對記錄之間的邏輯關係並不特別在意。XML 查詢的長相卻完全不同:使用者給出的是一個以正則路徑表達式描述的結構模式,系統要找出所有符合該模式的資料。換句話說,XML 索引要解的題目是「模式匹配」,這與傳統 B 樹那類索引的設計出發點有本質差異。

路線一:基於路徑的索引

這類索引以樹結構中節點的路徑資訊為基礎,透過某種約簡策略,讓約簡後的結構只保留彼此不同的路徑,不再出現兩條完全相同的路徑。代表性方案包括 DataGuides、Index Fabric 與 APEX。

DataGuides

DataGuides 是一份從根節點出發的精簡路徑摘要,由邊標籤串接而成的字串路徑只被描述一次。它能有效減少路徑遍歷時需要訪問的節點數,對於「從根往下走」的查詢相當有效。但遇到含萬用字元(wildcard)的路徑,或是 XPath 標準中 descendant-or-self 軸的查詢,就得執行多次連接操作,效率明顯下滑,同時也存在資料冗餘。

Index Fabric

Index Fabric 由 Patricia Trie 演進而來。它為每一條通往元素節點的標記路徑產生一個字串編碼,再把這些編碼插入 Patricia Trie,於是「按路徑查詢 XML」被轉化為「查詢字串」:先將查詢路徑編碼成字串,再到索引樹中檢索。它的優點是完整保留了 XML 的層次結構資訊,能統一處理有模式與無模式兩種情況,且查詢與更新所需時間與層次深度相關,而不取決於索引鍵的長度。缺點則是元素節點之間的結構關係有所流失——它只保留了帶有文字值的元素節點,因此在處理 descendant-or-self 軸的部分匹配查詢時,表現與 DataGuides 同樣不理想。

APEX

APEX 換了個角度:它引入查詢分佈的統計資訊,把高頻出現的查詢所對應的標籤節點集合預先存進一個雜湊結構,作用近似於快取。新查詢進來時,先在雜湊表中查找是否已有現成的節點集合可回應。這套做法對常見查詢相當划算,但面對帶有元素值或屬性值條件的查詢表達式時,處理效率就偏低。

路線二:基於節點的索引

基於節點的索引,本質上是把 XML 資料拆解成一個個資料單元的記錄集合,並在每筆記錄中保存該單元在文件中的位置資訊。它打破了「必須沿著標籤路徑才能找到節點」的限制,把 XML 轉寫成規範形式的節點記錄。因為位置資訊被保留下來,這類索引很容易與成熟的關聯資料庫結合,也因此成為目前應用最廣的一種。依位置資訊的編碼方式不同,又可細分為兩大類。

前綴編碼

前綴編碼的做法很直觀:把父節點的編碼直接作為子節點編碼的前綴。Dewey 編碼是典型代表,文獻中的 ORDPATH 也採用類似思路,並進一步給出了 ORDPATH 的壓縮方法,該壓縮方案後來被 SQL Server 2005 用於索引組織。

有了前綴編碼,判斷節點 v 是否為節點 u 的後代,只需檢查 u 的編碼是否為 v 的編碼前綴即可。這類索引還有一個重要性質:字典有序。以某節點為根的子樹中,任一節點的前綴編碼必定大於(或小於)其左兄弟(右兄弟)子樹中所有節點的前綴編碼。正因具備這種有序性,前綴索引既能有效支援包含關係運算,也能順帶處理文件位置關係的計算。

區間編碼

區間編碼為樹中每個節點賦予一組 [start, end] 區間,並滿足「父節點的區間包含其後代節點的區間」這一約束。最早的代表是 Dietz 編碼,它給每個節點一組二元組:先序遍歷序號與後序遍歷序號。由於祖先節點在先序遍歷中必定早於其後代出現、在後序遍歷中必定晚於後代出現,因此兩組序號的大小關係即可判定祖先/後代關係。

另一個典型是 XISS 索引,它為每個節點賦予一組數字對:order 為擴展的前序編碼,size 表示子孫範圍。XISS 的查詢策略是把原始查詢拆成多個子表達式,分別求值,再把中間結果連接起來得到最終答案,因此對含萬用字元的查詢支援良好。但代價在於:所有中間結果都要做連接,而這種連接可能極其耗時,特別是當路徑很長、卻只是個簡單表達式的時候。

兩種機制如何取捨

基於路徑的索引依賴節點合併策略,透過節點等價、路徑等價等手段,得到遠小於原始文件的索引結構;但它整體仍是樹形,查詢時基本上還是要遍歷索引樹才能得到結果。它對簡單路徑表達式的支援相當好,一旦換成正則路徑表達式,效果就打折扣。

基於節點的索引則靠編碼技術為每個節點建立標識,節點間的結構關係可以透過編碼在常數時間內判定,因而能很好地支援正則路徑表達式。它的弱點出現在長路徑上:當查詢產生的中間結果數量龐大時,連接操作的代價會變得非常沉重。

兩者各有短板,卻恰好可以互補。從實際落地情況看,基於節點的索引應用更廣、研究也更成熟,因此達夢在 XML 索引結構上的取捨是:以基於節點的索引為主體,適度借鑑基於路徑的索引加以改良,力求在結構匹配能力與連接成本之間取得平衡。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved