空間數(shù)據(jù)庫(kù)索引技術(shù)課件

空間數(shù)據(jù)庫(kù)索引技術(shù)空間數(shù)據(jù)庫(kù)索引技術(shù)目錄空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)空間數(shù)據(jù)庫(kù)的索引是提高空間數(shù)據(jù)庫(kù)存儲(chǔ)效率、空間檢索性能的關(guān)鍵技術(shù)。目錄空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)空間數(shù)

空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù),例如地圖上的經(jīng)緯度、湖泊、城市等。典型的關(guān)系型數(shù)據(jù)庫(kù)模式中,并沒有存儲(chǔ)空間數(shù)據(jù)的位置,它只能處理單維的屬性數(shù)據(jù)。所謂單維屬性數(shù)據(jù)是指?jìng)鹘y(tǒng)類型(包括數(shù)字型、字符型等)的數(shù)據(jù),它不包括描述空間位置和形狀的坐標(biāo)信息和描述空間關(guān)系的拓?fù)湫畔?。與傳統(tǒng)的數(shù)據(jù)庫(kù)相比,空間數(shù)據(jù)的處理是一項(xiàng)時(shí)間和空間開銷更大的操作。為了有效提高對(duì)空間數(shù)據(jù)的處理效率,空間數(shù)據(jù)庫(kù)必須利用有效的索引機(jī)制?？臻g數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)空間數(shù)據(jù)是指與二維、三維空間數(shù)據(jù)空間數(shù)據(jù)空間數(shù)據(jù)的特征1.數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性2.數(shù)據(jù)的動(dòng)態(tài)性3.數(shù)據(jù)的海量性4.沒有標(biāo)準(zhǔn)的空間代數(shù)操作5.時(shí)間代價(jià)比較大6.多尺度與多態(tài)性7.不能排序性8.空間關(guān)系特性空間數(shù)據(jù)的特征1.數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性2.數(shù)據(jù)的動(dòng)態(tài)性3數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性對(duì)于空間數(shù)據(jù)來(lái)說，空間對(duì)象有可能是點(diǎn)、線或者其他類型的對(duì)象，因此在數(shù)據(jù)庫(kù)進(jìn)行存儲(chǔ)的時(shí)候，不可能用一種固定長(zhǎng)度的數(shù)據(jù)類型來(lái)存取所有的數(shù)據(jù)，需要根據(jù)對(duì)象的不同情況來(lái)選擇合適的數(shù)據(jù)結(jié)構(gòu)。沒有標(biāo)準(zhǔn)的空間代數(shù)操作數(shù)據(jù)的海量性數(shù)據(jù)的動(dòng)態(tài)性這個(gè)特性要求數(shù)據(jù)結(jié)構(gòu)要能夠適應(yīng)由插入、刪除或者更新等操作所引起的數(shù)據(jù)的變化?？臻g數(shù)據(jù)的數(shù)據(jù)量是非常巨大的，通常成為海量數(shù)據(jù)，一個(gè)城市的地理信息系統(tǒng)中的數(shù)據(jù)可以達(dá)到幾十GB，若將視頻數(shù)據(jù)也加在其中，可以達(dá)到TB的數(shù)量級(jí)。在空間數(shù)據(jù)庫(kù)中，空間對(duì)象的操作并沒有一定的標(biāo)準(zhǔn)，通常要根據(jù)實(shí)際的應(yīng)用領(lǐng)域來(lái)確定，而且操作是不封閉的,對(duì)象的相交可能形狀就會(huì)發(fā)生變化，這也是導(dǎo)致空間代數(shù)操作不能標(biāo)準(zhǔn)化的重要原因。數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性對(duì)于空間數(shù)據(jù)來(lái)說，空間對(duì)象有可能是點(diǎn)多尺度與多態(tài)性同一個(gè)空間對(duì)象，在不同的觀察尺度具有不同的比例尺和精度，導(dǎo)致一個(gè)對(duì)象在不同的情況下，其表現(xiàn)的形態(tài)也各不相同,如一個(gè)城市一定的比例尺下就退化為一個(gè)點(diǎn)?？臻g關(guān)系特性不能排序性空間對(duì)象都有其空間位置信息，無(wú)法對(duì)空間數(shù)據(jù)進(jìn)行線性排序并且保證空間相鄰的對(duì)象仍然能夠相鄰?？臻g數(shù)據(jù)不僅僅包含了空間的位置信息，而且包含了對(duì)象的拓?fù)湫畔?，這些信息方便空間數(shù)據(jù)的查詢和空間分析，但同時(shí)也增加了對(duì)空間數(shù)據(jù)一致性和完整性的維護(hù)復(fù)雜度?？臻g數(shù)據(jù)的海量性，加上操作的不標(biāo)準(zhǔn)，沒有更好的標(biāo)準(zhǔn)的方法進(jìn)行查詢優(yōu)化，所以對(duì)于各種操作所花費(fèi)的時(shí)間代價(jià)也各不相同，但往往都高于傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)的操作代價(jià)。時(shí)間代價(jià)比較大多尺度與多態(tài)性同一個(gè)空間對(duì)象，在不同的觀察尺度具有不同的比例

