摘 要：介紹Native XML數(shù)據(jù)庫(kù)的概念和XML文檔在Native XML數(shù)據(jù)庫(kù)中3種不同的存儲(chǔ)策略，然后以一個(gè)開(kāi)放源代碼的Native XML數(shù)據(jù)庫(kù)產(chǎn)品[CD2]dbXML為對(duì)象，研究它的頁(yè)面存儲(chǔ)策略。針對(duì)其頁(yè)面存儲(chǔ)策略在“空閑”頁(yè)面管理上存在的問(wèn)題，提出尾部頁(yè)面截取策略，有效地釋放“空閑”頁(yè)面占用的磁盤空間。

關(guān)鍵詞：XML；Native XML數(shù)據(jù)庫(kù)；dbXML；存儲(chǔ)策略；尾部頁(yè)面截取策略

Study and Improvement on the Storage ofNative XML Database

HE Yuzhen1，XU Xuezhou2

(1.Yuncheng University，Yuncheng，044000，China;2.Software Engineering Institute，Xidian University，Xi′an，710071，China

Abstract：(The concept of native XML database and three deferent storage ways in whichXML document is stored in the native XML database is introduced.And then，the paper studies dbXML which is a kind of open source native XML database and researches into its page storage strategy.On the basis of the above，to resolve the question which exists in the managing of the free page the paper brings forward tail page truncating strategy，which helps dbXML release the disk space hold by the free page.

eywords：XML；Native XML database；dbXML;storage strategy；tail page truncating strategy

伴隨著XML應(yīng)用的飛速發(fā)展，XML有關(guān)數(shù)據(jù)和文檔大量出現(xiàn)，以數(shù)據(jù)庫(kù)方式實(shí)現(xiàn)XML數(shù)據(jù)的有效管理和快速精確的查詢已經(jīng)成為趨勢(shì)。在傳統(tǒng)數(shù)據(jù)庫(kù)廠商紛紛支持XML的同時(shí)，一種專門用于處理XML的數(shù)據(jù)庫(kù)[CD2]Native XML數(shù)據(jù)庫(kù)正在快速發(fā)展，并成為一個(gè)新的研究熱點(diǎn)。Native XML數(shù)據(jù)庫(kù)的含義是：以XML格式存儲(chǔ)信息的數(shù)據(jù)庫(kù)，這種數(shù)據(jù)庫(kù)通過(guò)創(chuàng)建一些索引，與XML文檔一起存儲(chǔ)到資源庫(kù)中，以支持快速搜索資源庫(kù)來(lái)查找包含特定信息的文檔。NXD的邏輯模型建立在XML文檔之上，而非文檔中的數(shù)據(jù)之上，并根據(jù)它來(lái)存取數(shù)據(jù)。該模型至少包括元素、屬性和PCDATA和文檔順序。NXD最小存儲(chǔ)單位是XML文檔。目前已經(jīng)有一些Native XML數(shù)據(jù)庫(kù)的原型系統(tǒng)，如Ipedo，Tamino，Natix，Xyleme，Berkeley DB XML，dbXML，XDB和Xindice。 

1 Native XML數(shù)據(jù)庫(kù)存儲(chǔ)策略

底層存儲(chǔ)和索引策略是Native XML數(shù)據(jù)庫(kù)的核心技術(shù)之一。一個(gè)良好的底層存儲(chǔ)和索引策略，是Native XML數(shù)據(jù)庫(kù)進(jìn)行高效的查詢和讀寫的關(guān)鍵。Native XML數(shù)據(jù)庫(kù)中存儲(chǔ)XML文檔的方式大致分為3種： 

(1字節(jié)流方式存儲(chǔ):在此方式下，XML文檔特有的圖/樹(shù)結(jié)構(gòu)被線性化為字節(jié)流。當(dāng)存儲(chǔ)和檢索整個(gè)文檔時(shí)，這種方式效率較高。但是，任何一次查詢文檔時(shí)都必須通過(guò)分析器處理后才能獲得結(jié)構(gòu)信息，對(duì)于本文的模式匹配方式的查詢顯然是一個(gè)不小的缺點(diǎn)。并且，對(duì)于XML文檔的一部分內(nèi)容的更新，可能要涉及整個(gè)文檔的更新，效率比較低。

(2元模型方式存儲(chǔ):它直接保存文檔的結(jié)構(gòu)信息，并利用傳統(tǒng)DBMS 及其數(shù)據(jù)模型存儲(chǔ)XML文檔。根據(jù)底層采用數(shù)據(jù)庫(kù)的不同，又分為基于關(guān)系數(shù)據(jù)庫(kù)的（RDB方式）和基于面向?qū)ο髷?shù)據(jù)庫(kù)的（OODB方式）2種方法。

RDB方式是將結(jié)點(diǎn)轉(zhuǎn)換成關(guān)系數(shù)據(jù)庫(kù)中的屬性，將XML文檔存儲(chǔ)于二維表中。優(yōu)點(diǎn)是可以使用關(guān)系數(shù)據(jù)庫(kù)實(shí)現(xiàn)存儲(chǔ)方法，缺點(diǎn)是效率低。另外關(guān)系表語(yǔ)義表達(dá)能力差，無(wú)法表達(dá)非結(jié)構(gòu)化的XML 文檔中復(fù)雜的引用關(guān)系。因此關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的一些優(yōu)化存儲(chǔ)策略（如聚類存儲(chǔ)）很難應(yīng)用于XML數(shù)據(jù)。

OODB的存儲(chǔ)方法是使用XML DTD或XML Schema所給出的信息導(dǎo)出存儲(chǔ)模式，可以使用一種規(guī)范的方法從DTD或Schema導(dǎo)出類型的存儲(chǔ)結(jié)構(gòu)。使用該存儲(chǔ)方法，系統(tǒng)既可對(duì)存儲(chǔ)，也可對(duì)查詢處理進(jìn)行優(yōu)化。通常在類型事先知道且類型變化相對(duì)較少的“穩(wěn)定”環(huán)境中，使用這種結(jié)構(gòu)方法是較為合適的。

(3混合式存儲(chǔ)：在這種方式下， 某種程度的數(shù)據(jù)細(xì)節(jié)被設(shè)置為“閾”，比“閾”的粒度粗的結(jié)構(gòu)被存儲(chǔ)在數(shù)據(jù)庫(kù)中已結(jié)構(gòu)化的部分，而更精細(xì)的部分被存儲(chǔ)在數(shù)據(jù)庫(kù)中字節(jié)化了的部分。這種方式的特點(diǎn)是：數(shù)據(jù)查詢較快而數(shù)據(jù)更新較慢。

dbXML 是一個(gè)開(kāi)放源代碼的Native XML數(shù)據(jù)庫(kù)產(chǎn)品，它的存儲(chǔ)策略是以集合方式存貯XML文檔，預(yù)解析的壓縮文檔存貯。下面以dbXML為對(duì)象，針對(duì)其頁(yè)面管理策略及存在的問(wèn)題，提出新的改進(jìn)方法。

2 dbXML的頁(yè)面存儲(chǔ)策略

dbXML實(shí)現(xiàn)頁(yè)面存儲(chǔ)策略，它允許文件的某一片斷映射到內(nèi)存中，從而向上層提供高效地訪問(wèn)文件的方式。每個(gè)頁(yè)面有固定的長(zhǎng)度，如果將要存儲(chǔ)的XML文檔大于頁(yè)面的固定長(zhǎng)度，則會(huì)創(chuàng)建新的頁(yè)面來(lái)存儲(chǔ)剩余的內(nèi)容，并鏈接到前一個(gè)頁(yè)面。頁(yè)面文件的結(jié)構(gòu)如圖1所示：

如圖1所示，一個(gè)頁(yè)面文件包含一個(gè)頁(yè)面文件頭部，及一系列固定長(zhǎng)度的頁(yè)面。頁(yè)面文件頭部長(zhǎng)度為4 kB。頁(yè)面的缺省長(zhǎng)度也為4 kB，它也包含1個(gè)64 B的頁(yè)面頭，剩余空間用于存儲(chǔ)實(shí)際的數(shù)據(jù)。每個(gè)頁(yè)面都有1個(gè)頁(yè)號(hào)，當(dāng)系統(tǒng)需要讀寫頁(yè)號(hào)為n的頁(yè)面，而它不在內(nèi)存中時(shí)，系統(tǒng)計(jì)算該頁(yè)面的起始偏移地址offset，并將該頁(yè)面讀入內(nèi)存。計(jì)算的公式如下：

3 頁(yè)面存儲(chǔ)策略存在的問(wèn)題

dbXML將所有的XML數(shù)據(jù)以分頁(yè)的形式存儲(chǔ)在文件中，每一個(gè)集合維護(hù)一個(gè)頁(yè)面文件，它被分成多個(gè)頁(yè)面，每個(gè)頁(yè)面都有頁(yè)面號(hào)標(biāo)識(shí)，頁(yè)面可以通過(guò)其nextPage字段相互連接，從而可以存儲(chǔ)超過(guò)頁(yè)面長(zhǎng)度的數(shù)據(jù)。dbXML通過(guò)B+樹(shù)來(lái)訪問(wèn)一個(gè)XML文檔的各個(gè)頁(yè)面，樹(shù)節(jié)點(diǎn)也存儲(chǔ)在了頁(yè)面中。

比如在集合mycol在初始創(chuàng)建時(shí)，頁(yè)面文件mycol.tbl中僅有一個(gè)頁(yè)面文件頭部和一個(gè)頁(yè)面，頁(yè)面文件頭部占用4 kB，存儲(chǔ)了當(dāng)前頁(yè)面數(shù)量、根節(jié)點(diǎn)頁(yè)面號(hào)等信息；頁(yè)面則用于存儲(chǔ)B+樹(shù)根節(jié)點(diǎn)包含的索引信息，也占用4 kB。它們共占用8 kB。假設(shè)在該集合中插入2個(gè)XML文檔：a.xml和b.xml，a.xml長(zhǎng)度為3 kB，b.xml長(zhǎng)度為5 kB，每個(gè)頁(yè)面的固定長(zhǎng)度為4 kB。則a.xml占用的頁(yè)面數(shù)目為1個(gè)頁(yè)面，b.xml占用的頁(yè)面數(shù)目為2個(gè)頁(yè)面，插入后該集合的頁(yè)面文件內(nèi)容如圖2所示：

頁(yè)面文件頭部的first_free_page和last_free_page的值為-1，表明當(dāng)前沒(méi)有任何空閑的頁(yè)面。頁(yè)號(hào)為0的頁(yè)面的狀態(tài)位為0x02，表明當(dāng)前頁(yè)面存儲(chǔ)的是B+樹(shù)節(jié)點(diǎn)，由頁(yè)面文件頭部的root_page字段的值可以看出，該節(jié)點(diǎn)為樹(shù)的根節(jié)點(diǎn)；頁(yè)號(hào)為1的頁(yè)面存儲(chǔ)了a.xml，狀態(tài)位0x14表明當(dāng)前頁(yè)面存儲(chǔ)的是文檔的數(shù)據(jù)，并且是第一個(gè)頁(yè)面；頁(yè)號(hào)為2和3的頁(yè)面存儲(chǔ)了b.xml，3號(hào)頁(yè)面的狀態(tài)位為0x7E，表明它不是文檔的第一個(gè)頁(yè)面。這時(shí)刪除b.xml，那么， mycol.tbl文件的內(nèi)容將變化如圖3所示：

由于b.xml的刪除，原先占用的2個(gè)頁(yè)面2和3將變?yōu)榭臻e狀態(tài)，狀態(tài)位變?yōu)?x00，同時(shí)，頁(yè)面文件的頭部字段first_free_page將指向第一個(gè)空閑頁(yè)面，last_free_page將指向最后一個(gè)空閑頁(yè)面，空閑頁(yè)面間也使用next_page字段相互連接。

從上述過(guò)程可以看出，dbXML的新頁(yè)面是在插入新的文檔是產(chǎn)生的，如果當(dāng)前頁(yè)面文件中存在空閑頁(yè)面，則新文檔首先會(huì)使用它們，只有當(dāng)沒(méi)有空閑頁(yè)面或空閑頁(yè)面數(shù)量不夠，才會(huì)將分配新的頁(yè)面。但是，dbXML自始自終都并沒(méi)有釋放空閑頁(yè)面，mycol.tbl文件的大小不斷的增大，即使該集合僅存儲(chǔ)了一個(gè)1 kB大小的文檔，空閑頁(yè)面仍然會(huì)占用該頁(yè)面文件的剩余空間而不被釋放；只有當(dāng)該集合被刪除時(shí)，頁(yè)面文件才會(huì)被刪除，不再占用磁盤空間。dbXML的這種存儲(chǔ)方式，盡管在一定程度上提高了存取的效率，但十分浪費(fèi)磁盤空間，尤其在多次存儲(chǔ)和刪除較大的XML文檔時(shí)表現(xiàn)明顯。針對(duì)dbXML的頁(yè)面存儲(chǔ)策略的不足，本文提出一種改進(jìn)方法。

4 頁(yè)面存儲(chǔ)策略的改進(jìn)

由上面分析得知，頁(yè)面文件的長(zhǎng)度不斷增加，就是由于尾部的空閑文件沒(méi)有及時(shí)釋放造成的。如果能夠釋放掉這些空閑頁(yè)面，便可以在一定程度上緩解頁(yè)面文件增加的速度。頁(yè)面文件頭部記錄了當(dāng)前頁(yè)面的數(shù)量pageCount，那么，文件尾部的頁(yè)號(hào)一定為：

[J]pNum＝pageCount -1 

從頁(yè)面文件的尾部進(jìn)行檢索，如果當(dāng)前頁(yè)面的狀態(tài)為空閑，就將該頁(yè)面從空閑頁(yè)面鏈表中刪除，直到尾部頁(yè)面為非空閑頁(yè)面為止。采用的算法流程如圖4所示：

空閑頁(yè)面截取策略在一定程度上可以緩解文件增加的速度，但由于順序存儲(chǔ)的特性，頁(yè)面文件尾部的頁(yè)面號(hào)都是較大的值。如果在申請(qǐng)頁(yè)面時(shí)，優(yōu)先使用頁(yè)面號(hào)小的空閑頁(yè)面，XML文檔的數(shù)據(jù)能夠盡可能的集中在頁(yè)面文件的前面部分，在文件尾部申請(qǐng)新頁(yè)面的可能性將降低。為此，必須對(duì)空閑頁(yè)面進(jìn)行排序，保證該鏈表以頁(yè)號(hào)的升序排列。由于空閑頁(yè)面鏈表為單鏈表結(jié)構(gòu)，采用插入排序的算法，每當(dāng)文檔刪除時(shí)，將產(chǎn)生的空閑頁(yè)面插入到有序鏈表的合適位置。

void truncateFiles(

{long pageFirst=fileHeader.getPageCount(-1;

while ( true

{Page p= (Pagepages.get(pageFirst;[JY]//pages為已經(jīng)加載頁(yè)面的緩存

If(p= =1

p = new Page(pageFirst.longValue(;

PageHeader ph=p.getPageHeader(;

If(ph.getStatus= =0x00

{ pages.remove(pageFirst;[LL]

pageFirst = pageFirst -1;

}else

break;}

deleteFreePages(pageFirst;

[JY]//從頁(yè)面空閑鏈表中刪除當(dāng)前的尾部空閑頁(yè)面

}

在空閑頁(yè)面成為有序鏈表之后，文件尾部的空閑頁(yè)面連續(xù)，并且頁(yè)面號(hào)最大，那么，只要找到尾部連續(xù)的空閑頁(yè)面最小的頁(yè)面號(hào)，即可將其后面的所有頁(yè)面刪除。delTailFreePages函數(shù)完成了將尾部空閑頁(yè)面刪除的功能，參數(shù)pageFirst記錄尾部連續(xù)的空閑頁(yè)面最小的頁(yè)面號(hào)，該函數(shù)的算法描述如下：

void delTailFreePages(long pageFirst

{long pageNum= fileHeader.getFirstFreePage(;

if (pageNum = =pageFirst

{fileHeader.setFirstFreePage(-1;

fileHeader.setFirstFreePage(-1;}

else

{ while ( true

{ Page p = new Page(pageNum.longValue(;

If(p.getNextPage( ! =pageFirst 

pageNum=p.getNextPage(;

else

{

fileHeader.setLastFreePage(pageNum;

p.setNextPage(-1;

p.write(;

break;

} } }

long offset = fileHeader.getHeaderSize ( + pageFirst* fileHeader.getPageSize (;

file.Truncate(offset;[JY]//截取指定位置的文件尾部

}

5 結(jié) 語(yǔ)

尾部頁(yè)面截取策略的主要目的在于截取頁(yè)面文件中位于尾部位置的那些空閑頁(yè)面，釋放相應(yīng)的磁盤空間。同時(shí)，該策略始終維護(hù)空閑頁(yè)面鏈表的有序排列，與原先的空閑頁(yè)面管理機(jī)制相比，它保證在空閑頁(yè)面分配時(shí)，總是優(yōu)先分配最小的頁(yè)面號(hào)，使更多的數(shù)據(jù)盡可能的集中在頁(yè)面文件的首部，減少尾部頁(yè)面截取的次數(shù)。

參 考 文 獻(xiàn)

［1］dbXML-group.dbXML下載[EB/OL].http://www.dbxml.com/.

［2］馮建華，錢乾.純XML數(shù)據(jù)庫(kù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2006(6:1-4.

［3］陳海建，茅忠明.XML本源數(shù)據(jù)庫(kù)開(kāi)放模型的設(shè)計(jì)與實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2006(22:238-240.

［4］李驥，陳福生.Native-XML數(shù)據(jù)庫(kù)綜述[J].計(jì)算機(jī)工程與設(shè)計(jì)，2004，25(6:932-935.