第6章-空間索引與空間信息查詢

第6章空間索引與查詢6.1空間索引一、空間索引技術二、簡單格網(wǎng)空間索引三、四叉樹索引四、R樹索引五、空間填充曲線對一個數(shù)據(jù)集做“索引”，是為了提高對這個數(shù)據(jù)集檢索的效率。索引是用來提供快速、有選擇性的存取數(shù)據(jù)庫的一種機制。相當于一個映射機構，將屬性的值轉換為相應的地址或地址集。對于空間數(shù)據(jù)，其存儲主要依賴于空間對象之間的位置關系而非屬性值。鑒于空間數(shù)據(jù)的特點，我們需要尋找適用的空間索引機制。

一、空間索引1.空間索引的定義

空間索引是指根據(jù)空間要素的地理位置、形狀或空間對象之間的某種空間關系，按一定的順序排列的一種數(shù)據(jù)結構，一般包括空間要素標識，外包絡矩形以及指向空間要素的指針。

2.空間索引的作用

為了GIS系統(tǒng)中快速定位到所選中的空間要素，從而提高空間操作的速度和效率?？臻g索引的技術和方法是GIS關鍵技術之一，是快速高效的查詢、檢索和顯示地理空間數(shù)據(jù)的重要指標，他的優(yōu)劣直接影響空間數(shù)據(jù)庫和GIS系統(tǒng)的整體性能。3.空間索引的分類按照搜索分割對象不同,可將空間索引分為3類,即基于點區(qū)域劃分的索引方法、基于面區(qū)域劃分的索引方法和基于三維體區(qū)域劃分的索引方法。B樹是常見的基于點區(qū)域劃分的索引。常見的空間索引

常見空間索引一般是自頂向下、逐級劃分空間的各種數(shù)據(jù)結構空間索引，比較有代表性的包括BSP樹、R樹、R+樹和CELL樹等。此外，結構較為簡單的格網(wǎng)型空間索引有著廣泛的應用。二、簡單格網(wǎng)空間索引基本思想是將研究區(qū)域用橫豎線條劃分大小相等和不等的格網(wǎng)，記錄每一個格網(wǎng)所包含的空間實體。當用戶進行空間查詢時，首先計算出用戶查詢對象所在格網(wǎng)，然后再在該網(wǎng)格中快速查詢所選空間實體，這樣一來就大大地加速了空間索引的查詢速度。

為了便于建立空間索引的線性表,每個格網(wǎng)按一定規(guī)律進行編碼，建立碼與空間實體的關系,該關系表就成為格網(wǎng)索引文件。每個要素在一個或者多個網(wǎng)格中,每個網(wǎng)格可以包含多個要素。21232931535561632022283052546062171925274951575916182426485056585713153739454746121436384446139113335414302810323440422123293153556163202228305254606217192527495157591618242648505658571315373945474612143638444613911333541430281032344042空間索引對象索引Peano鍵空間對象空間對象Peano鍵集7BA25-2514EB7-715EC54-5525AC60-6026ED32-3332DD35-3533DD38-3835D.FE14-1537EE26-2638DE37-3739EE39-3948EE48-4850EE50-5054CF35-3555C60CABCEDF每個要素在一個或者多個網(wǎng)格中,每個網(wǎng)格可以包含多個要素,要素不是真正被分割。由此建立Peano鍵和空間對象的關系。三.四叉樹檢索點四叉樹區(qū)域四叉樹

MX四叉樹