空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)庫(kù)空間數(shù)據(jù)庫(kù)指的是GIS地理信息系統(tǒng)在計(jì)算機(jī)物理存儲(chǔ)介質(zhì)上存儲(chǔ)的與應(yīng)用相關(guān)的地理空間數(shù)據(jù)的總和，一般是以一系列特定結(jié)構(gòu)的文件的形式組織在存儲(chǔ)介質(zhì)之上的?？臻g數(shù)據(jù)庫(kù)的研究始于20世紀(jì)70年代的地圖制圖與調(diào)干圖像處理領(lǐng)域，其目的是為了有效地利用衛(wèi)星遙感資源迅速繪制出各種經(jīng)濟(jì)專題地圖。由于傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)在空間數(shù)據(jù)的表示、存儲(chǔ)、管理、檢索上存在許多缺陷，從而形成了空間數(shù)據(jù)庫(kù)這一數(shù)據(jù)庫(kù)研究領(lǐng)域。而傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)只針對(duì)簡(jiǎn)單對(duì)象，無(wú)法有效的支持復(fù)雜對(duì)象（如圖形、圖像）。注：空間數(shù)據(jù)庫(kù)就是將GIS中的圖層、數(shù)據(jù)集、網(wǎng)絡(luò)、拓?fù)潢P(guān)系存在關(guān)系等數(shù)據(jù)庫(kù)中，如SQLSERVER、ORACLE、Access等，就構(gòu)成了一個(gè)空間數(shù)據(jù)庫(kù)?？臻g數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)庫(kù)空間數(shù)據(jù)庫(kù)指的是GIS

