推薦：談XML卷之實(shí)戰(zhàn)錦囊(1)：動(dòng)態(tài)排序
動(dòng)機(jī)： 排序功能讓我們頁面上的數(shù)據(jù)顯的更人性化，是我們?cè)诰W(wǎng)站上見過的很普遍的一個(gè)功能效果了。以往的自動(dòng)排序都是用大量的腳本代碼來完成的，對(duì)一般的愛好者來說這是件困難的事情。然而用XML

XML(可擴(kuò)展標(biāo)記語言)已成為Web應(yīng)用中數(shù)據(jù)表示和數(shù)據(jù)交換的標(biāo)準(zhǔn),隨著Internet的快速發(fā)展,尤其是電子商務(wù)，Web服務(wù)等應(yīng)用的廣泛使用,XML類型的數(shù)據(jù)成為當(dāng)前主流的數(shù)據(jù)形式。因此XML數(shù)據(jù)的管理技術(shù)尤其是XML數(shù)據(jù)查詢技術(shù)成為當(dāng)前的研究熱點(diǎn)。

 

相比起關(guān)系型數(shù)據(jù)，XML有著各種各樣的優(yōu)點(diǎn)，但有個(gè)最大的缺陷就是它的效率。因?yàn)殛P(guān)系型數(shù)據(jù)文件中，數(shù)據(jù)的字段名只需出現(xiàn)一次即可，而XML數(shù)據(jù)文件中，元素名將反復(fù)出現(xiàn)，這必須會(huì)影響到查詢的效率。為了盡可能的提高XML的查詢效率，需要為XML類型提供了索引功能。

 

萬維網(wǎng)聯(lián)盟于2007年1月23日將XPath2.0和XQuery1.0確定為推薦標(biāo)準(zhǔn)，結(jié)束了此前各種查詢語言群雄逐鹿的局面。 基于此標(biāo)準(zhǔn)， 除傳統(tǒng)廠商外，各科研機(jī)構(gòu)紛紛提出了對(duì)XPath和XQuery的實(shí)現(xiàn)(文獻(xiàn)中提及的有十?dāng)?shù)種)，其存儲(chǔ)模型不同，查詢算法各異，優(yōu)化途徑也各有所長(zhǎng)，在這樣的背景下，達(dá)夢(mèng)數(shù)據(jù)庫公司根據(jù)自身發(fā)展戰(zhàn)略，也提出了自己的XML查詢引擎模型，目前，達(dá)夢(mèng)的XML查詢引擎正在緊張開發(fā)中，而對(duì)XML數(shù)據(jù)建立有效的索引是影響XML數(shù)據(jù)查詢性能的重要因素。在深入分析當(dāng)前已有的數(shù)據(jù)庫產(chǎn)品的索引技術(shù)基礎(chǔ)上為達(dá)夢(mèng)XML查詢引擎設(shè)計(jì)一種較為合理的索引結(jié)構(gòu)，以使該引擎能發(fā)揮較優(yōu)性能。

 

XML索引技術(shù)簡(jiǎn)介

 

目前，人們對(duì)XML的研究主要分為兩個(gè)方面。一個(gè)是對(duì)XML這種半結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)、查詢和管理的的原生數(shù)據(jù)庫，其中的數(shù)據(jù)和元數(shù)據(jù)完全采用XML結(jié)構(gòu)表示，與其底層的數(shù)據(jù)存儲(chǔ)格式(如對(duì)象模型、關(guān)系模型等)無關(guān)。另一個(gè)是它與關(guān)系數(shù)據(jù)庫之間的相互轉(zhuǎn)換，利用關(guān)系數(shù)據(jù)庫的成熟技術(shù)對(duì)XML數(shù)據(jù)進(jìn)行處理。由于后一個(gè)方向比較有現(xiàn)實(shí)意義，因此成了XML研究中的重點(diǎn)。

 