PR四叉樹CIF四叉樹1.點四叉樹以空間點為劃分點，將索引空間分為兩兩不相交的的2k個子空間，依次與它的2k個子結點相對應，對于位于某一子空間的點，則分配給對應的子樹。點四叉樹的構造過程：（1）輸入空間點A，以A為根節(jié)點并進行劃分空間。（2）輸入空間點B，B落入A的NW象限，并且A的NW象限為空，則B直接放入A的NW象限孩子結點。同理，C是A的SW孩子結點。（3）輸入D，由于D落入A的NW象限，但是NW不為空，所以繼續(xù)往下查找，得到B的NE象限為空，因此，D作為B的NE孩子結點。（4）同理，空間點E、F，分別為A的SE、NE孩子節(jié)點。缺點：（1）盡管點四叉樹構造簡單，但是刪除一個節(jié)點時，該節(jié)點對應的所有子樹節(jié)點必須重新插入四叉樹中，效率很差。（2）對于精確匹配的點查找，效率很高，但是對于區(qū)域查找，查找路徑有多條，效率較差。（3）樹的動態(tài)性差，樹的結構完全由點的插入順序決定。樹的平衡難以保證。 區(qū)域四叉樹(Region-BasedQuadtree)是以區(qū)域目標為循環(huán)分解對象的四叉樹,分解過程既可以按照區(qū)域邊界,也可以按照區(qū)域內部對二維空間進行劃分。 如果區(qū)域四叉樹中的結點覆蓋的區(qū)域中所有數(shù)組元素的值都相同，則該結點是葉子結點。否則，該結點是內部結點，被進一步劃分為四個等大小的子結點。 主要有MX四叉樹與PR四叉樹。 避免了點四叉樹的動態(tài)性差、結構完全由點的插入順序決定的功能缺點。2.區(qū)域四叉樹MX四叉樹

MX四叉樹將每個空間點看成是區(qū)域四叉樹中的一個黑象素，或當成一個方陣（SquareMatrix）中的非零元素，因此稱為MX四叉樹。 利用葉子節(jié)點為黑節(jié)點或空閑點表示數(shù)據(jù)空間某一位置空間點的存在與否。

樹的構造過程即是對整個數(shù)據(jù)空間重復地進行2k次等分，直到每一空間點都位于某一象限的最左下角的過程。MX四叉樹特點： 空間中每一個點都屬于某一象限且位于該象限的最左下角，每一象限只與一個空間點相關聯(lián)。 盡管D同時是兩個大小不等的象限的最左下角，但其應屬于最下一級象限（即最后一次空間劃分所產(chǎn)生的子象限）。這就決定了所有空間點均位于葉子節(jié)點。缺點： 插入（或刪除）一個點可能導致樹的深度增加（或減少）一層或多層，所有的葉子節(jié)點都必須重新定位。 樹的深度往往很大，這會影響查找效率。

PR（PointRegion）四叉樹葉子節(jié)點或者為空，或者包含唯一數(shù)據(jù)點。PR四叉樹

PR四叉樹與MX四叉樹的構造過程類似，不同的是，當分解到一個象限只包含一個點時，不需要繼續(xù)分解使該點位于某一子象限的最左下角。 另外，插入或刪除一個點也不會影響到其他的分支，操作比較簡單。PR四叉樹與MX四叉樹的區(qū)別：（1）數(shù)據(jù)點位于象限內，不要求位于左下角。（2）葉子節(jié)點可能不在樹的同一層次。（3）PR四叉樹的葉子結點數(shù)及樹的深度都小于MX四叉樹，因此PR四叉樹效率高。CIF四叉樹

CIF四叉樹是為了表示VLSI（VeryLargeScaleIntegration)應用中的小矩形而提出的。它可以用于索引空間矩形及其他形體。 表示方式與區(qū)域四叉樹類似，數(shù)據(jù)空間被遞歸的細分，直至產(chǎn)生的子象限不再包含任何矩形。 在分解過程中，所有與任一劃分線相交的矩形與該劃分線對應的象限相關聯(lián)。0數(shù)據(jù)桶的容量設為3。相交查詢：從根節(jié)點開始，首先檢查與之關聯(lián)的所有矩形是否為查找結果；接下來檢查象限空間與查詢區(qū)域相交的孩子結點….直到葉子節(jié)點。插入矩形：首先檢查根節(jié)點，如果與根節(jié)點的劃分線相交，則插入到根節(jié)點對應的桶鏈表中；否則檢查包含該矩形的子象限的孩子結點…；如果檢查到某一沒有孩子的象限，而且該矩形依舊沒有插入到對應的位置，那么該象限必須再次細分直到為該矩形找到對應的子象限。刪除矩形：找到矩形所在結點，從數(shù)據(jù)桶中刪除。如果刪完后桶為空，且該節(jié)點沒有孩子結點，則可以刪除該節(jié)點。

