一種內(nèi)存數(shù)據(jù)庫空間索引的設(shè)計與實現(xiàn).pdf

1、由于空間數(shù)據(jù)往往是海量數(shù)據(jù)，考慮到內(nèi)存價格昂貴以往要將空間數(shù)據(jù)存儲在內(nèi)存數(shù)據(jù)庫中基本是不可能的。隨著近年來計算機硬件技術(shù)的飛速發(fā)展，內(nèi)存價格不斷降低，其容量卻不斷提高，由于內(nèi)存數(shù)據(jù)庫在管理空間數(shù)據(jù)上巨大的實時性優(yōu)勢，可以預(yù)見在不久的將來，內(nèi)存數(shù)據(jù)庫會取代磁盤數(shù)據(jù)庫成為空間數(shù)據(jù)的主要載體，故本課題的目標(biāo)就是設(shè)計一種基于內(nèi)存數(shù)據(jù)庫使用的空間索引結(jié)構(gòu)。
　　 傳統(tǒng)的磁盤數(shù)據(jù)庫的瓶頸在于磁盤I/O，故在設(shè)計時所有算法的一個重要目標(biāo)是減少

2、對磁盤訪問次數(shù)，而在內(nèi)存數(shù)據(jù)庫中，系統(tǒng)對內(nèi)存的讀取速度問題成為了新的瓶頸。如果單純的將傳統(tǒng)基于磁盤數(shù)據(jù)庫的索引套用到內(nèi)存數(shù)據(jù)庫中肯定是不合適的。針對這個問題近年來出現(xiàn)了緩存敏感（Cache-Conscious）技術(shù)，最近的研究也證明通過對基于磁盤的單維索引進(jìn)行緩存敏感改造完全可以應(yīng)用于內(nèi)存數(shù)據(jù)庫且達(dá)到比傳統(tǒng)內(nèi)存數(shù)據(jù)庫單維索引更好的性能。
　　 通過對現(xiàn)有緩存敏感技術(shù)的研究，并在對比分析了幾種常見的空間索引結(jié)構(gòu)后，以空間索引 樹的

3、結(jié)構(gòu)為基礎(chǔ)，提出了基于緩存敏感技術(shù)的一種新的空間索引樹，叫做緩存敏感 樹（CSR,Cache Sensitive-Tree）索引。為了達(dá)到緩存敏感的要求，CSR樹通過幾種方法對R樹的節(jié)點進(jìn)行壓縮，具體方法有去除子節(jié)點中和父節(jié)點中重合的邊界信息；對節(jié)點中最小外包矩形的坐標(biāo)采用相對于父節(jié)點坐標(biāo)的相對坐標(biāo)表示；對坐標(biāo)軸進(jìn)行一定精度的量化等。
　　 最后給出了CSR樹的詳細(xì)數(shù)據(jù)結(jié)構(gòu)與查詢、插入、刪除等常用的算法的偽代碼，并在特定的環(huán)境和