一種空間索引結構的新的空間檢索結構

1用人不確定的索引結構目前，許多應用頻繁涵蓋了大數據集和高維數據對象，如數據結構、圖形數據庫、3d、gis、機器人、計算機視覺等。此外，許多應用程序還需要動態更新例如插入和刪除等。怎樣組織/索引這類數據成為一個富有挑戰性的問題。一種空間索引結構要盡量追求數據存儲、數據搜索(查詢、檢索)、數據更新等方面的效率。這三個方面與應用相關,不同的應用要求各有差異,但要同時做到這三方面卻非常困難。近年來,國內外學者提出了許多不同的空間索引方法:包括R-樹、R+-樹、R*-樹、區域四叉樹等,但這些索引方法各有優缺點。例如:R-樹采用最小約束矩形來遞歸分解索引空間,其存儲效率相對較高,但由于矩形區域之間可能產生重疊,因此區域搜索可能需要沿多條路徑進行,從而降低了搜索效率。R+-樹雖然避免了矩形區域的重疊,但它可能需要在不同的結點中存儲同一個矩形的標識,從而降低其存儲效率。R*-樹與R-樹有類似缺點。本文介紹一種新的空間數據庫的索引結構——QR*-樹。QR*-樹是一種基于四叉樹和R*-樹的空間索引結構,它結合了四叉樹和R*-樹的優點,可以將搜索范圍限定在索引空間的某一部分,然后再用類似R*-樹的搜索算法來進行查詢,因此提高了數據的查詢效率,尤其是在數據量非常巨大的應用領域中。2相關工作空間索引結構的種類很多,但大多數空間索引結構可以歸為兩大類:以區域規則劃分為基礎的索引結構;基于R-樹的索引結構。2.1圖像分解和組織區域四叉樹將索引空間遞歸分解成四個相等大小的象限(子象限),直到子象限完全被圖像充滿或完全沒有圖像為止。這樣的塊即為葉結點。非葉結點只有部分被圖像覆蓋,因此要進一步進行分解。區域四叉樹的建立是通過將子象限按某種空間填充曲線排序后的順序插入到樹中來實現的。MX四叉樹與區域四叉樹的組織方式類似,區別是葉子結點為黑結點或空結點分別表示數據空間某一位置空間點的存在與否。MX四叉樹的高度是平衡的、空間劃分是等分的,因此結構簡單。但其插入(刪除)一個點可能導致樹的深度增加(減少)一層或多層,且所有的葉子結點都必須重新定位。另外,MX四叉樹的高度往往很大,這無疑也會影響其搜索效率。2.2r-樹的最小約束盒自從Guttman于1984年提出了R-樹的概念之后,許多學者對這種索引結構產生了興趣。到目前為止,相繼提出了許多基于R-樹的結構,如R+-樹、R*-樹、X-樹和SR-樹等。基于R-樹的索引結構的基本思想都是一樣的:每個非葉結點有一個與之相關的最小約束盒MBB(MinimumBoundBox),所有在這個MBB中的對象存儲在以MBB為根結點的子樹中。最小約束盒的大小依賴于對象的分布和對象的大小。基于R-樹的索引結構的平均高度為O(logN)(N為數據集的大小)。R-樹是一種類似于B+-樹的結構。R-樹的主要缺陷是結點的重疊。如果待查詢的區域包含了幾個兄弟結點的重疊區域,則以這些結點為根的子樹都將被搜索,這會降低搜索效率,也很難對搜索效率進行預測。隨后的結構改善了這個問題。R+-樹是R-樹和K-D-B-樹結合的產物,它將對象標識進行復制以使結點不產生重疊,因此在搜索中避免了點查詢在R-樹中的多路徑搜索。R*-樹則盡量減小結點間的重疊面積,它對上溢結點進行刪除,并強制重插入該結點中的所有對象。X-樹在偵測到所有可能的分裂都會造成大的重疊時,通過不分裂結點的策略來達到降低重疊的目的。這種不分裂的結點稱為超結點(Supernode),但是這種方法也帶來另一個問題,即一個超結點的孩子個數是不固定的,且有可能超結點會很大(尤其是在維度很高的情況下),這會使得搜索超結點的時間變長。SR-樹的最小約束盒是最小約束矩形和最小約束球相交的區域,這種結構可降低結點的重疊是因為:在高維空間中超矩形的平均體積要小于超球的體積,而超矩形的平均直徑卻要大于超球。然而SR-樹的插入和刪除操作代價很高且存儲需求也相應增加了。3r#-樹未發現沒有取得追蹤路徑在R*-樹中,中間結點的索引空間重疊是不可能避免的,當進行查找時往往會產生多條查找路徑,且其中有些是失敗查找路徑,這使得R*-樹的查找性能受到影響,尤其是當失敗查找路徑較長時,對查找性能影響很大。如果能設計出一種索引結構,能將R*-樹的查找限定在空間的某一部分來進行,則會大大提高查找性能。為此本文提出了一種新的空間索引結構——QR*-樹。3.1quamdearQR*-樹是結合Quadtree和R-樹而提出的一種空間索引結構。設d>0,n=∑l=0d?1(2k)l?(kd>0,n=∑l=0d-1(2k)l?(k為空間的維數,d為Quadtree深度),則QR*-樹由一棵深度為d的四叉樹Qt和n棵R*-樹組成。Qt共有n個結點,依次為:Qt0,Qt1,…,Qtn-1。Qt將整個數據空間S劃分成n個d級子空間,依次記為:S0,S1,…,Sn-1(其中S0=S)。每一級的所有子空間兩兩不相交,且一起構成整個索引空間S。n棵R*-樹:Rt0,Rt1,…,Rtn-1分別與Qt的n個結點及Qt劃分的n個子空間相關聯。Si與Rti相關聯,即Rti用于索引屬于Si的空間目標。一空間目標P屬于Si是指:(a)P完全落于Si或Si完全包圍P;(b)Si是所有完全包圍P的子空間中的最小者。圖1是二維空間QR*-樹的一個例子。在該例中,QR*-樹由一棵深度為2的Quadtree樹和5棵R*-樹組成。整個空間被劃分為2級共5個子空間:S0,S1,S2,S3,S4(S0=S1∪S2∪S3∪S4),Rt0,Rt1,Rt2,Rt3,Rt4這5棵R*-樹分別與之相關聯。完全包圍r1的最小子空間為S1,因此r1被分配給Rt1;完全包圍r2的最小子空間了S0,因此r2被分配給Rt0。因此QR*-樹的結構由Quadtree和R*-樹的結構組成。R*-樹的結點結構如下所示:葉子結點:(COUNT,LEVEL,<OI1,MBR1>,<OI2,MBR2>,…,<OIm,MBRm>);非葉結點:(COUNT,LEVEL,<CP1,MBR1>,<CP2,MBR2>,…,<CPm,MBRm>)。其中,葉子結點的OIi為空間目標的標識(整型),MBRi為該目標在k維空間中的最小約束“矩形”;非葉結點的CPi為指向子樹根結點的指針,MBRi代表其子樹索引空間。Quadtree采用線性的存儲結構,其結點結構可描述為:<S,Rt>,其中S為該結點關聯的子空間,Rt為與S關聯的R*-樹。由于S可以根據Quadtree結點的層次及結點在該層的順序確定,因此實現時可以不需顯式存儲;為了減少查詢過程中提取R*-樹根結點的次數,可以在Quadtree結點中增加一項MBR,存儲其對應的R*-樹的索引空間(如果查詢目標不在MBR之內,則不需要提取對應R*-樹結點,因此可以減少磁盤頁的訪問次數)。3.2稀疏樹操作3.2.1以最小約束子空間為依托的必要性插入一個數據矩形,必須首先確定其屬于的最小子空間及其關聯結點,然后再將其插入到對應的R*-樹中。例如:在圖1中,插入數據矩形r7,首先求出最小約束子空間為S2,然后將其插入到Rt2中;插入數據矩形r2,首先求出最小約束子空間為S0,然后將其插入到Rt0中。插入算法Insert(N,P)(N為QR*-樹的根結點,P為待插入數據矩形的最小約束矩形)的形式可形式化描述如下:(1)如果N是葉結點,則調用R*-樹的插入算法將其插入;(2)若N是非葉結點,則在N的所有孩子結點對應的子空間中查找到完全包含P的子空間P1,然后轉(1)在N的子樹中進行插入;如果找不到完全包含P的子空間,則在根結點中插入P。3.2.2最小約束子空間刪除一個數據矩形,必須首先確定其屬于的最小子空間及其關聯結點,然后再將其從對應的R*-樹中刪除該數據矩形。例如:在圖1中,要刪除數據矩形r4,首先求出其最小約束子空間為S4,然后從Rt4中刪除之;要刪除數據矩形r9,首先求出最小約束子空間為S0,然后從Rt0中刪除它。刪除算法Delete(N,P)(N為QR*-樹的根結點,P為待刪除數據矩形的最小約束矩形)的形式可形式化描述如下:(1)如果N是葉結點,則調用R*-樹的刪除算法將其刪除;(2)若N是非葉結點,則N的所有孩子結點對應的子空間中查找到完全包含P的子空間P1,再轉(1)在N的子樹中進行刪除;如果找不到完全包含P的子空間,則將P從根結點中刪除。3.2.3r#-樹的調整與篩查給定查找矩形區域QR,查找所有與QR重疊的空間目標或完全落入QR的空間目標,必須對所有與QR相交的子空間所關聯的R*-樹進行查找操作。也就是說,從Quadtree的根結點開始,如果根結點關聯的子空間與QR與對應R*-樹的索引空間相交,則須在該R*-樹中進行查找操作。然后,對于每一子結點,比較其關聯子空間是否與QR相交,如果不相交,則該結點及其子樹截斷,不用繼續往下查找;如果相交,且與對應R*-樹的索引空間相交,則在對應的R*-樹中進行查找操作。接下來繼續比較下一級的子結點……例如在圖1中,查找所有與QR重疊的數據矩形,過程如下:(1)QR與根結點Q0關聯子空間S0相交,且與Rt0的索引空間相交,因此在Rt0中查找,返回滿足查找要求的數據矩形r9;(2)QR與S1、S2、S3都不相交,不用繼續比較;(3)QR與Q4關聯子空間S4相交,且與Rt4的索引空間相交,因此在Rt4中查找,返回滿足查找要求的數據矩形r4;查找算法Search(N,W)(N為QR*-樹的根結點,W為給定的查詢矩形區域)的形式化描述如下:(1)S:=與N相關聯的子空間;(2)如果S不與W重疊,返回;(3)如果N.MBR與W重疊,則調用R*-樹的查找算法RS_Search(N.PR,W);(4)在N的所有孩子結點中調用Search(N.child,W)。由于所有空間目標的索引信息都存儲在R*-樹中,因此QR*-樹的查找最終都要歸結于R*-樹的查找,對Quadtree結點的訪問只是為了確定其對應R*-樹是否可能包含要查找的目標。4quamdear的存儲開裂QR*-樹的算法在Windows2000系統下實現,CPU為賽揚IV1.7GHz,內存128MB。其它參數設置為:磁盤頁大小1024Bytes,R*-樹結點最小空間利用率為50%。圖2給出了二維隨機數據下的實驗結果曲線圖(包括空間開銷曲線圖、插入性能曲線圖、刪除性能曲線圖和查找性能曲線圖)。從實驗結果可以看出:(1)總體上,QR*-樹的存儲空間開銷與其Quadtree的深度成正比,且比一般R*-樹要大。但在有些情況下,R*-樹的存儲開銷要比Quadtree深度較大的QR*-樹大,這主要與空間目標的數量及分布有關。值得注意的是,索引目標數量越多,QR*-樹與R*-樹的存儲開銷越接近。(2)就插入、刪除、查找性能而言,QR*-樹總是要優于R*-樹。值得一提的是,QR*-樹的查找性能要遠勝過R*-樹,且在一定范圍內,Quadtree深度越大,QR*-樹的查找性能越好。需要注意的是,索引目標數量越多,QR*-樹的插入、刪除,特別是查找性能越優于R*-樹。(3)盡管QR*-樹的存儲空間開銷往往要略大些,但只要選擇合適的Quadtree深度,可以在增加較小的存儲空間的前提下,換取更高的查找性能。例如:在圖2中,當索引目標數大于100000時,深度為3的QR*-樹的存儲空間開銷比R*-樹略高,但查找性能的提高卻異常顯著。也就是說,索引目標數越多,數據量越大,QR*-樹的整體優勢較之于R*-樹越明顯,這一點對于大型的空間數據庫系統來說,具有一定的實用價值