BSP樹(shù)空間索引

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

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

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

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

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

SQL Server 2008的空間索引

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

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

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

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

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

您可以通過(guò)指定非默認(rèn)的網(wǎng)格密度控制分解過(guò)程。例如，在不同級(jí)別指定不同網(wǎng)格密度對(duì)于基于索引空間的大小和空間列中的對(duì)象來(lái)優(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ù)。讀取空間對(duì)象(或?qū)嵗?的數(shù)據(jù)后，空間索引將為該對(duì)象執(zhí)行"分割過(guò)程"。分割過(guò)程通過(guò)將對(duì)象與其接觸的網(wǎng)格單元集("接觸單元")相關(guān)聯(lián)使該對(duì)象適合網(wǎng)格層次結(jié)構(gòu)。從網(wǎng)格層次結(jié)構(gòu)的第 1 級(jí)開(kāi)始，分割過(guò)程以"廣度優(yōu)先"方式對(duì)整個(gè)級(jí)別進(jìn)行處理。在可能的情況下，此過(guò)程可以連續(xù)處理所有四個(gè)級(jí)別，一次處理一個(gè)級(jí)別。

研究歷程

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

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