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

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

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

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