機構(gòu)索引定義

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

網(wǎng)格層次結(jié)構(gòu)的單元是利用多種 Hilbert 空間填充曲線以線性方式編號的。然而，出于演示目的，這里使用的是簡單的按行編號，而不是由 Hilbert 曲線實際產(chǎn)生的編號。在下圖中，幾個表示建筑物的多邊形和表示街道的線已經(jīng)放進(jìn)了一個 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，默認(rèn)設(shè)置所有級別都為 中。

您可以通過指定非默認(rèn)的網(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)先"方式對整個級別進(jìn)行處理。在可能的情況下，此過程可以連續(xù)處理所有四個級別，一次處理一個級別。

研究歷程

當(dāng)前數(shù)據(jù)搜索的一個關(guān)鍵問題是速度。提高速度的核心技術(shù)是空間索引?？臻g索引是由空間位置到空間對象的映射關(guān)系。當(dāng)前的一些大型數(shù)據(jù)庫都有空間索引能力，像Oracle，DB2?？臻g索引技術(shù)并不單是為了提高顯示速度，顯示速度僅僅是它所要解決的一個問題?？臻g索引是為空間搜索提供一種合適的數(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)系進(jìn)行劃分，以后對空間對象的存取都基于劃分塊進(jì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ù)文件，這種訪問磁盤的代價就會嚴(yán)重影響系統(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)系只可能是大于、小于、等于三種，若對多個字段進(jìn)行索引，必須指定各個字段的優(yōu)先級形成一個組合字段，而地理數(shù)據(jù)的多維性，在任何方向上并不存在優(yōu)先級問題，因此B樹并不能對地理數(shù)據(jù)進(jìn)行有效的索引，所以需要研究特殊的能適應(yīng)多維特性的空間索引方式。 1984年Guttman發(fā)表了《R樹:一種空間查詢的動態(tài)索引結(jié)構(gòu)》，它是一種高度平衡的樹，由中間節(jié)點和頁節(jié)點組成，實際數(shù)據(jù)對象的最小外接矩形存儲在頁節(jié)點中，中間節(jié)點通過聚集其低層節(jié)點的外接矩形形成，包含所有這些外接矩形。其后，人們在此基礎(chǔ)上針對不同空間運算提出了不同改進(jìn)，才形成了一個繁榮的索引樹族，是流行的空間索引。