空間索引

常見空間索引類型有BSP樹、K-D-B樹、R樹、R+樹和CELL樹，空間索引的性能的優(yōu)越直接影響空間數(shù)據(jù)庫和地理信息系統(tǒng)的整體性能。結(jié)構(gòu)較為簡單的格網(wǎng)型空間索引在各GIS軟件和系統(tǒng)中(如ArcGIS)都有著廣泛的應(yīng)用。

分形(Fractal)理論，是現(xiàn)代數(shù)學(xué)的一個新分支。分形幾何學(xué)是一門以非規(guī)則幾何形態(tài)為研究對象的幾何學(xué)。通過對分形理論的深入研究，證明了皮亞諾曲線的一些性質(zhì)，尤其對Hilbert空間填(略)，為空間索引的研究提供了必要的理論知識。

空間數(shù)據(jù)(略)空間信息領(lǐng)域的核心研究內(nèi)容之一.隨著空間信息基礎(chǔ)設(shè)施建設(shè)和空間數(shù)據(jù)獲取技術(shù)的快速發(fā)展,空間數(shù)據(jù)規(guī)模越來越大，對空間數(shù)據(jù)共享的要求越來越高，與此同時空間數(shù)據(jù)倉庫、空間數(shù)據(jù)挖掘等(略)系統(tǒng)性能提出了日益增長的需求。在依賴硬件改善數(shù)據(jù)庫系統(tǒng)性能越來越困難的情況下，以提高空間數(shù)據(jù)共享能力，增強空間數(shù)據(jù)的索引效率成為當(dāng)前研究的熱點前沿。

基于分形理論，通過生成Hilbert曲線，將空間數(shù)據(jù)進行有效合理的劃分，并且結(jié)合當(dāng)前空間索引系統(tǒng)中應(yīng)用廣泛的R-樹空間(略)成了一種新的空間索引算法及體系，很好地解決了空間索引速度和索引精度問題，(略)分布式海量空間數(shù)據(jù)的空間索引效率。具體如下:深入研究了分形圖形的編碼理論，L系統(tǒng)和迭代函數(shù)系統(tǒng)繪制分形圖形的方法，并給出Hilbert空間填充曲線的生成方案，設(shè)計出掃描矩陣算法。

R樹

R樹是B樹向多維空間發(fā)展的另一種形式，它將空間對象按范圍劃分，每個結(jié)點都對應(yīng)一個區(qū)域和一個磁盤頁，非葉結(jié)點的磁盤頁中存儲其所有子結(jié)點的區(qū)域范圍，非葉結(jié)點的所有子結(jié)點的區(qū)域都落在它的區(qū)域范圍之內(nèi);葉結(jié)點的磁盤頁中存儲其區(qū)域范圍之內(nèi)的所有空間對象的外接矩形。每個結(jié)點所能擁有的子結(jié)點數(shù)目有上、下限，下限保證對磁盤空間的有效利用，上限保證每個結(jié)點對應(yīng)一個磁盤頁，當(dāng)插入新的結(jié)點導(dǎo)致某結(jié)點要求的空間大于一個磁盤頁時，該結(jié)點一分為二。R樹是一種動態(tài)索引結(jié)構(gòu)，即:它的查詢可與插入或刪除同時進行，而且不需要定期地對樹結(jié)構(gòu)進行重新組織。

1 R-Tree數(shù)據(jù)結(jié)構(gòu)

R-Tree是一種空間索引數(shù)據(jù)結(jié)構(gòu)，下面做簡要介紹:

(1)R-Tree是n 叉樹，n稱為R-Tree的扇(fan)。

(2)每個結(jié)點對應(yīng)一個矩形。

(3)葉子結(jié)點上包含了小于等于n 的對象，其對應(yīng)的矩為所有對象的外包矩形。

(4)非葉結(jié)點的矩形為所有子結(jié)點矩形的外包矩形。

R-Tree的定義很寬泛，同一套數(shù)據(jù)構(gòu)造R-Tree，不同方可以得到差別很大的結(jié)構(gòu)。什么樣的結(jié)構(gòu)比較優(yōu)呢?有兩標(biāo)準(zhǔn):

