基于CB＋－tree的時態(tài)XML索引動態(tài)更新方法*

馬程，徐海燕

（1.蚌埠學院計算機科學與技術系，安徽蚌埠233000；2.華為軟件技術有限公司南京研究所，江蘇南京210008）

基于CB＋－tree的時態(tài)XML索引動態(tài)更新方法*

馬程1，徐海燕2

（1.蚌埠學院計算機科學與技術系，安徽蚌埠233000；2.華為軟件技術有限公司南京研究所，江蘇南京210008）

針對時態(tài)XML更新問題，使用了CB＋－tree索引時態(tài)XML文檔和文檔添加冗余空間存儲，借助時態(tài)信息索引、實體地址索引雙重索引和文檔冗余存儲方式高效地實現文檔的局部更新。實驗結果表明，將實體時態(tài)信息和地址索引分離，并為文檔添加冗余空間，減少了XML文檔更新時間，其效率明顯提高。

B＋－tree索引；動態(tài)更新；時態(tài)XML

隨著XML數據的大量涌現，有效實現其存儲、索引和查詢一直是XML相關技術領域研究的熱點，但XML文檔的更新始終是XML數據操作的一個難點。目前國內外對時態(tài)XML的研究還處于起步階段，其索引方面有了一些研究成果。例如，Alberto O.Mendelzon提出了一種TempIndex［1］索引機制，它包含三種結構：時態(tài)模式、時態(tài)深度表、cp和cp＋value表。葉小平等人［2］提出了一種時態(tài)XML查詢數據模型TXQDM，在模型中引入TXQDM結點間時態(tài)連通概念，構建了結點間的一種等價關系，通過研究結點分類和等價類中結點間時態(tài)包含產生的擬序結構，從而建立了時態(tài)XML索引數據模型TXIDM。陳麗冰等人［3］基于擴展的XPath模型，構建了一種時間連通性的等價關系，并且在該關系的等價類基礎上建立索引。通常XML文檔部分內容更新時，大量移動數據非常耗時。針對文檔更新，文章提出了CB＋－tree實體地址索引和文檔增加冗余空間存儲，該方法在動態(tài)實現文檔的局部更新時效率較高。

1 相關技術概述

1.1 時態(tài)XML文檔

XML文檔可以被建模成基于XPath有序、具有邊標記的結點層次圖形結構［4］。為實現自身查詢，以這種結構為基礎，建立XML查詢數據模型。時態(tài)查詢XML數據模型，即在常規(guī)模型上添加時態(tài)信息［5］。

1.2 CB＋－tree原理

CB＋－tree（Changing B＋－tree）是改進B＋－tree的平衡樹，根節(jié)點處至少有兩個子節(jié)點，包含m個關鍵字的中間節(jié)點，m＋1個指針Pi（每個指針指向下層子節(jié)點）。CB＋－tree不同于B＋－tree，葉子節(jié)點新增三種指針：

（1）第一種指針，用于指向同一層次節(jié)點，有前向指針和后向指針，葉子節(jié)點間形成一個雙向鏈表。

（2）第二種指針，用于指向處理重復鍵值的查詢鏈表，每個葉子節(jié)點包含一個指針數組m_pointers［m］。如插入的鍵值與葉子節(jié)點中的某個鍵值相同時，就在其后面分配一個鏈表，用來存儲剛插進來的新鍵值，插入時按照tend從大到小的順序進行。

（3）第三種指針MPointer，仍指向鏈表，但該鏈表的作用是，將該葉子節(jié)點中的所有數據（不含m_pointer［m］所指鏈表中的數據）按照tend從大到小的順序，依次插入單鏈表中。當進行快照查詢或時間段查詢時，可以減少與tend的比較時間，以提高查詢效率。

2 時態(tài)XML索引結構及文檔存儲方式

采用職工數據庫作為實驗數據集，CB＋－tree索引的關鍵字的結構是（id，tend，tstart，addr，length，filename）；id為實體號，tend和tstart分別設置為實體的事務結束和開始時刻，addr為實體在文檔中的偏移地址，length為實體的信息長度，filename為實體的路徑。

2.1 TCB＋－tree和ACB＋－tree

在CB＋－tree中間節(jié)點和葉子節(jié)點的關鍵字中，都包含上文提到的所有信息。根據CB＋－tree的特性，僅需從到達葉子節(jié)點的MPointer和m_pointer［m］中取出其實體的地址信息，利用文檔實體的addr和length，即可隨機調出全部信息，而中間節(jié)點包含的addr、length和filename，會造成索引空間的浪費。

為了解決這一缺陷，提出了建立TCB＋－tree（Temporal CB＋－tree）和ACB＋－tree（Address CB＋－tree）的雙重索引，其核心仍是CB＋－tree。TCB＋－tree索引實體的時態(tài)信息，ACB＋－tree索引實體的地址信息。TCB＋－tree的關鍵字結構為（id，tstart，tend），tstart作為索引關鍵字；ACB＋－tree的索引關鍵字為id，其葉子節(jié)點的m_pointer［m］中鏈表數據字段為（id，addr，length，filename）。

2.2 添加冗余的文檔存儲方式