空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間索引空間索引是指依據(jù)空間對(duì)象的位置和形狀或空間對(duì)象之間的某種空間關(guān)系,按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu),其中包含空間對(duì)象的概要信息。作為一種輔助性的空間數(shù)據(jù)結(jié)構(gòu),空間索引介于空間操作算法與空間對(duì)象之間,它通過篩選作用,大量與特定空間操作無(wú)關(guān)的空間對(duì)象被排除,從而提高空間操作的速度和效率?？臻g索引的性能優(yōu)劣直接影響空間數(shù)據(jù)庫(kù)和地理信息系統(tǒng)的整體性能,它是空間數(shù)據(jù)庫(kù)和地理信息系統(tǒng)的一項(xiàng)關(guān)鍵技術(shù)?？臻g數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間索引空間索引是指依據(jù)空間對(duì)象空間索引結(jié)構(gòu)的特點(diǎn)1.動(dòng)態(tài)構(gòu)造2.二級(jí)/三級(jí)存儲(chǔ)管理3.支持盡量多的操作4.獨(dú)立于輸入數(shù)據(jù)及插入順序5.可增長(zhǎng)性6.時(shí)間的有效性7.空間的有效性8.并行性及可恢復(fù)性空間索引結(jié)構(gòu)的特點(diǎn)1.動(dòng)態(tài)構(gòu)造2.二級(jí)/三級(jí)存儲(chǔ)管理3.支動(dòng)態(tài)構(gòu)造在數(shù)據(jù)庫(kù)中，數(shù)據(jù)有動(dòng)態(tài)和靜態(tài)兩種，由于對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)需要有一定的操作，比如插入或刪除，因此要求索引結(jié)構(gòu)也必須能夠與之保持一致，即空間的索引結(jié)構(gòu)也應(yīng)該支持動(dòng)態(tài)的數(shù)據(jù)的插入和刪除，以便于維護(hù)數(shù)據(jù)的一致性。獨(dú)立于輸入數(shù)據(jù)及插入順序支持盡量多的操作二級(jí)/三級(jí)存儲(chǔ)管理盡管隨著技術(shù)的發(fā)展，主存的容量日益增大，但仍不能將一個(gè)完整的數(shù)據(jù)庫(kù)調(diào)入到主存中，因此索引結(jié)構(gòu)要充分考慮到二級(jí)以及三級(jí)的存儲(chǔ)管理，以提高對(duì)這中間緩存的利用率。輸入數(shù)據(jù)的順序?qū)τ行┧饕Y(jié)構(gòu)的索引效率產(chǎn)生一定的影響，有些索引結(jié)構(gòu)在不同的輸入順序下會(huì)產(chǎn)生不同的索引并且性能差異很大，因此空間索引結(jié)構(gòu)應(yīng)該支持各種高維數(shù)據(jù)，并且支持任意的插入順序，使索引結(jié)構(gòu)能夠適用于各種數(shù)據(jù)的情況。索引結(jié)構(gòu)應(yīng)支持多種操作以滿足不同數(shù)據(jù)的類型需要，在提高對(duì)某些數(shù)據(jù)處理能力的基礎(chǔ)上，不能犧牲其它的操作的處理能力，應(yīng)同時(shí)保持相應(yīng)的處理性能。

動(dòng)態(tài)構(gòu)造在數(shù)據(jù)庫(kù)中，數(shù)據(jù)有動(dòng)態(tài)和靜態(tài)兩種，由于對(duì)數(shù)據(jù)庫(kù)中的數(shù)可增長(zhǎng)性索引結(jié)構(gòu)要能夠根據(jù)數(shù)據(jù)庫(kù)大小的增長(zhǎng)而調(diào)整相應(yīng)的結(jié)構(gòu)，具有一定的自適應(yīng)性。并行性及可恢復(fù)性空間的有效性時(shí)間的有效性查找速度必須是快速的，要求查詢或者更新等操作的時(shí)間復(fù)雜度要低。索引結(jié)構(gòu)要能夠支持并行操作，以提高查詢的效率，并在發(fā)生異常時(shí)，可以較快的對(duì)建立的索引結(jié)構(gòu)進(jìn)行重建，即要有一定的可恢復(fù)性。一個(gè)索引結(jié)構(gòu)同其原始數(shù)據(jù)相比應(yīng)是比較小的，從而保證一定的空間利用率?？稍鲩L(zhǎng)性索引結(jié)構(gòu)要能夠根據(jù)數(shù)據(jù)庫(kù)大小的增長(zhǎng)而調(diào)整相應(yīng)的結(jié)構(gòu)，幾種有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)KD-樹類網(wǎng)格文件

R-樹