(1)位置上相鄰的結(jié)點盡量在樹中聚集為一個父結(jié)點。

(2)同一層中各兄弟結(jié)點相交部分比例盡量小。

R樹是一種用于處理多維數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，用來訪問二維或者更高維區(qū)域?qū)ο蠼M成的空間數(shù)據(jù).R樹是一棵平衡樹。樹上有兩類結(jié)點:葉子結(jié)點和非葉子結(jié)點。每一個結(jié)點由若干個索引項構(gòu)成。對于葉子結(jié)點，索引項形如(Index，Obj_ID)。其中，Index表示包圍空間數(shù)據(jù)對象的最小外接矩形MBR，Obj_ID標(biāo)識一個空間數(shù)據(jù)對象。對于一個非葉子結(jié)點，它的索引項形如(Index，Child_Pointer)。 Child_Pointer 指向該結(jié)點的子結(jié)點。Index仍指一個矩形區(qū)域，該矩形區(qū)域包圍了子結(jié)點上所有索引項MBR的最小矩形區(qū)域。一棵R樹的示例如圖所示:

2 R-Tree算法描述

算法描述如下:

對象數(shù)為n，扇區(qū)大小定為fan。

(1)估計葉結(jié)點數(shù)k=n/fan。

(2)將所有幾何對象按照其矩形外框中心點的x值排序。

(3)將排序后的對象分組，每組大小為 *fan，最后一組可能不滿員。

(4)上述每一分組內(nèi)按照幾何對象矩形外框中心點的y值排序。

(5)排序后每一分組內(nèi)再分組，每組大小為fan。

(6)每一小組成為葉結(jié)點，葉子結(jié)點數(shù)為nn。

(7)N=nn，返回1。

3 R-Tree空間索引算法的研究歷程

1 R-Tree

多維索引技術(shù)的歷史可以追溯到20世紀(jì)70年代中期。就在那個時候，諸如Cell算法、四叉樹和k-d樹等各種索引技術(shù)紛紛問世，但它們的效果都不盡人意。

R+樹

在Guttman的工作的基礎(chǔ)上，許多R樹的變種被開發(fā)出來， Sellis等提出了R+樹，R+樹與R樹類似，主要區(qū)別在于R+樹中兄弟結(jié)點對應(yīng)的空間區(qū)域無重疊，這樣劃分空間消除了R樹因允許結(jié)點間的重疊而產(chǎn)生的"死區(qū)域"(一個結(jié)點內(nèi)不含本結(jié)點數(shù)據(jù)的空白區(qū)域)，減少了無效查詢數(shù)，從而大大提高空間索引的效率，但對于插入、刪除空間對象的操作，則由于操作要保證空間區(qū)域無重疊而效率降低。同時R+樹對跨區(qū)域的空間物體的數(shù)據(jù)的存儲是有冗余的，而且隨著數(shù)據(jù)庫中數(shù)據(jù)的增多，冗余信息會不斷增長。Greene也提出了他的R樹的變種。

R*樹

在1990年，Beckman和Kriegel提出了最佳動態(tài)R樹的變種--R*樹。R*樹和R樹一樣允許矩形的重疊，但在構(gòu)造算法R*樹不僅考慮了索引空間的"面積"，而且還考慮了索引空間的重疊。該方法對結(jié)點的插入、分裂算法進行了改進，并采用"強制重新插入"的方法使樹的結(jié)構(gòu)得到優(yōu)化。但R*樹算法仍然不能有效地降低空間的重疊程度，尤其是在數(shù)據(jù)量較大、空間維數(shù)增加時表現(xiàn)的更為明顯。R*樹無法處理維數(shù)高于20的情況。

QR樹

QR樹利用四叉樹將空間劃分成一些子空間，在各子空間內(nèi)使用許多R樹索引，從而改良索引空間的重疊。QR樹結(jié)合了四叉樹與R樹的優(yōu)勢，是二者的綜合應(yīng)用。實驗證明:與R樹相比，QR樹以略大(有時甚至略小)的空間開銷代價，換取了更高的性能，且索引目標(biāo)數(shù)越多，QR樹的整體性能越好。

SS樹