CIF四叉樹可以用于索引矩形以及任何其他形體的空間目標而不需要經(jīng)過目標近似與空間目標映射，因此對于區(qū)與查詢，效率相對MX、PR四叉樹要高些。 但是區(qū)域查詢往往需要訪問多個節(jié)點對應的存儲桶，尤其當索引量增大，大區(qū)域節(jié)點所包含較多數(shù)據(jù)矩形時，外存I/O開銷很大。四叉樹索引優(yōu)點：結構清晰，容易建立。它同時具有聚集空間目標的能力（在柵格數(shù)據(jù)存儲中發(fā)揮突出作用），提高了檢索效率，得到廣泛應用。

有很多改進的方法被提出：（1）一體化索引，進行了索引空間的三級劃分，包括索引塊、基本格網(wǎng)、細分格網(wǎng)，并采用行次序法對各級區(qū)域進行了編碼。（2）CELLQTREE，葉子節(jié)點索引點對象，中間節(jié)點索引線和面對象，較好的解決了大區(qū)域對象的標示符在子空間結點中的多次重復存儲問題。四叉樹索引的缺點：當索引數(shù)據(jù)量較大時，如果四叉樹層次過小，將導致查找性能下降；如果四叉樹層次過大，將導致重復存儲的增加，從而增加空間開銷，這同時又會影響查找性能。四.R樹空間索引1.R樹

1984年Guttman發(fā)表了《R樹:一種空間查詢的動態(tài)索引結構》，首次提出了R樹空間索引結構。其后，人們在此基礎上針對不同空間運算提出了不同改進，才形成了一個繁榮的索引樹族，是目前流行的空間索引。

R樹是一種高度平衡的樹，由中間節(jié)點和頁節(jié)點組成，實際數(shù)據(jù)對象的最小外接矩形存儲在頁節(jié)點中，中間節(jié)點通過聚集其低層節(jié)點的外接矩形形成，包含所有這些外接矩形。

R樹是一種動態(tài)索引結構，即：它的查詢可與插入或刪除同時進行，而且不需要定期地對樹結構進行重新組織。R樹示例圖五、空間填充曲線空間填充曲線是一種重要的近似表示方法，將數(shù)據(jù)空間劃分成大小相同的網(wǎng)格，再根據(jù)一定的方法將這些網(wǎng)格編碼，每個格指定一個唯一的編碼，并在一定程度上保持空間鄰近性，即相鄰的網(wǎng)格的標號也相鄰，一個空間對象由一組網(wǎng)格組成。這樣可以將多維的空間數(shù)據(jù)降維表示到一維空間當中。理想的空間映射方法是：在多維空間中聚集的空間實體，經(jīng)過填充曲線編碼以后，在一維空間中仍然是聚集的。（a）行排序（b）Hilbert排序（c）Z排序圖5-30幾種常用的空間填充編碼方法1)Z-ordering曲線（peano曲線）Z-排序（Z-ordering）技術將數(shù)據(jù)空間循環(huán)分解到更小的子空間（被稱為PeanoCell），每個子空間根據(jù)分解步驟依次得到一組數(shù)字，稱為該子空間的Z-排序值。子空間有不同的大小，Z-排序有不同的長度，顯然，子空間越大，相應的Z-排序值越短。這里，分辨率（resolution）是指最大的分解層次，它決定了Z-排序值的最大長度。圖5-31Z-排序示例2n×2n個分區(qū)，編號為0~2n×2n-12)Hilbert曲線與Z-排序類似，Hilbert曲線也是一種空間填充曲線，它利用一個線性序列來填充空間，其構造過程如圖5-33所示。實驗證明，Hi1bert曲線的方法比Z-排序好一些，因為它沒有斜線。不過Hilbert曲線算法的計算量要比Z-排序復雜。圖5-33Hilbert曲線示例6.2空間查詢一.空間信息與空間信息查詢二.空間查詢方式三.空間信息查詢語言一.空間信息與空間信息查詢空間位置和形態(tài)對象所在的地理區(qū)域，對象的幾何和屬性特征?？臻g關系和關聯(lián)空間對象間的拓撲關系。空間分布規(guī)律特定類別地物分布在特定的區(qū)域，如電子市場、娛樂場所、飲食街等。時空演化通過時間空間數(shù)據(jù)分析，可以研究和揭示事物發(fā)展演化的規(guī)律。空間信息分類空間信息查詢

