空間索引(Spatial Index)

空間資料型態是用 .NET 所撰寫,提供豐富功能的類別,則空間索引則是該資料型態進資料庫的重要考量。以下節錄 SQL Server 2008 對空間索引的說明:ms-help://MS.SQLCC.v10/MS.SQLSVR.v10.en/s10de_1devconc/html/16a32f47-961e-4cba-b60c-11303acee1ab.htm (強迫自己好好讀一遍微笑 )

格階層(Grid Hierarchy)

在 SQL Server 2008 空間索引依然採用 B-Tree 結構,這代表 2 維的的空間資料要以線性的 B-Tree 來表現。因此 SQL Server 將空間資料以階層(level)的方式解構。例如先以 Grid 結構均分 16 格,每格再切分 16 格

image

如圖 Grid 階層經四層切割後,是 16 的四次方,總 65536 格。

Grid 階層中,所有的格子(cell)透過型變(variation of)過的 Hibert space-filling curve 來線性編號。但為了簡化說明,此處改以列(row-wise)為主的順序編號,從左上方開始編。在圖形中,以多邊形代表建築物,而線條代表道路,此為 4*4 階層 1 的圖示:

image

格密度(Grid Density)

軸上所劃分的格子數定義了格密度,數量越大,格密度越大,而 T-SQL 的 CREATE SPATIAL INDEX 語法的 GRIDS 子句可以讓你一各層定義不同的格密度。其關鍵字意義如下表:

關鍵字

格設定

格子(cell)的數量

Low

4*4

16

Medium

8*8

64

High

16*16

256

若未透過 GRIDS 子句指定格密度,預設為 Medium

語法範例如下:

CREATE SPATIAL INDEX SIndx_SpatialTable_geography_col3
   ON SpatialTable2(object)
   WITH ( GRIDS = ( LEVEL_3 = HIGH, LEVEL_2 = HIGH ) );

棋盤(tessellation)

當切割要建索引的空間成格階層後,就執行棋盤程序(tessellation process),將空間資料套入格階層,從第一層開始執行 breadth first,找空間物件有碰到哪些格子(touched cells),逐層往下做,一次一層。棋盤程序將物件所碰觸的格子記錄進空間索引,藉由這些記錄下來的格子,透過空間索引可以比較兩個空間物件的關係。

棋盤規則(Tessellation Rules)

為了局限紀錄空間物件的被碰觸格子(touched cell)之數量,棋盤程序使用了如下的棋盤規則,以決定棋盤程序的深度(depth),和索引要記錄哪些被碰觸格子:

  • 覆蓋(covering)規則:如果空間物件完整覆蓋某個格子,則該格子會被記錄下來,且不再進行進一步的棋盤程序。如圖中第一層的第 15 格,在第二層的完整覆蓋第 11 格。覆蓋規則將簡化棋盤程序,並減少空間索引紀錄的資料量。

image

  • Cell-per-object 規則:強制每個物件可使用的格子最大數量。除了階層 1 外,Cell-per-object 規則將會控制每個物件可以記錄的資訊量。在建立索引時,可以透過 CELLS_PER_OBJECT = n 子句來定義,預設是 16,以取得容量和精確度的平衡,其值域為 1 – 8192。T-SQL 語法範例如下:

    CREATE SPATIAL INDEX SIndx_SpatialTable_geography_col2
       ON SpatialTable2(object)
       USING GEOGRAPHY_GRID
       WITH (
        GRIDS = (MEDIUM, LOW, MEDIUM, HIGH ),
        CELLS_PER_OBJECT = 64,
        PAD_INDEX  = ON );

    由於第 1 層可以不接受限制,所以當第 1 層的數量達到或超過限制時,棋盤程序就會停止,而不再做下一階層的掃描。

    由於格子的數量要小於 CELLS_PER_OBJECT 的設定,所以當執行某個格子的棋盤程序後,其記錄的子格子數量將會超過限制,則該程序就會放棄,僅記錄父格子。以上圖為例,如 CELLS_PER_OBJECT 設定為 9,則於第一層紀錄 15 後,針對格子 15 進行棋盤程序,當要進入再下一層時,需要 9 個格子來記錄,超過總數量,因此放棄下一層,而在索引中僅記錄格子 15。

     

  • deepest-cell 規則:每一個低階的格子隸屬於高階的格子,例如 4.4.10.13 隸屬 4.4.10,4.4.10 隸屬 4.4,4.4 隸屬 4。由於 Query Processor 可以理解格子的階層關係,因此索引中只需要記載最下層的格子,以減少須存放的資訊。