SS樹對R*樹進行了改進，通過以下措施提高了最鄰近查詢的性能:用最小邊界圓代替最小邊界矩形表示區(qū)域的形狀，增強了最鄰近查詢的性能，減少將近一半存儲空間;SS樹改進了R*樹的強制重插機制。當(dāng)維數(shù)增加到5是，R樹及其變種中的邊界矩形的重疊將達到90%，因此在高維情況(≥5)下，其性能將變的很差，甚至不如順序掃描。

X樹

X樹是線性數(shù)組和層狀的R樹的雜合體，通過引入超級結(jié)點，大大地減少了最小邊界矩形之間的重疊，提高了查詢效率。X樹用邊界圓進行索引，邊界矩形的直徑(對角線)比邊界圓大，SS樹將點分到小直徑區(qū)域。由于區(qū)域的直徑對最鄰近查詢性能的影響較大，因此SS樹的最鄰近查詢性能優(yōu)于R*樹;邊界矩形的平均容積比邊界圓小，R*樹將點分到小容積區(qū)域;由于大的容積會產(chǎn)生較多的覆蓋，因此邊界矩形在容積方面要優(yōu)于邊界圓。SR樹既采用了最小邊界圓(MBS)，也采用了最小邊界矩形(MBR)，相對于SS樹，減小了區(qū)域的面積，提高了區(qū)域之間的分離性，相對于R*樹，提高了鄰近查詢的性能。

對一個數(shù)據(jù)集做"索引"，是為了提高對這個數(shù)據(jù)集檢索的效率。書的"目錄"就是這本書內(nèi)容的"索引"，當(dāng)我們拿到一本新書，想查看感興趣內(nèi)容的時候，我們會先查看目錄，確定感興趣的內(nèi)容會在哪些頁里，直接翻到那些頁，就OK了，而不是從第一章節(jié)開始翻，一個字一個字地找我們感興趣的內(nèi)容，直到找到為止，這種檢索內(nèi)容的效率也太低了，如果一本書沒有目錄，可以想象有多么不方便…指可空間在索引查找中的重要性 可見書的目錄有多重要 索引有多重要啊!

1984年Guttman發(fā)表了《R-樹:一種空間查詢的動態(tài)索引結(jié)構(gòu)》

SQL Server 2008的空間索引

SQL Server 2008 引入了對空間數(shù)據(jù)和空間索引的支持，"空間索引"是一種擴展索引，允許您對空間列編制索引?？臻g列是包含空間數(shù)據(jù)類型(如 geometry 或 geography)數(shù)據(jù)的表列。本節(jié)中的主題介紹了空間索引。

在 SQL Server 2008 中，空間索引(存儲在:sys.spatial_indexes表中)使用 B 樹構(gòu)建而成，也就是說，這些索引必須按 B 樹的線性順序表示二維空間數(shù)據(jù)。因此，將數(shù)據(jù)讀入空間索引之前，SQL Server 2008 先實現(xiàn)對空間的分層均勻分解。索引創(chuàng)建過程會將空間分解成一個四級"網(wǎng)格層次結(jié)構(gòu)"。這些級別指的是"第 1 級"(頂級)、"第 2 級"、"第 3 級"和"第 4 級"。

每個后續(xù)級別都會進一步分解其上一級，因此上一級別的每個單元都包含下一級別的整個網(wǎng)格。在給定級別上，所有網(wǎng)格沿兩個軸都有相同數(shù)目的單元 (例如 4x4 或 8x8)，并且單元的大小都相同。下圖顯示了網(wǎng)格層次結(jié)構(gòu)每個級別的右上角單元被分解成 4x4 網(wǎng)格的情況。事實上，所有單元都是以這種方式分解的。因此，以此為例，將一個空間分解成四個級別的 4x4 網(wǎng)格際上會總共產(chǎn)生 65,536 個第四級單元。針對空間索引進行的空間分解與應(yīng)用程序數(shù)據(jù)使用的度量單位無關(guān)。

網(wǎng)格層次結(jié)構(gòu)的單元是利用多種 Hilbert 空間填充曲線以線性方式編號的。然而，出于演示目的，這里使用的是簡單的按行編號，而不是由 Hilbert 曲線實際產(chǎn)生的編號。在下圖中，幾個表示建筑物的多邊形和表示街道的線已經(jīng)放進了一個 4x4 的 1 級網(wǎng)格中。第 1 級單元的編號為 1 到 16，編號從左上角的單元開始。

