PMR四叉樹空間索引的優(yōu)化研究.pdf

1、當(dāng)前地理信息系統(tǒng)正面臨著海量空間數(shù)據(jù)存儲(chǔ)及管理的挑戰(zhàn),建立高效的空間數(shù)據(jù)索引是實(shí)現(xiàn)海量空間數(shù)據(jù)管理的關(guān)鍵技術(shù)。對(duì)于海量空間數(shù)據(jù)集,索引的構(gòu)造采用逐個(gè)插入數(shù)據(jù)對(duì)象的方法是不可取的,桶載入引起了越來(lái)越多的研究者的興趣。
　　迄今為止,人們已提出了一些有關(guān)空間索引的桶載入方法,但它們大多關(guān)注的是R樹及其相關(guān)結(jié)構(gòu)。對(duì)于其它的索引結(jié)構(gòu),如基于四叉樹,B樹和空間填充曲線相結(jié)合的桶載入問(wèn)題則還沒(méi)有真正地解決。本文在探討一些具有代表性的桶載入方法

2、的基礎(chǔ)上,主要對(duì)能索引任意空間對(duì)象的PMR四叉樹的桶載入技術(shù)進(jìn)行了深入研究。
　　由于桶載入方法是基于外存的算法,I/O復(fù)雜度和空間復(fù)雜度是此類算法性能的評(píng)價(jià)指標(biāo)?？臻g索引通常以B樹形式存貯在磁盤數(shù)據(jù)庫(kù)中,在論文中,首先提出了同時(shí)適用于建庫(kù)和更新的B+樹批量裝載方法。與傳統(tǒng)的B+樹插入算法相比,該方法減少了磁盤讀寫次數(shù)和運(yùn)行時(shí)間,并提高了空間利用率。其次,分析了傳統(tǒng)的PMR四叉樹的插入算法,發(fā)現(xiàn)它采用自頂向下遍歷四叉樹的方法來(lái)確定

3、對(duì)象的插入位置,判定過(guò)程十分繁瑣,于是提出了通過(guò)利用最小封閉塊來(lái)減少了相交測(cè)試次數(shù)的方法,稱之為改進(jìn)的PMR四叉樹插入算法。然后,針對(duì)前人批量構(gòu)造PMR四叉樹方法不能總是達(dá)到最優(yōu)目標(biāo)的缺點(diǎn),在改進(jìn)的插入算法的基礎(chǔ)上,提出了一個(gè)更好的桶載入PMR四叉樹的算法。其中心思想通過(guò)對(duì)對(duì)象以z-order預(yù)排序,在可用內(nèi)存使用完時(shí),利用對(duì)象的插入順序來(lái)選擇將內(nèi)存中哪些葉結(jié)點(diǎn)寫入B+樹,使葉結(jié)點(diǎn)總是以有序的順序進(jìn)行刷新,達(dá)到了更高的空間利用率和建樹速

4、度。接著,探討了擴(kuò)展該桶載入方法去處理向一個(gè)已存在的PMR四叉樹進(jìn)行桶插入構(gòu)造索引的問(wèn)題,并給出了桶插入PMR四叉樹的算法。最后,對(duì)動(dòng)態(tài)插入方法和桶載入方法在執(zhí)行時(shí)間上進(jìn)行了實(shí)驗(yàn)比較,實(shí)驗(yàn)數(shù)據(jù)包括真實(shí)數(shù)據(jù)和人工數(shù)據(jù),實(shí)驗(yàn)結(jié)果表明桶載入方法使得四叉樹的構(gòu)造速度相對(duì)于傳統(tǒng)的四叉樹構(gòu)造方法有較大的提高。同時(shí),本文的桶載入方法可運(yùn)用到許多基于規(guī)則劃分的空間數(shù)據(jù)結(jié)構(gòu)上,來(lái)加快它們的構(gòu)造。因此,PMR四分樹空間索引的優(yōu)化研究,對(duì)地理信息系統(tǒng)發(fā)展和空