查詢什么空間查詢的一般問題是“有沒有？”、“是什么？”、“在什么地方？”、“怎樣（到達）？”查詢對象圖形中的信息屬性表中的信息其它信息一般問題是“某圖元代表什么實體，有什么屬性”、“處于什么位置、距離、路徑”、“一定范圍內包含的地物，地物之間的關系等”。查詢的意義

信息管理通過查詢可以獲取特定數(shù)據(jù)，進行信息管理和數(shù)據(jù)更新。特定信息提取通過查詢提取需要的信息，據(jù)棄無關的信息，便于使用?？臻g分析基礎查詢結果一般是對所需查找的信息及數(shù)據(jù)的報告，研究需要對這些數(shù)據(jù)單獨提出進行相關分析。1、圖查文(圖形查詢屬性)2、文查圖(屬性查詢圖形)2、空間關系的查詢(面—點、面—線、面—面、線—點、線—線查詢)4、邏輯查詢(SQL查詢)二.空間查詢方式圖文互查是GIS中最常用的查詢。如：在中國行政區(qū)圖查人口>4000萬的省。1）和一般SQL查詢類似，構建SQL查詢語句進行查詢。2）查詢到結果后，利用圖形和屬性的對應關系，再圖上表示出結果。1、圖查文圖查文圖查文2、文查圖

一般GIS軟件提供“INFO”工具。用點選、區(qū)域圈選、多邊形選擇、矩形選擇的方式選中地物，并顯示出查詢對象的屬性列表。1）利用空間索引，在數(shù)據(jù)庫中快速檢索被選空間實體。2）根據(jù)實體和屬性的連接關系得到所查詢實體的屬性列表。文查圖文查圖MapInfo軟件中點目標的幾何參數(shù)查詢MapInfo軟件中線目標的幾何參數(shù)查詢Mapinfo軟件中面狀目標的幾何參數(shù)查詢是指給定一個點或一個幾何圖形，檢索出該圖形范圍內的空間對象以及相應的屬性。這種查詢方式又稱為圖形查詢屬性的方式。

MapInfo軟件中圖形查屬性的表達方式ArcView軟件中圖形查屬性的表達方式3、空間關系的查詢通過空間關系查詢和定位空間實體是地理數(shù)據(jù)庫不同于一般數(shù)據(jù)庫的功能之一。如查詢滿足下列條件的城市：滬線東部（空間方位關系）；距離京滬線不超過50km（空間距離關系）;城市人口大于100萬（屬性信息查詢）；·面面查詢如與某個多邊形相鄰的多邊形有哪些·面線查詢如某個多邊形的邊界有哪些線·面點查詢如某個多邊形內有哪些點狀地物·線面查詢如某條線經(jīng)過（穿過）的多邊形有哪些，某條鏈的左、右多邊形是哪些·線線查詢如與某條河流相連的支流有哪些，某條道路跨過哪些河流?！ぞ€點查詢如某條道路上有哪些橋梁，某條輸電線上有哪些變電站?！c面查詢如某個點落在哪個多邊形內。·點線查詢如某個結點由哪些線相交而成。

水系城鎮(zhèn)查詢城鎮(zhèn)是否位于平原區(qū)內舉例：點面查詢(1)鄰接查詢從多邊形與弧段關系的表中，檢索出該多邊形關系的所有弧段從弧段關系的左右多邊形的表中，檢索出這些弧段所關聯(lián)的多邊形(2)包含關系查詢

查詢某一個面狀所包含的某一類的空間對象(3)穿越查詢長江所經(jīng)過的縣市(4)落入查詢

查詢一個空間對象它落在哪個空間對象之內?？刹捎每臻g運算，使用點在多邊形內，線在多邊形內，或面在多邊形內的差別方法。

(5)緩沖區(qū)查詢

緩沖區(qū)查詢根據(jù)用戶需要給定一個點緩沖、線緩沖或面緩沖的距離，從而形成一個緩沖區(qū)的多邊形，再根據(jù)多邊形檢索的原理，檢索出該緩沖區(qū)多邊形內的空間地物。