沿網(wǎng)格軸的單元數(shù)目確定了網(wǎng)格的"密度":單元數(shù)目越大，網(wǎng)格的密度越大。例如，8x8 網(wǎng)格(產(chǎn)生 64 個單元)的密度就大于 4x4 網(wǎng)格(產(chǎn)生 16 個單元)的密度。網(wǎng)格密度是以每個級別為基礎(chǔ)定義的。網(wǎng)格配置單元數(shù)目低 :4X4 =16，中8X8 = 64，高16X16 =256，默認設(shè)置所有級別都為 中。

您可以通過指定非默認的網(wǎng)格密度控制分解過程。例如，在不同級別指定不同網(wǎng)格密度對于基于索引空間的大小和空間列中的對象來優(yōu)化索引可能非常有 用?？臻g索引的網(wǎng)格密度顯示在 sys.spatial_index_tessellations 目錄視圖的 level_1_grid、level_2_grid、level_3_grid 和 level_4_grid 列中。

將索引空間分解成網(wǎng)格層次結(jié)構(gòu)后，空間索引將逐行讀取空間列中的數(shù)據(jù)。讀取空間對象(或?qū)嵗?的數(shù)據(jù)后，空間索引將為該對象執(zhí)行"分割過程"。分割過程通過將對象與其接觸的網(wǎng)格單元集("接觸單元")相關(guān)聯(lián)使該對象適合網(wǎng)格層次結(jié)構(gòu)。從網(wǎng)格層次結(jié)構(gòu)的第 1 級開始，分割過程以"廣度優(yōu)先"方式對整個級別進行處理。在可能的情況下，此過程可以連續(xù)處理所有四個級別，一次處理一個級別。

研究歷程

當(dāng)前數(shù)據(jù)搜索的一個關(guān)鍵問題是速度。提高速度的核心技術(shù)是空間索引?？臻g索引是由空間位置到空間對象的映射關(guān)系。當(dāng)前的一些大型數(shù)據(jù)庫都有空間索引能力，像Oracle，DB2?？臻g索引技術(shù)并不單是為了提高顯示速度，顯示速度僅僅是它所要解決的一個問題。空間索引是為空間搜索提供一種合適的數(shù)據(jù)結(jié)構(gòu)，以提高搜索速度?？臻g索引技術(shù)的核心是:根據(jù)搜索條件，比如一個矩形，迅速找到與該矩形相交的所有空間對象集合。當(dāng)數(shù)據(jù)量巨大，矩形框相對于全圖很小時，這個集合相對于全圖數(shù)據(jù)集大為縮小，在這個縮小的集合上再處理各種復(fù)雜的搜索，效率就會大大提高。所謂空間索引，就是指依據(jù)空間實體的位置和形狀或空間實體之間的某種空間關(guān)系，按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間實體的概要信息如對象的標(biāo)識、外接矩形及指向空間實體數(shù)據(jù)的指針。簡單的說，就是將空間對象按某種空間關(guān)系進行劃分，以后對空間對象的存取都基于劃分塊進行。 1 引言 空間索引是對存儲在介質(zhì)上的數(shù)據(jù)位置信息的描述，用來提高系統(tǒng)對數(shù)據(jù)獲取的效率?？臻g索引的提出是由兩方面決定的:其一是由于計算機的體系結(jié)構(gòu)將存貯器分為內(nèi)存、外存 兩種，訪問這兩種存儲器一次所花費的時間一般為30~40ns，8~10ms，可以看出兩者相差十 萬倍以上，盡管有"內(nèi)存數(shù)據(jù)庫"的說法，但絕大多數(shù)數(shù)據(jù)是存儲在外存磁盤上的，如果對磁盤上數(shù)據(jù)的位置不加以記錄和組織，每查詢一個數(shù)據(jù)項就要掃描整個數(shù)據(jù)文件，這種訪問磁盤的代價就會嚴重影響系統(tǒng)的效率，因此系統(tǒng)的設(shè)計者必須將數(shù)據(jù)在磁盤上的位置加以記錄和組織，通過在內(nèi)存中的一些計算來取代對磁盤漫無目的的訪問，才能提高系統(tǒng)的效率，尤其是GIS涉及的是各種海量的復(fù)雜數(shù)據(jù)，索引對于處理的效率是至關(guān)重要的。其二是GIS 所表現(xiàn)的地理數(shù)據(jù)多維性使得傳統(tǒng)的B樹索引并不適用，因為B樹所針對的字符、數(shù)字等傳統(tǒng)數(shù)據(jù)類型是在一個良序集之中，即都是在一個維度上，集合中任給兩個元素，都可以在這個維度上確定其關(guān)系只可能是大于、小于、等于三種，若對多個字段進行索引，必須指定各個字段的優(yōu)先級形成一個組合字段，而地理數(shù)據(jù)的多維性，在任何方向上并不存在優(yōu)先級問題，因此B樹并不能對地理數(shù)據(jù)進行有效的索引，所以需要研究特殊的能適應(yīng)多維特性的空間索引方式。 1984年Guttman發(fā)表了《R樹:一種空間查詢的動態(tài)索引結(jié)構(gòu)》，它是一種高度平衡的樹，由中間節(jié)點和頁節(jié)點組成，實際數(shù)據(jù)對象的最小外接矩形存儲在頁節(jié)點中，中間節(jié)點通過聚集其低層節(jié)點的外接矩形形成，包含所有這些外接矩形。其后，人們在此基礎(chǔ)上針對不同空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是流行的空間索引。