image

以上圖為例,索引的 CELLS_PER_OBJECT 選項採用了預設的 16,而記錄物件所花的格子並未超過這個數量,因此可進行棋盤程序到最下一層,套用 deepest-cell 規則後,僅需要記載 12 個階層四的格子:4.4.10.13-15 、 4.4.14.1-3、 4.4.14.5-7、 4.4.14.9-11

Bounding Box

幾何資料(geometric)可以定義無限大空間,但 SQL Server 2008 的空間索引需要有限空間(finite space),為了解構(decomposition)而定義一個有限空間,geometry grid tessellation scheme 需要一個長方形的 bounding box;以座標的右上和左下點 (x-min,y-min) 和 (x-max,y-max) 來定義。

 image

語法範例如下:
CREATE SPATIAL INDEX SIndx_SpatialTable_geometry_col1
   ON SpatialTable(geometry_col)
   WITH ( BOUNDING_BOX = ( 0, 0, 500, 200 ) );

建立了空間索引後,以下的 geometry 方法可以較有效率地處理集合導向資料:

  • geometry1.STContains( geometry2 ) = 1
  • geometry1.STDistance( geometry2 ) < number
  • geometry1.STDistance( geometry2 ) <= number
  • geometry1.STEquals( geometry2 ) = 1
  • geometry1.STIntersects( geometry2 ) = 1
  • geometry1.STOverlaps(geometry2) = 1
  • geometry1.STTouches( geometry2 ) = 1
  • geometry1.STWithin( geometry2 ) = 1

使用方式必須是在 WHERE 子句後,以下述格式設定條件:
geometry1.方法( geometry2 )  比較運算子  數值

geography 則是 STIntersects(), STEquals(), and STDistance() 等方法可以使用空間索引

簡單的使用範例

搭配以下網頁 http://mikeo.co.uk/demo/sqlspatial/default.aspx 取得臺灣各地理座標(取多邊形的點時,要逆時針取)

image

在此建立存放地理資訊的資料表,並建立空間索引,然後輸入台北市各地標的經緯度資料,再比對各物件是否有交錯(STIntersects)

USE tempdb
go
CREATE TABLE tbGeography(
PK INT IDENTITY(1,1) PRIMARY KEY,
Descriptions NVARCHAR(100),
Geographys GEOGRAPHY);
go
CREATE SPATIAL INDEX SIndx ON tbGeography(Geographys);
–DROP INDEX SIndx ON tbGeography;

SELECT * FROM sys.spatial_reference_systems
WHERE well_known_text LIKE ‘%Taiwan%’

INSERT tbGeography(Descriptions, Geographys)VALUES (N’台北 101 大樓’,
geography::STGeomFromText(‘POINT(25.034127684732052 121.56410694122314)’, 4326))

INSERT into tbGeography (Descriptions, Geographys) VALUES (N’基隆路’,
geography::STGeomFromText(‘LINESTRING(25.042681800625725 121.56569480895997,
25.042759562579235 121.56586647033695, 25.028217219856525 121.55702590942383,
25.009628508097456 121.53462409973144)’, 4326))

INSERT into tbGeography (Descriptions, Geographys) VALUES (N’大安森林公園’,
geography::STGeomFromText(‘POLYGON((25.033369450224278 121.53292894363406,
25.026214596461695 121.53513908386233, 25.025884063244827 121.53743505477908,
25.033233356355037 121.53756380081182, 25.033369450224278 121.53292894363406))’, 4326))

DECLARE @g GEOGRAPHY = geography::STGeomFromText –建國南路
(‘LINESTRING(25.037335548101733 121.5373492240906, 25.036693982138722 121.5373492240906,
25.026972875183723 121.537070274353)’, 4326)

SELECT * FROM tbGeography WHERE Geographys.STIntersects(@g)= 1

結果如下:

image

TRUNCATE TABLE tbGeography

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

%d 位部落客按了讚: