空間索引管理(數(shù)據(jù)庫(kù))

時(shí)間：2022-10-31 10:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-10-31 10:30:01 來(lái)源：信息時(shí)代

    空間索引管理 : 在數(shù)據(jù)庫(kù)中高效處理空間查詢而設(shè)計(jì)的索引結(jié)構(gòu),它的目標(biāo)是要便于空間選取和空間連接查詢。在響應(yīng)一條查詢時(shí),空間索引方法只需查找該空間中所有對(duì)象的一個(gè)關(guān)聯(lián)子集,并將其返回至查詢結(jié)果集中。
1.空間索引實(shí)現(xiàn)方法
空間索引的基本思想是按照一個(gè)或多個(gè)空間關(guān)鍵碼來(lái)管理空間對(duì)象?？臻g關(guān)鍵碼是比空間對(duì)象本身更簡(jiǎn)單的幾何對(duì)象,對(duì)于矢量結(jié)構(gòu)而言通常采用外接矩形,對(duì)于柵格結(jié)構(gòu)采用規(guī)則格網(wǎng)單元。空間索引使用一種用于查詢過(guò)程的過(guò)濾和精練策略: 首先在空間關(guān)鍵碼的基礎(chǔ)上,執(zhí)行一個(gè)過(guò)濾步驟,返回一個(gè)候選集,作為完全滿足某個(gè)謂詞的所有對(duì)象的超集;其次,在精選步驟中,對(duì)于每一個(gè)候選對(duì)象(或者在空間連接中的一對(duì)候選對(duì)象)用精確的幾何信息進(jìn)行檢查。由于使用了外接矩形,大多數(shù)空間索引結(jié)構(gòu)都被設(shè)計(jì)成可以存儲(chǔ)一組點(diǎn)(點(diǎn)值)或一組矩形(線或者區(qū)域值)。
空間索引結(jié)構(gòu)用一組存儲(chǔ)桶(bucket)(通常對(duì)應(yīng)二級(jí)存儲(chǔ)器的頁(yè)面)來(lái)組織對(duì)象。每個(gè)存儲(chǔ)桶有一個(gè)關(guān)聯(lián)的桶區(qū)域,即包含了存儲(chǔ)在桶中全部對(duì)象的一部分空間。桶區(qū)域通常是矩形的。對(duì)于點(diǎn)數(shù)據(jù)結(jié)構(gòu),這些區(qū)域通常是不相交的,它們分割空間使每個(gè)點(diǎn)正好屬于一個(gè)存儲(chǔ)桶。對(duì)于一些矩形數(shù)據(jù)結(jié)構(gòu),桶區(qū)域可能是交疊的。
提供空間索引的基本方法有兩種:
(1)在系統(tǒng)中加入為空間屬性專門(mén)擴(kuò)展的索引數(shù)據(jù)結(jié)構(gòu),提供如同B-樹(shù)之于線性屬性的功能。
(2)使用空間填充曲線(如Z-序、Hilbert曲線)將空間映射到一維,以便存儲(chǔ)在標(biāo)準(zhǔn)的一維索引中,例如B樹(shù)。
除了空間選取,空間索引還支持其他的操作,例如,空間連接、查找最符合待查詢值的對(duì)象等。
2. 空間索引結(jié)構(gòu)
常用的空間索引結(jié)構(gòu)有聚簇索引(z-序、Hilbert曲線)、格網(wǎng)文件、R-樹(shù)等。
(1)空間聚簇索引: 在二級(jí)存儲(chǔ)器中,使空間上鄰近的和查詢上有關(guān)聯(lián)性的對(duì)象在物理上存儲(chǔ)在一起,稱為空間聚簇索引。在空間數(shù)據(jù)庫(kù)中采用聚簇索引結(jié)構(gòu)來(lái)存儲(chǔ)空間數(shù)據(jù)能夠減少I/O代價(jià)。聚簇的目的就是降低一般大查詢的尋道和等待的響應(yīng)時(shí)間。空間數(shù)據(jù)庫(kù)中有三種用于提供有效查詢處理的聚簇存儲(chǔ)結(jié)構(gòu): ①內(nèi)部聚簇: 一個(gè)對(duì)象的全部數(shù)據(jù)都存放在同一個(gè)磁盤(pán)頁(yè)面中,這里假設(shè)它比頁(yè)面的空閑空間小; 否則,這個(gè)對(duì)象就要存儲(chǔ)在多個(gè)物理上連續(xù)的頁(yè)面中。這種情況下,對(duì)象占用的頁(yè)面至多比存儲(chǔ)該對(duì)象所需最少頁(yè)面多一個(gè)頁(yè)面。②本地聚簇: 一些空間對(duì)象(或者近似值)被分組到同一頁(yè)面,這種分組可以依照數(shù)據(jù)空間中對(duì)象的位置(或近似)來(lái)施行。③全局聚簇: 與本地聚簇相反,一組空間鄰接的對(duì)象并不存儲(chǔ)在一個(gè)而是多個(gè)物理上鄰接的頁(yè)面中,這些頁(yè)面可以由單條讀命令訪問(wèn)。
由于空間數(shù)據(jù)所處的多維空間中沒(méi)有天然的順序,而存儲(chǔ)磁盤(pán)是邏輯一維的設(shè)備,因此,空間聚集索引技術(shù)需要一個(gè)從高維空間向一維空間的映射。該映射是距離不變的,使空間上鄰近的元素映射在直線上接近的點(diǎn),而且一一對(duì)應(yīng),即空間上的任意兩個(gè)點(diǎn)不會(huì)映射到直線上同一個(gè)點(diǎn)。
空間填充(space-filling)曲線的方法是利用一個(gè)線性順序來(lái)填充空間,可以獲得從一端到另一端的曲線。主要包括Z序(Z-order)、格雷碼(Gray code)和Hilbert曲線。
(2)格網(wǎng)文件: 格網(wǎng)文件是采用多屬性索引技術(shù)來(lái)分割n維空間的索引方法。從局部上來(lái)看,它采用了固定格網(wǎng)方法。固定格網(wǎng)是訪問(wèn)多維點(diǎn)的最簡(jiǎn)單的結(jié)構(gòu)(例如經(jīng)緯網(wǎng))。固定格網(wǎng)方法將n維空間劃分成同等大小的存儲(chǔ)桶,其數(shù)據(jù)結(jié)構(gòu)是一個(gè)n維數(shù)組。位于一個(gè)單元中的點(diǎn)可以存儲(chǔ)在一個(gè)動(dòng)態(tài)結(jié)構(gòu)中(例如鏈表)來(lái)處理溢出。這種結(jié)構(gòu)對(duì)于靜態(tài)一致分布的數(shù)據(jù)(例如衛(wèi)星影像)很有用。然而,固定格網(wǎng)結(jié)構(gòu)是定死的,它的目錄稀疏而巨大。
格網(wǎng)文件達(dá)到了更好的靈活性和性能。它對(duì)于精確匹配和部分匹配提取都有較好的I/O性能。使用格網(wǎng)文件的目標(biāo)就是為了實(shí)現(xiàn)二次磁盤(pán)訪問(wèn)原則: 一次是訪問(wèn)獲得目錄項(xiàng),另一次是得到實(shí)際存儲(chǔ)桶以獲取實(shí)際記錄。格網(wǎng)文件有兩部分: 第一部分包括一個(gè)n維格網(wǎng)目錄,目錄中每一項(xiàng)指向一個(gè)數(shù)據(jù)存儲(chǔ)桶;第二部分是線性增長(zhǎng)的一維數(shù)組結(jié)構(gòu),這個(gè)數(shù)組用來(lái)標(biāo)識(shí)格網(wǎng)目錄的索引,該索引引用了包含對(duì)象(記錄)的塊或存儲(chǔ)桶。
格網(wǎng)文件的查詢時(shí)間很短,對(duì)于精確匹配查詢,只作一次到目錄的磁盤(pán)訪問(wèn)和一次數(shù)據(jù)訪問(wèn)。然而,格網(wǎng)文件本質(zhì)上會(huì)造成目錄非常松散,導(dǎo)致主存緩沖區(qū)和二級(jí)存儲(chǔ)器的浪費(fèi)。例如,超立方體可能只有非常少或沒(méi)有記錄,鄰近目錄項(xiàng)可能指向同一個(gè)數(shù)據(jù)塊。這就意味著,對(duì)于局部匹配和范圍查找,需要掃描很多只有少量數(shù)據(jù)塊的目錄項(xiàng)。
(3) R-樹(shù): R-樹(shù)是用于索引空間對(duì)象的高度平衡樹(shù),是B-樹(shù)在k維上的自然擴(kuò)展。R-樹(shù)中用對(duì)象的最小外接矩形來(lái)表示空間對(duì)象。由于R-樹(shù)采用的是數(shù)據(jù)驅(qū)動(dòng)的方法,因此不會(huì)因?yàn)榭臻g對(duì)象的分布稀疏而造成存儲(chǔ)浪費(fèi)。
R-樹(shù)的結(jié)構(gòu)與特性:①每個(gè)葉結(jié)點(diǎn)包含m至M條索引記錄(其中m≤M/2),除非它是根結(jié)點(diǎn)。②一個(gè)葉結(jié)點(diǎn)上的每條索引記錄是(I,元組標(biāo)識(shí)符),I是最小外接矩形,在空間上包含了所指元組表達(dá)的k維數(shù)據(jù)對(duì)象。③每個(gè)非葉結(jié)點(diǎn)都有m至M個(gè)子結(jié)點(diǎn),除非它是根結(jié)點(diǎn)。④對(duì)于非葉結(jié)點(diǎn)中的每個(gè)條目(I,子結(jié)點(diǎn)指針),I是空間包含其子結(jié)點(diǎn)中矩形的最小外接矩形。⑤根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn),除非它是葉結(jié)點(diǎn)。⑥所有葉出現(xiàn)在同一層。⑦所有最小外接矩形的邊與一個(gè)全局坐標(biāo)系的軸平行。
R-樹(shù)的存儲(chǔ)結(jié)構(gòu): ①R-樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)磁盤(pán)頁(yè)面。一個(gè)葉結(jié)點(diǎn)包括一組項(xiàng),格式為(I,元組標(biāo)識(shí)符),其中I為最小外接矩形,元組標(biāo)識(shí)符是數(shù)據(jù)庫(kù)中對(duì)應(yīng)最小外接矩形的存儲(chǔ)對(duì)象的元組唯一標(biāo)識(shí)。用I=(I₀,…,I_k-1)表示I,其中I_i在沿方向i的一個(gè)閉合區(qū)間[a,b]上。非葉結(jié)點(diǎn)由多個(gè)格式為(I,子結(jié)點(diǎn)指針)的項(xiàng)組成,其中I是子結(jié)點(diǎn)指針指向的更低層結(jié)點(diǎn)項(xiàng)中所有矩形的最小外接矩形。樹(shù)中每個(gè)結(jié)點(diǎn)最多有M個(gè)條目,最少有m個(gè)(m≤M/2),除非它是根。根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn),除非它是葉。②由于R-樹(shù)是一棵平衡樹(shù),在對(duì)應(yīng)插入對(duì)象的葉結(jié)點(diǎn)已滿的情況下,插入操作可能會(huì)導(dǎo)致結(jié)點(diǎn)向根部分裂。葉面分裂算法非常復(fù)雜。不過(guò),R-樹(shù)已經(jīng)在許多商用數(shù)據(jù)庫(kù)系統(tǒng)中實(shí)現(xiàn)了,它們支持通用的存取方法和合理大小(1024字節(jié))的磁盤(pán)頁(yè)面。R-樹(shù)的最大層數(shù)是log_mN-1,其中N是樹(shù)中條目的總數(shù)。在最壞情況下,除根之外,結(jié)點(diǎn)空間的利用率是m/M。如果m大于3或4,樹(shù)將水平擴(kuò)展,這樣,幾乎所有的空間都用于存儲(chǔ)索引記錄的葉結(jié)點(diǎn)。m值增大就意味著R-樹(shù)的深度相對(duì)變淺。R-樹(shù)是一個(gè)動(dòng)態(tài)結(jié)構(gòu),還允許存儲(chǔ)不同類型的對(duì)象。
基于R-樹(shù)的查詢與性能: 點(diǎn)和范圍查詢?cè)赗-樹(shù)中可以用自頂向下遞歸的方法處理。查詢點(diǎn)(或區(qū)域)首先與根結(jié)點(diǎn)中每個(gè)項(xiàng)(I,子結(jié)點(diǎn)指針)進(jìn)行比較。如果查詢點(diǎn)在I中(或查詢區(qū)域與其交疊),則查找算法就遞歸地應(yīng)用在子結(jié)點(diǎn)指針?biāo)赶虻腞-樹(shù)結(jié)點(diǎn)。該過(guò)程直至R-樹(shù)的葉結(jié)點(diǎn)為止。使用葉結(jié)點(diǎn)中選出的項(xiàng)來(lái)得到與選中空間主碼關(guān)聯(lián)的記錄。
R-樹(shù)的查詢性能取決于兩個(gè)因素:覆蓋和交疊。樹(shù)中一層的覆蓋是指這一層所有結(jié)點(diǎn)的最小外接矩形所覆蓋的全部區(qū)域。覆蓋是對(duì)靜態(tài)空間的間接衡量,或者是樹(shù)覆蓋的空白區(qū)。樹(shù)中一層的交疊是指被不止一個(gè)該層結(jié)點(diǎn)關(guān)聯(lián)的多邊形所覆蓋的全部區(qū)域。交疊使得查找一個(gè)對(duì)象需要訪問(wèn)樹(shù)的多個(gè)結(jié)點(diǎn)。R-樹(shù)的這個(gè)問(wèn)題意味著,即使已經(jīng)盡量減少了交疊,查詢操作的最差性能仍然是無(wú)法估計(jì)的。若要得到一個(gè)高效的R-樹(shù),覆蓋和交疊都應(yīng)該最小,而且交疊的最小化要比覆蓋更具有決定性。由此導(dǎo)致了其他基于R-樹(shù)的變種和備選結(jié)構(gòu)。例如,packed R-樹(shù)、R*-樹(shù)和R⁺-樹(shù)。
R⁺-樹(shù)的結(jié)構(gòu): 在R⁺-樹(shù)中,空間對(duì)象的最小外接矩形可能被樹(shù)中非葉結(jié)點(diǎn)的矩形分割。R⁺-樹(shù)有如下特點(diǎn):①對(duì)于中間結(jié)點(diǎn)的每個(gè)項(xiàng)(I,child-pointer),由child-pointer指向結(jié)點(diǎn)為根的子樹(shù)包括一個(gè)矩形R,當(dāng)且僅當(dāng)R被I覆蓋。唯一的例外是當(dāng)I是一個(gè)葉結(jié)點(diǎn)的矩形。在這種情況下,R與I只交疊。②對(duì)中間結(jié)點(diǎn)的任何兩個(gè)項(xiàng)(I₁,child-pointer1)和(I₂,child-pointer2),I₁與I₂之間的交疊是零。③根至少有兩個(gè)子結(jié)點(diǎn),除非它是葉結(jié)點(diǎn)。④所有的葉都在同一層。⑤中間結(jié)點(diǎn)的所有矩形都是不相交的,因而中間結(jié)點(diǎn)項(xiàng)之間零交疊。如果一個(gè)對(duì)象的最小外接矩形被兩個(gè)或多個(gè)R⁺樹(shù)高層結(jié)點(diǎn)的矩形分割,與這些非葉結(jié)點(diǎn)中矩形相對(duì)應(yīng)的每個(gè)項(xiàng)都有一個(gè)派生的葉結(jié)點(diǎn)指向這個(gè)對(duì)象。這樣,樹(shù)的高度增加(雖然只是輕微的),但查詢操作的性能會(huì)有很大提高。
對(duì)于高度動(dòng)態(tài)的數(shù)據(jù),R⁺-樹(shù)比packed R-樹(shù)更好,因?yàn)樗_保了持續(xù)的高效。同R-樹(shù)相反,由于R⁺-樹(shù)的第一個(gè)特點(diǎn),它可能會(huì)需要向下分裂。因此對(duì)分裂結(jié)點(diǎn)的選擇很重要。