Ｎａｔｉｖｅ ＸＭＬ數據庫存儲研究與改進

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

關鍵詞：XML；Native XML數據庫；dbXML；存儲策略；尾部頁面截取策略

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應用的飛速發展，XML有關數據和文檔大量出現，以數據庫方式實現XML數據的有效管理和快速精確的查詢已經成為趨勢。在傳統數據庫廠商紛紛支持XML的同時，一種專門用于處理XML的數據庫[CD2]Native XML數據庫正在快速發展，并成為一個新的研究熱點。Native XML數據庫的含義是：以XML格式存儲信息的數據庫，這種數據庫通過創建一些索引，與XML文檔一起存儲到資源庫中，以支持快速搜索資源庫來查找包含特定信息的文檔。NXD的邏輯模型建立在XML文檔之上，而非文檔中的數據之上，并根據它來存取數據。該模型至少包括元素、屬性和PCDATA和文檔順序。NXD最小存儲單位是XML文檔。目前已經有一些Native XML數據庫的原型系統，如Ipedo，Tamino，Natix，Xyleme，Berkeley DB XML，dbXML，XDB和Xindice。 

1 Native XML數據庫存儲策略

底層存儲和索引策略是Native XML數據庫的核心技術之一。一個良好的底層存儲和索引策略，是Native XML數據庫進行高效的查詢和讀寫的關鍵。Native XML數據庫中存儲XML文檔的方式大致分為3種： 

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

(2元模型方式存儲:它直接保存文檔的結構信息，并利用傳統DBMS 及其數據模型存儲XML文檔。根據底層采用數據庫的不同，又分為基于關系數據庫的（RDB方式）和基于面向對象數據庫的（OODB方式）2種方法。

RDB方式是將結點轉換成關系數據庫中的屬性，將XML文檔存儲于二維表中。優點是可以使用關系數據庫實現存儲方法，缺點是效率低。另外關系表語義表達能力差，無法表達非結構化的XML 文檔中復雜的引用關系。因此關系數據庫系統的一些優化存儲策略（如聚類存儲）很難應用于XML數據。

OODB的存儲方法是使用XML DTD或XML Schema所給出的信息導出存儲模式，可以使用一種規范的方法從DTD或Schema導出類型的存儲結構。使用該存儲方法，系統既可對存儲，也可對查詢處理進行優化。通常在類型事先知道且類型變化相對較少的“穩定”環境中，使用這種結構方法是較為合適的。

(3混合式存儲：在這種方式下， 某種程度的數據細節被設置為“閾”，比“閾”的粒度粗的結構被存儲在數據庫中已結構化的部分，而更精細的部分被存儲在數據庫中字節化了的部分。這種方式的特點是：數據查詢較快而數據更新較慢。

dbXML 是一個開放源代碼的Native XML數據庫產品，它的存儲策略是以集合方式存貯XML文檔，預解析的壓縮文檔存貯。下面以dbXML為對象，針對其頁面管理策略及存在的問題，提出新的改進方法。

2 dbXML的頁面存儲策略

dbXML實現頁面存儲策略，它允許文件的某一片斷映射到內存中，從而向上層提供高效地訪問文件的方式。每個頁面有固定的長度，如果將要存儲的XML文檔大于頁面的固定長度，則會創建新的頁面來存儲剩余的內容，并鏈接到前一個頁面。頁面文件的結構如圖1所示：

如圖1所示，一個頁面文件包含一個頁面文件頭部，及一系列固定長度的頁面。頁面文件頭部長度為4 kB。頁面的缺省長度也為4 kB，它也包含1個64 B的頁面頭，剩余空間用于存儲實際的數據。每個頁面都有1個頁號，當系統需要讀寫頁號為n的頁面，而它不在內存中時，系統計算該頁面的起始偏移地址offset，并將該頁面讀入內存。計算的公式如下：

3 頁面存儲策略存在的問題

dbXML將所有的XML數據以分頁的形式存儲在文件中，每一個集合維護一個頁面文件，它被分成多個頁面，每個頁面都有頁面號標識，頁面可以通過其nextPage字段相互連接，從而可以存儲超過頁面長度的數據。dbXML通過B+樹來訪問一個XML文檔的各個頁面，樹節點也存儲在了頁面中。

比如在集合mycol在初始創建時，頁面文件mycol.tbl中僅有一個頁面文件頭部和一個頁面，頁面文件頭部占用4 kB，存儲了當前頁面數量、根節點頁面號等信息；頁面則用于存儲B+樹根節點包含的索引信息，也占用4 kB。它們共占用8 kB。假設在該集合中插入2個XML文檔：a.xml和b.xml，a.xml長度為3 kB，b.xml長度為5 kB，每個頁面的固定長度為4 kB。則a.xml占用的頁面數目為1個頁面，b.xml占用的頁面數目為2個頁面，插入后該集合的頁面文件內容如圖2所示：

頁面文件頭部的first_free_page和last_free_page的值為-1，表明當前沒有任何空閑的頁面。頁號為0的頁面的狀態位為0x02，表明當前頁面存儲的是B+樹節點，由頁面文件頭部的root_page字段的值可以看出，該節點為樹的根節點；頁號為1的頁面存儲了a.xml，狀態位0x14表明當前頁面存儲的是文檔的數據，并且是第一個頁面；頁號為2和3的頁面存儲了b.xml，3號頁面的狀態位為0x7E，表明它不是文檔的第一個頁面。這時刪除b.xml，那么， mycol.tbl文件的內容將變化如圖3所示：

由于b.xml的刪除，原先占用的2個頁面2和3將變為空閑狀態，狀態位變為0x00，同時，頁面文件的頭部字段first_free_page將指向第一個空閑頁面，last_free_page將指向最后一個空閑頁面，空閑頁面間也使用next_page字段相互連接。

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

4 頁面存儲策略的改進

由上面分析得知，頁面文件的長度不斷增加，就是由于尾部的空閑文件沒有及時釋放造成的。如果能夠釋放掉這些空閑頁面，便可以在一定程度上緩解頁面文件增加的速度。頁面文件頭部記錄了當前頁面的數量pageCount，那么，文件尾部的頁號一定為：

[J]pNum＝pageCount -1 

從頁面文件的尾部進行檢索，如果當前頁面的狀態為空閑，就將該頁面從空閑頁面鏈表中刪除，直到尾部頁面為非空閑頁面為止。采用的算法流程如圖4所示：

空閑頁面截取策略在一定程度上可以緩解文件增加的速度，但由于順序存儲的特性，頁面文件尾部的頁面號都是較大的值。如果在申請頁面時，優先使用頁面號小的空閑頁面，XML文檔的數據能夠盡可能的集中在頁面文件的前面部分，在文件尾部申請新頁面的可能性將降低。為此，必須對空閑頁面進行排序，保證該鏈表以頁號的升序排列。由于空閑頁面鏈表為單鏈表結構，采用插入排序的算法，每當文檔刪除時，將產生的空閑頁面插入到有序鏈表的合適位置。

void truncateFiles(

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

while ( true

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

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]//從頁面空閑鏈表中刪除當前的尾部空閑頁面

}

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

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 結 語

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

參 考 文 獻

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

［2］馮建華，錢乾.純XML數據庫研究綜述[J].計算機應用研究，2006(6:1-4.

［3］陳海建，茅忠明.XML本源數據庫開放模型的設計與實現[J].微計算機信息，2006(22:238-240.

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