距黃河150公里范圍內的主要城市（6）地址匹配查詢

根據(jù)街道地址來查詢事物的空間位置和屬性信息是地理信息系統(tǒng)特有的一種查詢功能，這種查詢利用地理編碼，輸入街道門牌號碼，就可知道大致的位置和所在的街區(qū)。

（7）SQL查詢

（7）SQL查詢

查詢機耕道ArcGIS三.空間信息查詢語言１、SQL查詢語言２、擴展的SQL查詢MapInfo軟件中SQL輸入標準對話框

通過SQL語言查詢的結果

SelectfromwhereGIS中SQL查詢例1GIS中SQL查詢例2查世界地圖屬性表中有多少國家?總人口?總面積?多表連接查詢如查出美國地圖數(shù)據(jù)中總人口大于1000萬且州府人口大于20萬的州。

SELECT*FROMStates,StatecapWHERE

States.state=Statecap

.Stateand

States.pop_1990>10000000andStatecap.pop_1990>200000嵌套查詢求世界地圖中同伊拉克處于同一大洲的國家

SELECTcountry,continentFROMworldWHEREcontinent=(SELECTcontinent

FROMworld

WHEREcountry=“Iraq”)；首先求出伊拉克處于哪個洲；之后求出同伊拉克處于同一洲的國家。１、查詢謂詞的擴展２、面向對象的擴展３、模糊擴展擴展SQL查詢增加空間數(shù)據(jù)類型（點、線、面）增加空間操作算子（長度、面積）增加查詢條件（臨近、疊加、經(jīng)過）1、查詢謂詞的擴展

Mapinfo在SELECT語句中增加了地理函數(shù)和地理運算符.1、查詢謂詞的擴展例：美國“I10”號高速公路經(jīng)過哪幾個洲？先美國高速公路中找出“I10”號高速公路；再找“I10”號高速公路經(jīng)過哪幾個洲。WHEREStates.objCONTAINSUs_Hiway.objAND

(States.objINTERSECTS(SELECTobjFROMUs_HiwayWHERE

us_Hiway.highway=“I10”))地理運算符例如查詢三峽地區(qū)長江流域人口大于50萬的縣或市，擴展的SQL空間查詢語句為：

SELECT*

FROM

縣或市

WHERE

縣或市·人口>50萬

ANDCROSS

（河流·名稱=“長江”）

1、查詢謂詞的擴展擴展SQL空間查詢結果

這些SQL擴充和應用有關，目前還沒有形成標準。例：（1）選擇河南省所有城市和人口

SELECT城市名，人口FROM城市

WHERECENTER（城市地圖）INSIDE

河南；（2）選擇流經(jīng)河南省的所有河流的名稱和河南境內長度

SELECT河流名，LENGTH（INTERSECTS

（ROUTE（河流流域圖），河南））；

FROM河流WHEREROUTE(河流流域圖)INTERSECTS

河南；1、查詢謂詞的擴展

采用面向對象的方法來設計SQL語言（OOSQL）。優(yōu)點如下：（1）良好的查詢機制，易于實現(xiàn)持久性。（2）對象簡化了查詢，解決了某些常見的SQL難題。

2、面向對象的擴展2、面向對象的擴展OGIS協(xié)會（OpenGIS）是由一些主要軟件供應商組成的聯(lián)盟，負責制定與GIS互操作相關的行標準。OGIS的空間數(shù)據(jù)模型可以嵌入到各種編程語言中，例如C、Java、SQL等等，提出了一套規(guī)范，把二維地理空間ADT（abstractdatatype,抽象數(shù)據(jù)類型）整合到SQL之中，并且包括了指定拓撲的操作和空間分析操作。在OGIS標準中，所指定的操作可分成三類：⑴用于所有幾何類型的基本操作。例如，SpatialReference返回所定義對象幾何體采用的基礎坐標系統(tǒng)。⑵用于空間對象間拓撲關系的操作測試。例如，overlay判斷兩個對象內部是否有一個非空的交集。⑶用于空間分析的一般操作。例如，