在存儲時態(tài)XML文檔時，為了充分利用存儲空間，通常對多個實體進行連續(xù)存儲，但這種存儲方式很難實現文檔的局部更新，尤其是對體積較大的文檔。比如：在某個實體中添加或刪除信息時，該實體后面所有內容都要向后移動重新寫入，非常耗時。為減少移動頻率，存儲每個實體后緊接著寫入一些冗余空白，然后再存儲下一個實體的信息，如圖3所示。存儲方式修改后，ACB＋－tree鏈表中的數據需增加新的字段blankspace，更新為（id，addr，length，blankpspace，filename）。blank

space用于記錄實體信息后冗余空白的大小，用戶可根據需要設置

從混合烴組分的MMP實驗結果得到以下認識:混合體系組分中芳香烴為主的方案的MMP最大、環(huán)烷烴為主的方案的MMP次之、烷烴為主的方案的MMP最小，這與單組分烴類的實驗結果相符;與單一組分主要區(qū)別在于，混合烴組分/CO2的MMP均小于相同碳數的單組分/CO 2的MMP，這主要是混合組分中不同分子作用力綜合作用的結果。

blackspace大小，隨著實體信息的變化，其blankspace也相應更新。

圖3 添加冗余的文檔存儲方式

3 更新操作

XML文檔的更新包括文檔的全文更新和局部更新兩種形式。文章僅討論文檔的局部更新問題。實體元素的更新，主要包含元素的插入、刪除和內容的修改。時態(tài)XML文檔的局部更新，主要涉及到tend或tstart的變化，而父、子元素的tend和tstart具有相關性，導致實體在TCB＋－tree中的關鍵字信息可能需要更新，同時，實體的addr、length可能也需要更新。若是添加冗余后的更新，還需要更新blankspace。元素的更新、刪除與插入原理相通，選取元素的插入操作進行效率比對分析。

3.1 基于DOM的插入

基于DOM的插入需要把整個文檔先調入內存，用樹形結構來存儲XML文檔。向實體id插入新的元素，即需要通過遍歷找到相應id的子樹，然后為該子樹添加新的節(jié)點。該插入過程非常耗時，一是大體積文檔的調入和解析非常耗時；二是需要通過遍歷，才能查找到正確的插入位置。

3.2 未添加冗余空白前的插入

基于TCB＋－tree、ACB＋－tree雙重索引，未添加冗余空白前的插入過程為：插入新實體，以實體id為關鍵字，使用ACB＋－tree索引查詢，查詢到id時，讀取對應鏈表中數據（id，addr，length，filename），根據addr獲取該實體的全部信息，并將其作為一個XML文檔進行解析，使用XML操作中的插入函數進行插入。如果實體變化，把更新后的實體信息重新寫入文檔，其后的實體也全部后移、重新寫入，導致需要更新所有后移實體在ACB＋－tree索引中的addr。若實體元素的插入，引起了父節(jié)點的tend、tstart或二者同時變化，還需更新TCB＋－tree。TCB＋－tree是以tstart為關鍵字建立的索引，根據id號查詢，則需遍歷整個文檔，故借助輔助結構（id，oldtstart，newtstart，oldtend，newtend）記錄實體更新前后的tend和tstart，采用oldstart作為搜索關鍵字，在TCB＋－tree中找出該實體的時態(tài)信息位置，再刪除原節(jié)點，插入新節(jié)點。

3.3 添加冗余空白的插入

（1）根據輸入的待插入元素的實體號id，調用ACB＋－tree的Search算法。如果未查找id，則返回false；如果查找到了，則根據該關鍵字中的addr和length字段，獲取該實體信息的XML文檔片段tempXML。

（2）調用XmlDocument的LoadXml方法，解析該XML片段，再調用DOM相應函數，將新元素信息插入。

（3）插入后，對比插入前l(fā)ength與當前實體信息newlength，獲取addlength＝newlength－length。

（4）根據實體號id，在ACB＋－tree中查詢該關鍵字對應的葉子節(jié)點；查詢到該實體關鍵字后，將addlength與其blankspace比較。如果addlength大于blankspace，設置blankspace為0，記錄下超出冗余空間的長度newaddrlength＝addlength－blankspace，將id的length更新為length＋newaddrlength。通過id對應的葉子節(jié)點m_pNextNode指針，循環(huán)訪問后面所有的葉子節(jié)點，并將該實體后所有實體的addr改為addr＋newaddlength。如果addlength小于blankspace，可以直接插入新的內容，將實體的blankspace更新為blankspaceaddlength即可，同時將該實體索引關鍵字對應的length改為length＋addlength。

（5）插入新元素后，若其tend或tstart屬性引起父節(jié)點tend或tstart更新，需根據父節(jié)點原tstart值，在TCB＋－tree中查詢出該實體索引關鍵字位置，刪除該關鍵字，再重新插入tend或tstart更新后的關鍵字。如果未引起父節(jié)點的tend或tstart更新，則不需要更新TCB＋－tree索引。

（6）根據id的addr起始地址，將新的XML文檔內容重新寫入XML文檔中。返回true。

4 實驗分析

實驗環(huán)境：CPU為Intel Pentium D 930（1G），系統(tǒng)為Windows XP Professional，生成和查詢XML文檔的開發(fā)環(huán)境為.NET2005中的C＃，實驗數據來自于TimeCenter的職工數據庫。該數據庫三個文件夾共15 004個XML文件，300 000個職工的歷史和當前信息。

4.1 實驗過程

首先，對源數據進行冗余消除。如果子節(jié)點的tend、tstart屬性與父節(jié)點的屬性值相同，子節(jié)點不再存儲與父節(jié)點相同的時間屬性，消除冗余；其次，分別取5 002、10 004個XML文檔合并，合并后大小依次為86 MB、169 MB；最后，在合并后的兩個文檔內分別實現向100個實體中插入，實體號隨機產生。

4.2 實驗數據

基于TCB＋－tree和ACB＋－tree的雙重索引，分析冗余大小對更新時間的影響，其實驗結果見表1。

表1 冗余大小對更新時間的影響

由表1可知，冗余空白大于插入內容的條件下，冗余的大小對更新時間的效率影響不大。

基于TCB＋－tree、ACB＋－tree雙重索引在圖示中使用CB＋－tree來標識。由于冗余空白的更新時間很小，而基于DOM的更新時間遠比用索引的更新時間大，為在圖中清晰顯示添加冗余空白的更新時間，實驗中采取DOM更新花費時間的十分之一作為比較標準。基于CB＋－tree、B＋－tree、DOM三種方法，分別對原始文檔中插入實體（即未添加冗余空白）和添加冗余空白的插入進行實驗，其更新時間如圖4、圖5所示。對采用B＋－tree、CB＋－tree方式對添加冗余前后的更新時間進行對比，其結果如圖6所示。

圖4 三種方式對原始文檔插入比較

圖5 三種方式添加冗余空白的插入比較

圖6 B＋－tree、CB＋－tree方式冗余前后對比

由圖4可知，在原始文檔中插入實體基于CB＋－tree和B＋－tree的更新效率比基于DOM明顯提高，而且文檔越大效率提高越明顯，且基于CB＋－tree雙重索引的更新效率比基于B＋－tree的更新效率也有提高，但是基于CB＋－tree和B＋－tree的更新時間并不理想。由圖5可知，使用冗余存儲方式，基于CB＋－tree的更新效率遠遠高于基于B＋－tree和DOM的更新。由圖6可知，添加冗余后基于CB＋－tree和B＋－tree索引對時態(tài)XML文檔更新的效率提高顯著，但基于CB＋－tree和冗余空白的更新效率更高。

5 總結和展望

文章提出了時態(tài)和地址信息分開索引的雙重索引，TCB＋－tree以tstart作為索引關鍵字方便時態(tài)查詢，如果時態(tài)信息沒有變化，則不需要更新TCB＋－tree；ACB＋－tree以id作為索引關鍵字，便于通過id號查詢地址信息。同時，添加冗余空白減少文檔更新時頻繁移動重新寫入的操作。實驗證明，采用雙重索引和添加冗余空白減少了文檔更新時間，提高了文檔和索引更新的效率。

［1］Mendelzon A O，Rizzolo F，Vaisman A.Indexing Temporal XML Documents［C］//VLDB.Proceedings 2004 VLDB Conference 2004.San Francisco：Margan Kaufmann Publishers，2004：216－227.

［2］葉小平，陳鎧原，湯庸，等.時態(tài)XML索引技術［J］.計算機學報，2007，30（7）：1074－1085.

［3］陳麗冰，吉永杰，鄧楚燕.一種基于擴展時態(tài)XML模型的索引技術［J］.微型計算機信息，2006，22（5）：301－303.

［4］郭歡，葉小平，湯庸，等.基于時態(tài)編碼和線序劃分的時態(tài)XML索引［J］.軟件學報，2012，23（8）：2042－2057.

［5］葉小平，林衍崇，陳釗瀅，等.時態(tài)XML索引Txmlsindex［J］.華南師范大學學報（自然科學版），2015，47（1）：116－120.

Dynamic Update Based on CB＋－tree Temporal XML Index

MA Cheng1，XU Haiyan2
（1.Computer Department，Bengbu College，Bengbu 233000，China；2.Nanjing Research Institute of Huawei Software Technology Limited Company，Nanjing 210008，China）

Focused on the problem of temporal XML update，this paper uses CB＋－tree to index temporal XML，double indexes of temporal attributes and entities address，document redundancy storage to implement local document update efficiently.Experimental results show that the time of update XML document is reduced and the efficiency is improved obviously through Separating entity temporal information and address，adding redundancy space for document.

B＋－tree index；Dynamic update；Temporal XML

TP311.13

A

2095－2562（2016）01－0044－04

（責任編輯：黃容）

2015－11－20；

2016－01－10

2014年度蚌埠學院院級自然科學研究重點項目（2014ZR03zd）；2016年度安徽省自然科學研究重點項目（KJ2016A456）

馬程（1980—），女，安徽阜陽人，碩士，講師，主要研究方向為數據挖掘、時空數據庫索引。