四叉樹幾種有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)KD-樹類網(wǎng)格文件R網(wǎng)格文件網(wǎng)格文件的基本思想是根據(jù)一正交的網(wǎng)格劃分k維的數(shù)據(jù)空間。k維數(shù)據(jù)空間的網(wǎng)格由k個(gè)一維數(shù)組表示,這些數(shù)組稱為刻度。將其保存在主存?？潭鹊拿恳贿吔鐦?gòu)成k-1維的超平面。整個(gè)數(shù)據(jù)空間被所有的邊界劃分成許多k維的矩形子空間,這些矩形子空間稱為網(wǎng)格目錄,用k維的數(shù)組表示,將其保存在硬盤上。網(wǎng)格目錄的每一網(wǎng)格單元包含一外存頁(yè)的地址,這一外存頁(yè)存儲(chǔ)了該網(wǎng)格單元內(nèi)的數(shù)據(jù)目標(biāo),稱為數(shù)據(jù)頁(yè)。一數(shù)據(jù)頁(yè)允許存儲(chǔ)多個(gè)相鄰網(wǎng)格單元的目標(biāo)。網(wǎng)格文件的查找簡(jiǎn)單,查找效率較高,適用于點(diǎn)目標(biāo)的索引。網(wǎng)格文件網(wǎng)格文件的基本思想是根據(jù)一正交的網(wǎng)格劃分k維的數(shù)據(jù)空KD-樹類KD-樹是k維的二叉查找樹,是二叉查找樹在多維空間的擴(kuò)展。主要用于索引多屬性的數(shù)據(jù)或多維點(diǎn)數(shù)據(jù)。每一個(gè)節(jié)點(diǎn)所表示的k維空間被一個(gè)可能在k個(gè)方向上出現(xiàn)的超平面劃分為兩個(gè)部分。每一個(gè)超平面中至少有一個(gè)點(diǎn)數(shù)據(jù)。KD-樹對(duì)于點(diǎn)匹配查找,它繼承了二叉查找樹的優(yōu)點(diǎn),但刪除操作較復(fù)雜。KD-樹類KD-樹是k維的二叉查找樹,是二叉查找樹在多維空間四叉樹四叉樹實(shí)際上是指在k維數(shù)據(jù)空間中,每一節(jié)點(diǎn)有2k子樹。用于對(duì)空間點(diǎn)的表示與索引。每個(gè)節(jié)點(diǎn)存儲(chǔ)了一空間點(diǎn)的信息及2k個(gè)子節(jié)點(diǎn)的指針。如二維空間的四叉樹,每個(gè)子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)矩形,用四種方位NW,NE,SW,SE表示。逐級(jí)將空間劃分到含有數(shù)據(jù)的個(gè)數(shù)低于某一值的矩形為止。四叉樹四叉樹實(shí)際上是指在k維數(shù)據(jù)空間中,每一節(jié)點(diǎn)有2k子樹。R-樹R-樹是B-樹在多維空間的擴(kuò)展,其特點(diǎn)是能索引一定范圍內(nèi)的對(duì)象。其葉子節(jié)點(diǎn)包含多個(gè)形式為(OI,MBR)的實(shí)體,OI為空間目標(biāo)標(biāo)志,MBR為該目標(biāo)在k維空間中的最小包圍矩形。非葉子節(jié)點(diǎn)包含多個(gè)形式為(CP,MBR)的實(shí)體。CP為指向子樹根節(jié)點(diǎn)的指針,MBR為包圍其子節(jié)點(diǎn)中所有MBR的最小包圍矩形。R-樹必須滿足如下特性:(1)若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn),則至少有兩棵子樹;(2)除根之外的所有中間節(jié)點(diǎn)至多有M棵子樹,至少有m棵子樹;(3)每個(gè)葉子節(jié)點(diǎn)均包含m至M個(gè)數(shù)據(jù)項(xiàng);(4)所有的葉子節(jié)點(diǎn)都出現(xiàn)在同一層次;(5)所有節(jié)點(diǎn)都需要同樣的存儲(chǔ)空間(通常為一個(gè)磁盤頁(yè))。因此各子空間會(huì)產(chǎn)生重疊;查找路徑也往往是多條的。隨著索引數(shù)據(jù)量的增加,包圍矩形的重疊會(huì)增加,將嚴(yán)重影響查找性能。R-樹R-樹是B-樹在多維空間的擴(kuò)展,其特點(diǎn)是能索引一定范圍R-樹R-樹THANKSTHANKS

空間數(shù)據(jù)庫(kù)索引技術(shù)空間數(shù)據(jù)庫(kù)索引技術(shù)目錄空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)空間數(shù)據(jù)庫(kù)的索引是提高空間數(shù)據(jù)庫(kù)存儲(chǔ)效率、空間檢索性能的關(guān)鍵技術(shù)。目錄空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)空間數(shù)

空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)空間數(shù)據(jù)是指與二維、三維或更高維空間的空間坐標(biāo)及空間范圍相關(guān)的數(shù)據(jù),例如地圖上的經(jīng)緯度、湖泊、城市等。典型的關(guān)系型數(shù)據(jù)庫(kù)模式中,并沒有存儲(chǔ)空間數(shù)據(jù)的位置,它只能處理單維的屬性數(shù)據(jù)。所謂單維屬性數(shù)據(jù)是指?jìng)鹘y(tǒng)類型(包括數(shù)字型、字符型等)的數(shù)據(jù),它不包括描述空間位置和形狀的坐標(biāo)信息和描述空間關(guān)系的拓?fù)湫畔?。與傳統(tǒng)的數(shù)據(jù)庫(kù)相比,空間數(shù)據(jù)的處理是一項(xiàng)時(shí)間和空間開銷更大的操作。為了有效提高對(duì)空間數(shù)據(jù)的處理效率,空間數(shù)據(jù)庫(kù)必須利用有效的索引機(jī)制?？臻g數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)空間數(shù)據(jù)是指與二維、三維空間數(shù)據(jù)空間數(shù)據(jù)空間數(shù)據(jù)的特征1.數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性2.數(shù)據(jù)的動(dòng)態(tài)性3.數(shù)據(jù)的海量性4.沒有標(biāo)準(zhǔn)的空間代數(shù)操作5.時(shí)間代價(jià)比較大6.多尺度與多態(tài)性7.不能排序性8.空間關(guān)系特性空間數(shù)據(jù)的特征1.數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性2.數(shù)據(jù)的動(dòng)態(tài)性3數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性對(duì)于空間數(shù)據(jù)來(lái)說，空間對(duì)象有可能是點(diǎn)、線或者其他類型的對(duì)象，因此在數(shù)據(jù)庫(kù)進(jìn)行存儲(chǔ)的時(shí)候，不可能用一種固定長(zhǎng)度的數(shù)據(jù)類型來(lái)存取所有的數(shù)據(jù)，需要根據(jù)對(duì)象的不同情況來(lái)選擇合適的數(shù)據(jù)結(jié)構(gòu)。沒有標(biāo)準(zhǔn)的空間代數(shù)操作數(shù)據(jù)的海量性數(shù)據(jù)的動(dòng)態(tài)性這個(gè)特性要求數(shù)據(jù)結(jié)構(gòu)要能夠適應(yīng)由插入、刪除或者更新等操作所引起的數(shù)據(jù)的變化?？臻g數(shù)據(jù)的數(shù)據(jù)量是非常巨大的，通常成為海量數(shù)據(jù)，一個(gè)城市的地理信息系統(tǒng)中的數(shù)據(jù)可以達(dá)到幾十GB，若將視頻數(shù)據(jù)也加在其中，可以達(dá)到TB的數(shù)量級(jí)。在空間數(shù)據(jù)庫(kù)中，空間對(duì)象的操作并沒有一定的標(biāo)準(zhǔn)，通常要根據(jù)實(shí)際的應(yīng)用領(lǐng)域來(lái)確定，而且操作是不封閉的,對(duì)象的相交可能形狀就會(huì)發(fā)生變化，這也是導(dǎo)致空間代數(shù)操作不能標(biāo)準(zhǔn)化的重要原因。數(shù)據(jù)結(jié)構(gòu)的復(fù)雜性和多樣性對(duì)于空間數(shù)據(jù)來(lái)說，空間對(duì)象有可能是點(diǎn)多尺度與多態(tài)性同一個(gè)空間對(duì)象，在不同的觀察尺度具有不同的比例尺和精度，導(dǎo)致一個(gè)對(duì)象在不同的情況下，其表現(xiàn)的形態(tài)也各不相同,如一個(gè)城市一定的比例尺下就退化為一個(gè)點(diǎn)?？臻g關(guān)系特性不能排序性空間對(duì)象都有其空間位置信息，無(wú)法對(duì)空間數(shù)據(jù)進(jìn)行線性排序并且保證空間相鄰的對(duì)象仍然能夠相鄰?？臻g數(shù)據(jù)不僅僅包含了空間的位置信息，而且包含了對(duì)象的拓?fù)湫畔?，這些信息方便空間數(shù)據(jù)的查詢和空間分析，但同時(shí)也增加了對(duì)空間數(shù)據(jù)一致性和完整性的維護(hù)復(fù)雜度?？臻g數(shù)據(jù)的海量性，加上操作的不標(biāo)準(zhǔn)，沒有更好的標(biāo)準(zhǔn)的方法進(jìn)行查詢優(yōu)化，所以對(duì)于各種操作所花費(fèi)的時(shí)間代價(jià)也各不相同，但往往都高于傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)的操作代價(jià)。時(shí)間代價(jià)比較大多尺度與多態(tài)性同一個(gè)空間對(duì)象，在不同的觀察尺度具有不同的比例

