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

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

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

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

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