而除了存儲(chǔ)方案之外，索引技術(shù)也是決定一個(gè)數(shù)據(jù)庫系統(tǒng)最重要的因素之一。如果對(duì)XML文檔不構(gòu)建索引結(jié)構(gòu)，那么針對(duì)XML數(shù)據(jù)的任何查詢都很可能導(dǎo)致對(duì)整個(gè)文檔樹的遍歷，隨著XML數(shù)據(jù)集的增大，這種開銷是不可忍受的。故此，對(duì)XML索引技術(shù)的研究具有較高的理論和實(shí)用價(jià)值。

 

雖然傳統(tǒng)的索引技術(shù)經(jīng)過長(zhǎng)期的積累已經(jīng)相對(duì)成熟，但是，這類索引技術(shù)針對(duì)的主要是根據(jù)值(而不是具有某種關(guān)系的模式)定位數(shù)據(jù)記錄的功能，不太關(guān)注數(shù)據(jù)記錄間的邏輯關(guān)系;而 XML 數(shù)據(jù)查詢的基本特征就是根據(jù)模式特征(正則路徑表達(dá)式形式描述的結(jié)構(gòu)關(guān)系)的輸入提取符合該模式的數(shù)據(jù)，所以，XML 索引的主要內(nèi)容就是設(shè)計(jì)適用于模式匹配的技術(shù)。

 

XML索引分類

 

基于路徑的XML索引

 

基于路徑的索引是以XML樹結(jié)構(gòu)中節(jié)點(diǎn)的路徑信息為基礎(chǔ)，采取某種約簡(jiǎn)方式，使得約簡(jiǎn)后的樹結(jié)構(gòu)只維護(hù)不同的路徑信息，而不會(huì)存在具有相同路徑的兩個(gè)節(jié)點(diǎn)。 已經(jīng)提出的這類索引有：DataGuides索引、Index Fabric索引、XML數(shù)據(jù)的自適應(yīng)路徑索引(Adaptive Path Index for XML Data， APEX )

 

Dataguides 索引是從根結(jié)點(diǎn)為起始的精練路徑的一種結(jié)構(gòu)摘要。邊標(biāo)簽串聯(lián)在一起形成的字符串路徑在 Dataguides 中只描述一次。Dataguides 減少了遍歷路徑查詢時(shí)所需的部分結(jié)點(diǎn)，它對(duì)從根部遍歷 XML文檔是有效的。但對(duì)于含有通配符的路徑查詢或?qū)�帶有XPath標(biāo)準(zhǔn)中定義的descendant-or-self軸的路徑查詢要進(jìn)行多次的連接操作，查詢效率較低，并且存在數(shù)據(jù)冗余。

 

然后編寫關(guān)于這2個(gè)大字段的Java對(duì)象文件TestLob.java，分別定義類型為CLOB和BLOB屬性字段為String和byte[]類型，其中由于CLOB是處理大文本類型所以它對(duì)應(yīng)了Java中的String類型，BLOB是處理一些以二進(jìn)制流形勢(shì)存儲(chǔ)的沒有嚴(yán)格定義的大文件所以讓它使用byte[]類型，然后分別定義這2個(gè)屬性的Getter和Setter方法，相關(guān)代碼如下:

 

Dataguides 索引是從根結(jié)點(diǎn)為起始的精練路徑的一種結(jié)構(gòu)摘要。邊標(biāo)簽串聯(lián)在一起形成的字符串路徑在 Dataguides 中只描述一次。Dataguides 減少了遍歷路徑查詢時(shí)所需的部分結(jié)點(diǎn)，它對(duì)從根部遍歷 XML文檔是有效的。但對(duì)于含有通配符的路徑查詢或?qū)�帶有XPath標(biāo)準(zhǔn)中定義的descendant-or-self軸的路徑查詢要進(jìn)行多次的連接操作，查詢效率較低，并且存在數(shù)據(jù)冗余。

 

