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

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

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

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