空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)庫(kù)空間數(shù)據(jù)庫(kù)指的是GIS地理信息系統(tǒng)在計(jì)算機(jī)物理存儲(chǔ)介質(zhì)上存儲(chǔ)的與應(yīng)用相關(guān)的地理空間數(shù)據(jù)的總和，一般是以一系列特定結(jié)構(gòu)的文件的形式組織在存儲(chǔ)介質(zhì)之上的?？臻g數(shù)據(jù)庫(kù)的研究始于20世紀(jì)70年代的地圖制圖與調(diào)干圖像處理領(lǐng)域，其目的是為了有效地利用衛(wèi)星遙感資源迅速繪制出各種經(jīng)濟(jì)專題地圖。由于傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)在空間數(shù)據(jù)的表示、存儲(chǔ)、管理、檢索上存在許多缺陷，從而形成了空間數(shù)據(jù)庫(kù)這一數(shù)據(jù)庫(kù)研究領(lǐng)域。而傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)只針對(duì)簡(jiǎn)單對(duì)象，無(wú)法有效的支持復(fù)雜對(duì)象（如圖形、圖像）。注：空間數(shù)據(jù)庫(kù)就是將GIS中的圖層、數(shù)據(jù)集、網(wǎng)絡(luò)、拓?fù)潢P(guān)系存在關(guān)系等數(shù)據(jù)庫(kù)中，如SQLSERVER、ORACLE、Access等，就構(gòu)成了一個(gè)空間數(shù)據(jù)庫(kù)?？臻g數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間數(shù)據(jù)庫(kù)空間數(shù)據(jù)庫(kù)指的是GIS

空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間索引空間索引是指依據(jù)空間對(duì)象的位置和形狀或空間對(duì)象之間的某種空間關(guān)系,按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu),其中包含空間對(duì)象的概要信息。作為一種輔助性的空間數(shù)據(jù)結(jié)構(gòu),空間索引介于空間操作算法與空間對(duì)象之間,它通過篩選作用,大量與特定空間操作無(wú)關(guān)的空間對(duì)象被排除,從而提高空間操作的速度和效率?？臻g索引的性能優(yōu)劣直接影響空間數(shù)據(jù)庫(kù)和地理信息系統(tǒng)的整體性能,它是空間數(shù)據(jù)庫(kù)和地理信息系統(tǒng)的一項(xiàng)關(guān)鍵技術(shù)。空間數(shù)據(jù)庫(kù)索引的理論基礎(chǔ)空間索引空間索引是指依據(jù)空間對(duì)象空間索引結(jié)構(gòu)的特點(diǎn)1.動(dòng)態(tài)構(gòu)造2.二級(jí)/三級(jí)存儲(chǔ)管理3.支持盡量多的操作4.獨(dú)立于輸入數(shù)據(jù)及插入順序5.可增長(zhǎng)性6.時(shí)間的有效性7.空間的有效性8.并行性及可恢復(fù)性空間索引結(jié)構(gòu)的特點(diǎn)1.動(dòng)態(tài)構(gòu)造2.二級(jí)/三級(jí)存儲(chǔ)管理3.支動(dòng)態(tài)構(gòu)造在數(shù)據(jù)庫(kù)中，數(shù)據(jù)有動(dòng)態(tài)和靜態(tài)兩種，由于對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)需要有一定的操作，比如插入或刪除，因此要求索引結(jié)構(gòu)也必須能夠與之保持一致，即空間的索引結(jié)構(gòu)也應(yīng)該支持動(dòng)態(tài)的數(shù)據(jù)的插入和刪除，以便于維護(hù)數(shù)據(jù)的一致性。獨(dú)立于輸入數(shù)據(jù)及插入順序支持盡量多的操作二級(jí)/三級(jí)存儲(chǔ)管理盡管隨著技術(shù)的發(fā)展，主存的容量日益增大，但仍不能將一個(gè)完整的數(shù)據(jù)庫(kù)調(diào)入到主存中，因此索引結(jié)構(gòu)要充分考慮到二級(jí)以及三級(jí)的存儲(chǔ)管理，以提高對(duì)這中間緩存的利用率。輸入數(shù)據(jù)的順序?qū)τ行┧饕Y(jié)構(gòu)的索引效率產(chǎn)生一定的影響，有些索引結(jié)構(gòu)在不同的輸入順序下會(huì)產(chǎn)生不同的索引并且性能差異很大，因此空間索引結(jié)構(gòu)應(yīng)該支持各種高維數(shù)據(jù)，并且支持任意的插入順序，使索引結(jié)構(gòu)能夠適用于各種數(shù)據(jù)的情況。索引結(jié)構(gòu)應(yīng)支持多種操作以滿足不同數(shù)據(jù)的類型需要，在提高對(duì)某些數(shù)據(jù)處理能力的基礎(chǔ)上，不能犧牲其它的操作的處理能力，應(yīng)同時(shí)保持相應(yīng)的處理性能。