Index Fabric是在Patricia Trie樹上發(fā)展而來的一種索引結(jié)構(gòu)，它把到每個(gè)元素節(jié)點(diǎn)的每條標(biāo)記路徑都用一個(gè)字符串編碼，再將這些編碼值插入到Patricia Trie樹中去，從而將按照路徑方式對(duì)XML數(shù)據(jù)的查詢轉(zhuǎn)化為對(duì)字符串的查詢。在查詢時(shí)先將查詢路徑編碼成字符串的形式，再在索引樹中進(jìn)行查找。Index Fabric索引優(yōu)點(diǎn)是存儲(chǔ)了XML數(shù)據(jù)的層次結(jié)構(gòu)信息，統(tǒng)一處理了有模式和無模式信息情況下的XML數(shù)據(jù)的檢索，并且使對(duì)XML數(shù)據(jù)的查詢和更新所需要的時(shí)間與層次相關(guān)而不是與索引關(guān)鍵字的長(zhǎng)度相關(guān)。Index Fabric索引的缺點(diǎn)在于丟失了元素節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系，因?yàn)樗�只保留了有文本值的元素�?jié)點(diǎn)的信息。因此，與DataGuides索引類似，Index Fabric索引處理帶有XPath標(biāo)準(zhǔn)中定義的descendant-or-self軸的部分匹配查詢表達(dá)式效率不高

 

為此，APEX[14]引入了依賴于XML數(shù)據(jù)查詢分布的信息:將經(jīng)常出現(xiàn)的XML查詢語句對(duì)應(yīng)的標(biāo)簽節(jié)點(diǎn)預(yù)先保存在一個(gè)哈希結(jié)構(gòu)中。它的作用類似于Cache的功能:當(dāng)有新的查詢要求處理時(shí)，首先在哈希表中搜索是否有滿足的節(jié)點(diǎn)集合。但它對(duì)于帶有元素值或?qū)傩灾档牟樵儽磉_(dá)式的處理效率較低。

 

基于節(jié)點(diǎn)的索引

 

基于節(jié)點(diǎn)的索引本質(zhì)上即是將XML數(shù)據(jù)分解為數(shù)據(jù)單元的記錄集合，同時(shí)在記錄中保存該單元在XML數(shù)據(jù)中的位置信息。與基于路徑的索引不同，基于節(jié)點(diǎn)的索引打破了必須通過標(biāo)簽路徑查找節(jié)點(diǎn)這一限制，將XML數(shù)據(jù)分解成規(guī)范形式的節(jié)點(diǎn)記錄。由于保存了節(jié)點(diǎn)的位置信息，而且能夠很好地結(jié)合到成熟的關(guān)系數(shù)據(jù)庫管理系統(tǒng)中，因此它是目前應(yīng)用最廣泛的一種索引。

 

根據(jù)對(duì)位置信息的編碼方式不同，基于節(jié)點(diǎn)的索引一般可以分為一下幾類：

 

1. 基于前綴的索引

 

基于前綴的索引主要是根據(jù)Dewey[12]編碼生成的索引，文獻(xiàn)[13]的 ORDPATH 編碼采用的也是類似的方法,并給出了壓縮 ORDPATH的方法，該方法已應(yīng)用于SQL Server 2005的索引組織中。

 

 

前綴編碼的基本思想是直接將一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)的編碼作為該節(jié)點(diǎn)編碼的前綴，對(duì)于前綴編碼，要判斷一個(gè)節(jié)點(diǎn)v是否另一個(gè)節(jié)點(diǎn)u的后裔，只要判斷u的編碼是否v的編碼的前綴。前綴編碼索引的一個(gè)重要性質(zhì)是它們的字典有序：以節(jié)點(diǎn)r為根的子樹中的任意一個(gè)節(jié)點(diǎn)u，它的前綴編碼c(u)大于（小于）它的左兄弟子樹（右兄弟子樹）中所有節(jié)點(diǎn)的前綴編碼。因此，基于前綴的索引不僅能夠有效地支持包含關(guān)系的運(yùn)算，而且能夠有效地支持文檔位置關(guān)系的計(jì)算。

 

2. 基于區(qū)間編碼的索引

 

