空間索引是指依據空間對象的位置和形狀或空間對象之間的某種空間關係按一定的順序排列的一種數據結構，其中包含空間對象的概要信息，如對象的標識、外接矩形及指向空間對象實體的指針。
空間數據查詢即空間索引，是對存儲在介質上的數據位置信息的描述，是用來提高系統對數據獲取的效率，也稱為空間訪問方法(Spatial Access Method SAM)。是指依據空間對象的位置和形狀或空間對象之間的某種空間關係按一定的順序排列的一種數據結構其中包含空間對象的概要信息如對象的標識外接矩形及指向空間對象實體的指針。
作為一種輔助性的空間數據結構空間索引介於空間操作算法和空間對象之間它通過篩選作用大量與特定空間操作無關的空間對象被排除從而提高空間操作的速度和效率。
基本介紹
- 中文名：空間索引
- 外文名：spatial index
索引,空間索引,現狀,動態索引結構,空間索引類型,
索引
對一個數據集做“索引”，是為了提高對這個數據集檢索的效率。書的”目錄“就是這本書內容的”索引“，當我們拿到一本新書，想查看感興趣內容的時候，我們會先查看目錄，確定感興趣的內容會在哪些頁里，直接翻到那些頁，就OK了，而不是從第一章節開始翻，一個字一個字地找我們感興趣的內容，直到找到為止，這種檢索內容的效率也太低了，如果一本書沒有目錄，可以想像有多么不方便…指可空間在索引查找中的重要性 可見書的目錄有多重要 索引有多重要啊！
空間索引
作為一種輔助性的空間數據結構，空間索引介於空間操作算法和空間對象之間，它通過篩選作用，大量與特定空間操作無關的空間對象被排除，從而提高空間操作的速度和效率。
現狀
常見空間索引類型有BSP樹、K－D－B樹、R樹、R+樹和CELL樹，空間索引的性能的優越直接影響空間資料庫和地理信息系統的整體性能。結構較為簡單的格網型空間索引在各GIS軟體和系統中（如ArcGIS）都有著廣泛的套用。
分形（Fractal）理論，是現代數學的一個新分支。分形幾何學是一門以非規則幾何形態為研究對象的幾何學。通過對分形理論的深入研究，證明了皮亞諾曲線的一些性質，尤其對Hilbert空間填（略），為空間索引的研究提供了必要的理論知識。
空間數據（略）空間信息領域的核心研究內容之一.隨著空間信息基礎設施建設和空間數據獲取技術的快速發展,空間數據規模越來越大，對空間數據共享的要求越來越高，與此同時空間數據倉庫、空間數據挖掘等（略）系統性能提出了日益增長的需求。在依賴硬體改善資料庫系統性能越來越困難的情況下，以提高空間數據共享能力，增強空間數據的索引效率成為當前研究的熱點前沿。
基於分形理論，通過生成Hilbert曲線，將空間數據進行有效合理的劃分，並且結合當前空間索引系統中套用廣泛的R-樹空間（略）成了一種新的空間索引算法及體系，很好地解決了空間索引速度和索引精度問題，（略）分散式海量空間數據的空間索引效率。具體如下：深入研究了分形圖形的編碼理論，L系統和疊代函式系統繪製分形圖形的方法，並給出Hilbert空間填充曲線的生成方案，設計出掃描矩陣算法。
動態索引結構
1984年Guttman發表了《R-樹：一種空間查詢的動態索引結構》
SQL Server 2008的空間索引
SQL Server 2008 引入了對空間數據和空間索引的支持，“空間索引”是一種擴展索引，允許您對空間列編制索引。空間列是包含空間數據類型（如 geometry 或 geography）數據的表列。本節中的主題介紹了空間索引。
在 SQL Server 2008 中，空間索引(存儲在:sys.spatial_indexes表中)使用 B 樹構建而成，也就是說，這些索引必須按 B 樹的線性順序表示二維空間數據。因此，將數據讀入空間索引之前，SQL Server 2008 先實現對空間的分層均勻分解。索引創建過程會將空間分解成一個四級“格線層次結構”。這些級別指的是“第 1 級”（頂級）、“第 2 級”、“第 3 級”和“第 4 級”。
每個後續級別都會進一步分解其上一級，因此上一級別的每個單元都包含下一級別的整個格線。在給定級別上，所有格線沿兩個軸都有相同數目的單元 （例如 4x4 或 8x8），並且單元的大小都相同。下圖顯示了格線層次結構每個級別的右上角單元被分解成 4x4 格線的情況。事實上，所有單元都是以這種方式分解的。因此，以此為例，將一個空間分解成四個級別的 4x4 格線際上會總共產生 65,536 個第四級單元。針對空間索引進行的空間分解與應用程式數據使用的度量單位無關。
格線層次結構的單元是利用多種 Hilbert 空間填充曲線以線性方式編號的。然而，出於演示目的，這裡使用的是簡單的按行編號，而不是由 Hilbert 曲線實際產生的編號。在下圖中，幾個表示建築物的多邊形和表示街道的線已經放進了一個 4x4 的 1 級格線中。第 1 級單元的編號為 1 到 16，編號從左上角的單元開始。
沿格線軸的單元數目確定了格線的“密度”：單元數目越大，格線的密度越大。例如，8x8 格線（產生 64 個單元）的密度就大於 4x4 格線（產生 16 個單元）的密度。格線密度是以每個級別為基礎定義的。格線配置單元數目低 ：4X4 =16，中8X8 = 64，高16X16 =256，默認設定所有級別都為 中。
您可以通過指定非默認的格線密度控制分解過程。例如，在不同級別指定不同格線密度對於基於索引空間的大小和空間列中的對象來最佳化索引可能非常有 用。空間索引的格線密度顯示在 sys.spatial_index_tessellations 目錄視圖的 level_1_grid、level_2_grid、level_3_grid 和 level_4_grid 列中。
將索引空間分解成格線層次結構後，空間索引將逐行讀取空間列中的數據。讀取空間對象（或實例）的數據後，空間索引將為該對象執行“分割過程”。分割過程通過將對象與其接觸的格線單元集（“接觸單元”）相關聯使該對象適合格線層次結構。從格線層次結構的第 1 級開始，分割過程以“廣度優先”方式對整個級別進行處理。在可能的情況下，此過程可以連續處理所有四個級別，一次處理一個級別。
研究歷程
當前數據搜尋的一個關鍵問題是速度。提高速度的核心技術是空間索引。空間索引是由空間位置到空間對象的映射關係。當前的一些大型資料庫都有空間索引能力，像Oracle，DB2。空間索引技術並不單是為了提高顯示速度，顯示速度僅僅是它所要解決的一個問題。空間索引是為空間搜尋提供一種合適的數據結構，以提高搜尋速度。空間索引技術的核心是：根據搜尋條件，比如一個矩形，迅速找到與該矩形相交的所有空間對象集合。當數據量巨大，矩形框相對於全圖很小時，這個集合相對於全圖數據集大為縮小，在這個縮小的集合上再處理各種複雜的搜尋，效率就會大大提高。所謂空間索引，就是指依據空間實體的位置和形狀或空間實體之間的某種空間關係，按一定順序排列的一種數據結構，其中包含空間實體的概要信息如對象的標識、外接矩形及指向空間實體數據的指針。簡單的說，就是將空間對象按某種空間關係進行劃分，以後對空間對象的存取都基於劃分塊進行。 1 引言 空間索引是對存儲在介質上的數據位置信息的描述，用來提高系統對數據獲取的效率。空間索引的提出是由兩方面決定的：其一是由於計算機的體系結構將存貯器分為記憶體、外存 兩種，訪問這兩種存儲器一次所花費的時間一般為30~40ns，8~10ms，可以看出兩者相差十 萬倍以上，儘管有“記憶體資料庫”的說法，但絕大多數數據是存儲在外存磁碟上的，如果對磁碟上數據的位置不加以記錄和組織，每查詢一個數據項就要掃描整個數據檔案，這種訪問磁碟的代價就會嚴重影響系統的效率，因此系統的設計者必須將數據在磁碟上的位置加以記錄和組織，通過在記憶體中的一些計算來取代對磁碟漫無目的的訪問，才能提高系統的效率，尤其是GIS涉及的是各種海量的複雜數據，索引對於處理的效率是至關重要的。其二是GIS 所表現的地理數據多維性使得傳統的B樹索引並不適用，因為B樹所針對的字元、數字等傳統數據類型是在一個良序集之中，即都是在一個維度上，集合中任給兩個元素，都可以在這個維度上確定其關係只可能是大於、小於、等於三種，若對多個欄位進行索引，必須指定各個欄位的優先權形成一個組合欄位，而地理數據的多維性，在任何方向上並不存在優先權問題，因此B樹並不能對地理數據進行有效的索引，所以需要研究特殊的能適應多維特性的空間索引方式。 1984年Guttman發表了《R樹:一種空間查詢的動態索引結構》，它是一種高度平衡的樹，由中間節點和頁節點組成，實際數據對象的最小外接矩形存儲在頁節點中，中間節點通過聚集其低層節點的外接矩形形成，包含所有這些外接矩形。其後，人們在此基礎上針對不同空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是流行的空間索引。
空間索引類型
R樹
R樹是B樹向多維空間發展的另一種形式，它將空間對象按範圍劃分，每個結點都對應一個區域和一個磁碟頁，非葉結點的磁碟頁中存儲其所有子結點的區域範圍，非葉結點的所有子結點的區域都落在它的區域範圍之內；葉結點的磁碟頁中存儲其區域範圍之內的所有空間對象的外接矩形。每個結點所能擁有的子結點數目有上、下限，下限保證對磁碟空間的有效利用，上限保證每個結點對應一個磁碟頁，當插入新的結點導致某結點要求的空間大於一個磁碟頁時，該結點一分為二。R樹是一種動態索引結構，即：它的查詢可與插入或刪除同時進行，而且不需要定期地對樹結構進行重新組織。
1 R-Tree數據結構
R-Tree是一種空間索引數據結構，下面做簡要介紹：
（1）R-Tree是n 叉樹，n稱為R-Tree的扇（fan）。
（2）每個結點對應一個矩形。
（3）葉子結點上包含了小於等於n 的對象，其對應的矩為所有對象的外包矩形。
（4）非葉結點的矩形為所有子結點矩形的外包矩形。
R-Tree的定義很寬泛，同一套數據構造R-Tree，不同方可以得到差別很大的結構。什麼樣的結構比較優呢？有兩標準：
（1）位置上相鄰的結點儘量在樹中聚集為一個父結點。
（2）同一層中各兄弟結點相交部分比例儘量小。
R樹是一種用於處理多維數據的數據結構，用來訪問二維或者更高維區域對象組成的空間數據.R樹是一棵平衡樹。樹上有兩類結點：葉子結點和非葉子結點。每一個結點由若干個索引項構成。對於葉子結點，索引項形如(Index，Obj_ID)。其中，Index表示包圍空間數據對象的最小外接矩形MBR，Obj_ID標識一個空間數據對象。對於一個非葉子結點，它的索引項形如(Index，Child_Pointer)。 Child_Pointer 指向該結點的子結點。Index仍指一個矩形區域，該矩形區域包圍了子結點上所有索引項MBR的最小矩形區域。一棵R樹的示例如圖所示：
2 R-Tree算法描述
算法描述如下：
對象數為n，扇區大小定為fan。
（1）估計葉結點數k=n/fan。
（2）將所有幾何對象按照其矩形外框中心點的x值排序。
（3）將排序後的對象分組，每組大小為 *fan，最後一組可能不滿員。
（4）上述每一分組內按照幾何對象矩形外框中心點的y值排序。
（5）排序後每一分組內再分組，每組大小為fan。
（6）每一小組成為葉結點，葉子結點數為nn。
（7）N=nn，返回1。
3 R-Tree空間索引算法的研究歷程
1 R-Tree
多維索引技術的歷史可以追溯到20世紀70年代中期。就在那個時候，諸如Cell算法、四叉樹和k-d樹等各種索引技術紛紛問世，但它們的效果都不盡人意。
R+樹
在Guttman的工作的基礎上，許多R樹的變種被開發出來， Sellis等提出了R+樹，R+樹與R樹類似，主要區別在於R+樹中兄弟結點對應的空間區域無重疊，這樣劃分空間消除了R樹因允許結點間的重疊而產生的“死區域”（一個結點內不含本結點數據的空白區域），減少了無效查詢數，從而大大提高空間索引的效率，但對於插入、刪除空間對象的操作，則由於操作要保證空間區域無重疊而效率降低。同時R+樹對跨區域的空間物體的數據的存儲是有冗餘的，而且隨著資料庫中數據的增多，冗餘信息會不斷增長。Greene也提出了他的R樹的變種。
R*樹
在1990年，Beckman和Kriegel提出了最佳動態R樹的變種——R*樹。R*樹和R樹一樣允許矩形的重疊，但在構造算法R*樹不僅考慮了索引空間的“面積”，而且還考慮了索引空間的重疊。該方法對結點的插入、分裂算法進行了改進，並採用“強制重新插入”的方法使樹的結構得到最佳化。但R*樹算法仍然不能有效地降低空間的重疊程度，尤其是在數據量較大、空間維數增加時表現的更為明顯。R*樹無法處理維數高於20的情況。
QR樹
QR樹利用四叉樹將空間劃分成一些子空間，在各子空間內使用許多R樹索引，從而改良索引空間的重疊。QR樹結合了四叉樹與R樹的優勢，是二者的綜合套用。實驗證明：與R樹相比，QR樹以略大（有時甚至略小）的空間開銷代價，換取了更高的性能，且索引目標數越多，QR樹的整體性能越好。
SS樹
SS樹對R*樹進行了改進，通過以下措施提高了最鄰近查詢的性能：用最小邊界圓代替最小邊界矩形表示區域的形狀，增強了最鄰近查詢的性能，減少將近一半存儲空間；SS樹改進了R*樹的強制重插機制。當維數增加到5是，R樹及其變種中的邊界矩形的重疊將達到90%，因此在高維情況（≥5）下，其性能將變的很差，甚至不如順序掃描。
X樹
X樹是線性數組和層狀的R樹的雜合體，通過引入超級結點，大大地減少了最小邊界矩形之間的重疊，提高了查詢效率。X樹用邊界圓進行索引，邊界矩形的直徑（對角線）比邊界圓大，SS樹將點分到小直徑區域。由於區域的直徑對最鄰近查詢性能的影響較大，因此SS樹的最鄰近查詢性能優於R*樹；邊界矩形的平均容積比邊界圓小，R*樹將點分到小容積區域；由於大的容積會產生較多的覆蓋，因此邊界矩形在容積方面要優於邊界圓。SR樹既採用了最小邊界圓（MBS），也採用了最小邊界矩形（MBR），相對於SS樹，減小了區域的面積，提高了區域之間的分離性，相對於R*樹，提高了鄰近查詢的性能。
