基于空間分解的路徑多維索引查詢方法研究與實現(xiàn).pdf

1、XML作為一種數(shù)據(jù)描述語言，由于其內(nèi)容與形式分離、易擴展、和易移植的特點，已經(jīng)成為廣泛應用的數(shù)據(jù)交換標準。基于XML的數(shù)據(jù)查詢十分頻繁，如何提高XML數(shù)據(jù)查詢效率也一直是領域研究熱點。XML數(shù)據(jù)索引的性能是決定其查詢效率的關鍵因素，路徑多維索引(Universal B+-Tree，簡稱UB-Tree)是一種將路徑轉(zhuǎn)化為空間地址，進而實現(xiàn)對數(shù)據(jù)進行多維管理的索引結(jié)構(gòu)，由于其擺脫了原有的路徑匹配只能基于字符串匹配的特點，逐漸成為XML數(shù)據(jù)索

2、引的一個重要實現(xiàn)技術，其中區(qū)域查詢算法的效率以及區(qū)間存儲方式是該技術中的重要研究課題。
　　 目前已實現(xiàn)的具有代表性的XML路徑多維索引方法是的UB-Tree方法(Universal B+-Tree)。UB-Tree方法存在兩個問題：1)索引樹中的節(jié)點記錄一個區(qū)間，但數(shù)據(jù)分布的無規(guī)律性使得區(qū)間內(nèi)通常只有少量數(shù)據(jù)點，對數(shù)據(jù)查詢的效率造成很大影響；2)在數(shù)據(jù)查詢時無法避免對空數(shù)據(jù)區(qū)間的遍歷。以上兩個問題顯著影響UB-Tree方法查詢

3、的效率。
　　 本文的研究擬對以上兩個問題進行改進。首先，針對存儲空間使用率不高，存在大量無數(shù)據(jù)區(qū)間的問題，本文在以區(qū)間段存儲取代原有的區(qū)間分割地址儲存方式的基礎上，采用改進的邊界區(qū)間存儲方式對批量數(shù)據(jù)進行存儲，有效提升了空間的有效利用，并減少了存儲結(jié)構(gòu)中對無數(shù)據(jù)區(qū)間的保存開銷；其次，針對數(shù)據(jù)查詢存在的效率問題，本文在Tomas Skopal等人提出的基于區(qū)間相交性判斷的改進DRU區(qū)域查詢算法基礎上，采用空間分解的方法對查詢區(qū)域