動(dòng)態(tài)構(gòu)造在數(shù)據(jù)庫(kù)中，數(shù)據(jù)有動(dòng)態(tài)和靜態(tài)兩種，由于對(duì)數(shù)據(jù)庫(kù)中的數(shù)可增長(zhǎng)性索引結(jié)構(gòu)要能夠根據(jù)數(shù)據(jù)庫(kù)大小的增長(zhǎng)而調(diào)整相應(yīng)的結(jié)構(gòu)，具有一定的自適應(yīng)性。并行性及可恢復(fù)性空間的有效性時(shí)間的有效性查找速度必須是快速的，要求查詢或者更新等操作的時(shí)間復(fù)雜度要低。索引結(jié)構(gòu)要能夠支持并行操作，以提高查詢的效率，并在發(fā)生異常時(shí)，可以較快的對(duì)建立的索引結(jié)構(gòu)進(jìn)行重建，即要有一定的可恢復(fù)性。一個(gè)索引結(jié)構(gòu)同其原始數(shù)據(jù)相比應(yīng)是比較小的，從而保證一定的空間利用率?？稍鲩L(zhǎng)性索引結(jié)構(gòu)要能夠根據(jù)數(shù)據(jù)庫(kù)大小的增長(zhǎng)而調(diào)整相應(yīng)的結(jié)構(gòu)，幾種有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)KD-樹類網(wǎng)格文件

R-樹

四叉樹幾種有代表性的空間數(shù)據(jù)索引結(jié)構(gòu)KD-樹類網(wǎng)格文件R網(wǎng)格文件網(wǎng)格文件的基本思想是根據(jù)一正交的網(wǎng)格劃分k維的數(shù)據(jù)空間。k維數(shù)據(jù)空間的網(wǎng)格由k個(gè)一維數(shù)組表示,這些數(shù)組稱為刻度。將其保存在主存?？潭鹊拿恳贿吔鐦?gòu)成k-1維的超平面。整個(gè)數(shù)據(jù)空間被所有的邊界劃分成許多k維的矩形子空間,這些矩形子空間稱為網(wǎng)格目錄,用k維的數(shù)組表示,將其保存在硬盤上。網(wǎng)格目錄的每一網(wǎng)格單元包含一外存頁(yè)的地址,這一外存頁(yè)存儲(chǔ)了該網(wǎng)格單元內(nèi)的數(shù)據(jù)目標(biāo),稱為數(shù)據(jù)頁(yè)。一數(shù)據(jù)頁(yè)允許存儲(chǔ)多個(gè)相鄰網(wǎng)格單元的目標(biāo)。網(wǎng)格文件的查找簡(jiǎn)單,查找效率較高,適用于點(diǎn)目標(biāo)的索引。網(wǎng)格文件網(wǎng)格文件的基本思想是根據(jù)一正交的網(wǎng)格劃分k維的數(shù)據(jù)空KD-樹類KD-樹是k維的二叉查找樹,是二叉查找樹在多維空間的擴(kuò)展。主要用于索