索引建好后，如果表中的數(shù)據(jù)發(fā)生變化，比如增加或修改了記錄，怎么辦?由于對表所發(fā)生的任何DML語句，都不會自動修改索引，因此，必須定時同步(sync)和優(yōu)化(optimize)索引，以正確反映數(shù)據(jù)的變化。

在索引建好后，可以在該用戶下查到Oracle自動產(chǎn)生了以下幾個表:(假設(shè)索引名為myindex):

DR$myindex$I，DR$myindex$K，DR$myindex$R，DR$myindex$N

其中以I表最重要，可以查詢一下該表:

select token_text,token_count from DR$ myindex $I where rownum<=20;

查詢結(jié)果在此省略?？梢钥吹?，該表中保存的其實就是Oracle 分析你的文檔后，生成的term記錄

在這里，包括term出現(xiàn)的位置、次數(shù)、hash值等。當(dāng)文檔的內(nèi)容改變后，可以想見這個I表的內(nèi)容也應(yīng)該相應(yīng)改變，才能保證Oracle在做全文檢索時正確檢索到內(nèi)容(因為所謂全文檢索，其實核心就是查詢這個表)。那么如何維護該表的內(nèi)容，不能每次數(shù)據(jù)改變都重新建立索引，這就要用到sync 和 optimize了。

同步(sync):將新的term 保存到I表;

優(yōu)化(optimize):清除I表的垃圾，主要是將已經(jīng)被刪除的term從I表刪除。

Oracle提供了一個所謂的ctx server來做這個同步和優(yōu)化的工作，只需要在后臺運行這個進程，它會監(jiān)視數(shù)據(jù)的變化，及時進行同步。另外，也可以用以下的job來完成(該job要建在和表同一個用戶下):

create or replace procedure sync

is

begin

execute immediate

'alter index myindex rebuild online' ||

' parameters (''sync'')' ;

execute immediate

'alter index myindex rebuild online' ||

' parameters (''optimize full maxtime unlimited'')' ;

end sync;

/

Set ServerOutput on

declare

v_job number;

begin

Dbms_Job.Submit

(

job => v_job,

what => 'sync;',

next_date => sysdate,/* default */

interval => 'sysdate + 1/720' /* = 1 day / (24 hrs * 30 min) = 2 mins */

);

Dbms_Job.Run (v_job);

Dbms_Output.Put_Line ('Submitted as job # ' || to_char (v_job));

end;

/

job的SYSDATE + (1/720)是指每隔2分鐘同步一次。具體的時間間隔，可以根據(jù)自己的應(yīng)用的需要而定。