機構索引出處

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

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

SQL Server 2008的空間索引

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

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

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

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

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

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

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

研究歷程

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