對(duì)于區(qū)間編碼索引,樹T中的每一個(gè)結(jié)點(diǎn)被賦予一個(gè)區(qū)間編碼[begin,end],滿足:一個(gè)結(jié)點(diǎn)的區(qū)間編碼包含它的后裔結(jié)點(diǎn)的區(qū)間編碼.也就是說，樹T中 的節(jié)點(diǎn)u是節(jié)點(diǎn)v的祖先，當(dāng)且僅當(dāng)start(u)

 

第一個(gè)區(qū)間編碼方案是Dietz編碼,樹T中的每一個(gè)結(jié)點(diǎn)被賦予一個(gè)具有先序遍歷序號(hào)和后序遍歷序號(hào)的二元組.由于樹T中的一個(gè)祖先結(jié)點(diǎn)u在先序遍歷(后序遍歷)中必然出現(xiàn)在它的后裔結(jié)點(diǎn)v之前(之后),因此, 節(jié)點(diǎn)u和v是祖先/后裔關(guān)系,當(dāng)且僅當(dāng)pre(u)

 

另一個(gè)區(qū)間編碼索引的典型例子是XISS索引，它為每個(gè)節(jié)點(diǎn)賦予一個(gè)數(shù)字對(duì)，其中order為擴(kuò)展的前序編碼，size為節(jié)點(diǎn)的子孫的范圍。對(duì)一棵文檔樹中的任意節(jié)點(diǎn)X和Y，當(dāng)且僅當(dāng)order(x)

 

XISS索引通過將原始查詢語句分解為子表達(dá)式。然后分別針對(duì)這些子表達(dá)式實(shí)現(xiàn)查詢，最后對(duì)這些中間結(jié)果進(jìn)行聯(lián)結(jié)獲得查詢結(jié)果集。從而能較好地支持含通配符的查詢語句。不過，它是對(duì)每一個(gè)中間結(jié)果進(jìn)行聯(lián)結(jié)后得到最終查詢結(jié)果。雖然這樣一種方法的確能夠解決所有的通配符問題，可是，這種中間結(jié)果的聯(lián)結(jié)很有可能是非常耗時(shí)的，特別是對(duì)于長(zhǎng)路徑的簡(jiǎn)單表達(dá)式。

 

兩種索引機(jī)制的比較

 

基于路徑的索引主要基于節(jié)點(diǎn)合并的策略，通過節(jié)點(diǎn)等價(jià)、路徑等價(jià)等技術(shù)，得到比原始文檔小得多的索引結(jié)構(gòu)，它的結(jié)構(gòu)仍然是樹型的，所以在處理查詢時(shí)，基本上仍須遍歷整個(gè)索引樹才能得到結(jié)果。基于路徑的索引可以很好地支持簡(jiǎn)單路徑表達(dá)式的查詢，但是對(duì)于正則路徑表達(dá)式，它效果不是很理想。

 

基于節(jié)點(diǎn)的索引通過編碼技術(shù)索引每一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系通過編碼可以在常數(shù)時(shí)間內(nèi)確定它可以很好地支持正則路徑表達(dá)式，但是對(duì)于長(zhǎng)的路徑表達(dá)式，尤其是在查詢產(chǎn)生的中間結(jié)果很多的時(shí)候，節(jié)點(diǎn)索引的連接操作代價(jià)高昂。

 

基于路徑的索引和基于節(jié)點(diǎn)的索引各有優(yōu)缺點(diǎn)，但可以優(yōu)勢(shì)互補(bǔ)。目前在實(shí)際應(yīng)用中，基于節(jié)點(diǎn)的索引應(yīng)用更為廣泛，研究得也比較成熟，因此，達(dá)夢(mèng)公司有關(guān)XML索引結(jié)構(gòu)研究主要以基于節(jié)點(diǎn)的索引為主，并適當(dāng)參考基于路徑的索引加以改進(jìn)。

分享：解讀XML 增、刪、改和查示例
1.已知有一個(gè)XML文件（bookstore.xml）如下：