1、2021/8/141空間數據索引技術空間數據索引技術與空間查詢語言與空間查詢語言第七講22021/8/14 空間數據索引技術 空間查詢語言32021/8/14空間索引技術空間索引技術一、 空間索引技術二、 簡單格網空間索引三、 KD樹索引（二叉樹索引）四、 B樹索引五、 四叉樹索引六、 可擴展的哈希索引七、 空間填充曲線42021/8/141)點四叉樹索引n點四叉樹是點四叉樹是QuadTreeQuadTree的一個變種，主要是針的一個變種，主要是針對空間點的存儲表達與索引，與對空間點的存儲表達與索引，與KDKD樹相似，樹相似，兩者的差別是在點四叉樹中，空間被分割成兩者的差別是在點四叉樹中，空間

2、被分割成四個矩形，四個不同的多邊形對應于四個矩形，四個不同的多邊形對應于SWSW、NWNW、SESE、NENE四個象限。四個象限。n點四叉樹的每個結點存儲了一個空間點的信點四叉樹的每個結點存儲了一個空間點的信息及孩子結點的指針。息及孩子結點的指針。五、四叉樹索引52021/8/14 （a a）平面圖）平面圖 （b b）結構圖）結構圖 圖圖5-22 5-22 一顆二維的點四叉樹結構一顆二維的點四叉樹結構(0,100)(100,100)(100,0)(0,0)B(10,75)D(30,90)F(80,70)A(45,45)E(70,20)C(25,15)AFBCEDNWNESWSE62021/8/

3、14n點四叉樹的結構簡單，對于精確匹配的點查點四叉樹的結構簡單，對于精確匹配的點查找性能較高，查找路徑只有一條。找性能較高，查找路徑只有一條。n但對區域查找，查找路徑有多條，查找性能但對區域查找，查找路徑有多條，查找性能較差。較差。n其搜索過程和其搜索過程和KDKD樹相似，如果想從樹相似，如果想從Point Point QuadTreeQuadTree中刪除一個點的話，則會引起相應中刪除一個點的話，則會引起相應的子樹的重建，一個簡單的方法是將所有子的子樹的重建，一個簡單的方法是將所有子樹上的數據重新插入。樹上的數據重新插入。72021/8/142) PR四叉樹nPRPR四叉樹是點四叉樹的一個變

4、種，它不使用數據集四叉樹是點四叉樹的一個變種，它不使用數據集中的點來分割空間。在中的點來分割空間。在PRPR四叉樹中，每次分割空間四叉樹中，每次分割空間時，都是將一個正方形分成四個相等的子正方形，時，都是將一個正方形分成四個相等的子正方形，依次進行，直到每個正方形的內容不超過所給定的依次進行，直到每個正方形的內容不超過所給定的桶量（比如一個對象）為止。桶量（比如一個對象）為止。 nPRPR四叉樹葉子結點可能不在樹的同一層次；葉子結四叉樹葉子結點可能不在樹的同一層次；葉子結點的黑結點或空結點分別表示數據空間某一位置空點的黑結點或空結點分別表示數據空間某一位置空間點的存在與否。間點的存在與否。82

5、021/8/14 圖圖5-24 PR5-24 PR四叉樹的索引結構四叉樹的索引結構NENWSWSEBCDDCBAG HFIEIFHG 92021/8/143) CIF四叉樹索引n它的組織方式與區域四叉樹相似，數據空間它的組織方式與區域四叉樹相似，數據空間被遞歸地細分直至產生的子象限不再包含任被遞歸地細分直至產生的子象限不再包含任何矩形。何矩形。n在分解的過程中，與任一劃分線相交的矩形在分解的過程中，與任一劃分線相交的矩形與該劃分線對應的象限相關聯，與該劃分線對應的象限相關聯，矩形只屬于矩形只屬于完全包圍它的最小象限完全包圍它的最小象限。圖。圖5-255-25是二維空間是二維空間一顆一顆CIFC

6、IF樹的例子（這里假設數據桶的容量樹的例子（這里假設數據桶的容量為為3 3個矩形）。個矩形）。 102021/8/14 （a a）平面圖）平面圖 （b b）結構圖）結構圖 （c c）桶表）桶表 圖圖5-25 5-25 二維空間二維空間CIFCIF四叉樹的一個例子四叉樹的一個例子112021/8/144) 基于固定網格劃分的四叉樹索引n在基于固定網格空間劃分的四叉樹空間索引機制在基于固定網格空間劃分的四叉樹空間索引機制中，二維空間范圍被劃分為一系列大小相等的棋中，二維空間范圍被劃分為一系列大小相等的棋盤狀矩形，即將地理空間的長和寬在盤狀矩形，即將地理空間的長和寬在X X和和Y Y方向上方向上進行

7、進行2 2N N等分，形成等分，形成2 2N N2 2N N的網格，并以此建立的網格，并以此建立N N級級四叉樹。四叉樹。n在四叉樹中，空間要素標識記錄在其外包絡矩形在四叉樹中，空間要素標識記錄在其外包絡矩形所覆蓋的每一個葉結點中。所覆蓋的每一個葉結點中。但當同一父親的四個兄弟結點都要記錄該空間要素標但當同一父親的四個兄弟結點都要記錄該空間要素標識時，則只將該空間要素標識記錄在該父親結點上，識時，則只將該空間要素標識記錄在該父親結點上，并按這一規則向上層推進。并按這一規則向上層推進。122021/8/14有效減少了大的空間要有效減少了大的空間要素（跨越多個網格）在素（跨越多個網格）在結點中的重

8、復記錄。結點中的重復記錄。132021/8/14網格文件n網格文件是一種典型的基于哈希的存取方式，網格文件是一種典型的基于哈希的存取方式，它是由包含著很多與數據桶相聯系的單元的它是由包含著很多與數據桶相聯系的單元的網格目錄來實現網格目錄來實現n對于二維空間為平行于對于二維空間為平行于x x或或y y軸的直線，這一軸的直線，這一超平面將數據空間劃分為兩個子空間。所有超平面將數據空間劃分為兩個子空間。所有的邊界一起將整個數據空間劃分成許多的邊界一起將整個數據空間劃分成許多k k維維的矩形子空間，這些矩形子空間稱為網格目的矩形子空間，這些矩形子空間稱為網格目錄，由一個錄，由一個k k維的數組表示。維

9、的數組表示。六、可擴展的哈希索引142021/8/14 圖圖5-28 5-28 網格文件的結構網格文件的結構152021/8/14n目錄項（即網格目錄數組的元素）和網格單目錄項（即網格目錄數組的元素）和網格單元之間具有一對一的關系。網格目錄的每一元之間具有一對一的關系。網格目錄的每一網格單元包含一個外存頁的地址，對應著一網格單元包含一個外存頁的地址，對應著一個數據桶，一般一個數據桶為硬盤上一個磁個數據桶，一般一個數據桶為硬盤上一個磁盤頁，這一外存頁存儲了包含了網格單元的盤頁，這一外存頁存儲了包含了網格單元的數據目標，稱為數據頁。數據目標，稱為數據頁。n數據頁所對應的一個或多個網格單元稱之為數據

10、頁所對應的一個或多個網格單元稱之為存儲區域存儲區域兩兩不相交。每個數據桶存儲區域存儲區域兩兩不相交。每個數據桶往往可以包含著幾個相鄰的單元，存儲多個往往可以包含著幾個相鄰的單元，存儲多個網格單元的目標，只要這幾個網格單元一起網格單元的目標，只要這幾個網格單元一起形成一矩形的區域。形成一矩形的區域。 六、可擴展的哈希索引162021/8/14D5D4D6網格文件插入目錄示意圖網格文件插入目錄示意圖172021/8/14七、空間填充曲線n空間填充曲線是一種重要的近似表示方法，將數空間填充曲線是一種重要的近似表示方法，將數據空間劃分成大小相同的網格，再根據一定的方據空間劃分成大小相同的網格，再根據一

11、定的方法將這些網格編碼，每個格指定一個唯一的編碼，法將這些網格編碼，每個格指定一個唯一的編碼，并在一定程度上保持并在一定程度上保持空間鄰近性空間鄰近性，即，即相鄰的網格相鄰的網格的標號也相鄰，的標號也相鄰，一個空間對象由一組網格組成。一個空間對象由一組網格組成。這樣可以將多維的空間數據降維表示到一維空間這樣可以將多維的空間數據降維表示到一維空間當中。當中。n理想的空間映射方法是：在多維空間中聚集的空理想的空間映射方法是：在多維空間中聚集的空間實體，經過填充曲線編碼以后，在一維空間中間實體，經過填充曲線編碼以后，在一維空間中仍然是聚集的。仍然是聚集的。 182021/8/14 （a a）行排序）

12、行排序 （b b）HilbertHilbert排序排序 （c c）Z Z排序排序 圖圖5-30 5-30 幾種常用的空間填充編碼方法幾種常用的空間填充編碼方法192021/8/141) Z-ordering曲線（peano曲線）lZ-排序（Z-ordering）技術將數據空間循環分解到更小的子空間（被稱為Peano Cell），每個子空間根據分解步驟依次得到一組數字，稱為該子空間的Z-排序值。l子空間有不同的大小，Z-排序有不同的長度，顯然，子空間越大，相應的Z-排序值越短。這里，分辨率（resolution）是指最大的分解層次，它決定了Z-排序值的最大長度。 202021/8/14 圖圖5-

13、31 Z-5-31 Z-排序示例排序示例2n 2n個分區， 編號為02n 2n-1212021/8/142) Hilbert曲線n與與Z-Z-排序類似，排序類似，HilbertHilbert曲線也是一種曲線也是一種空間填充曲線，它利用一個線性序列來空間填充曲線，它利用一個線性序列來填充空間，其構造過程如圖填充空間，其構造過程如圖5-335-33所示。所示。n實驗證明，實驗證明，Hi1bertHi1bert曲線的方法比曲線的方法比Z-Z-排排序好一些，因為它沒有斜線。不過序好一些，因為它沒有斜線。不過HilbertHilbert曲線算法的計算量要比曲線算法的計算量要比Z-Z-排序排序復雜。復雜。

14、222021/8/14 圖圖5-33 Hilbert5-33 Hilbert曲線示例曲線示例232021/8/14空間查詢語言空間查詢語言一、擴展一、擴展SQLSQL以處理空間數據以處理空間數據二、對象二、對象關系查詢語言關系查詢語言三、強調空間的查詢示例三、強調空間的查詢示例四、空間查詢處理四、空間查詢處理 242021/8/14n突破關系模型中關系必須是第一范式的限制，突破關系模型中關系必須是第一范式的限制，允許定義層次關系和嵌套關系。允許定義層次關系和嵌套關系。n增加抽象數據類型，如點、線、面、柵格、圖增加抽象數據類型，如點、線、面、柵格、圖像等。像等。n增加空間謂詞。如表示空間關系的，

15、包含、相增加空間謂詞。如表示空間關系的，包含、相交等，表示空間操作的，疊加、緩沖區等。交等，表示空間操作的，疊加、緩沖區等。n增加適合空間數據索引的方法，如增加適合空間數據索引的方法，如R數、四叉數、四叉樹等。樹等。一、擴展一、擴展SQLSQL以處理空間數據以處理空間數據在在SQL的基礎上進行擴展將是管理和分析空間的基礎上進行擴展將是管理和分析空間數據的一個趨勢。擴展關系模型主要表現在：數據的一個趨勢。擴展關系模型主要表現在：252021/8/14262021/8/14 定義的空間操作算子包括基本操作、空間關系運算定義的空間操作算子包括基本操作、空間關系運算和空間分析操作。和空間分析操作。操操

16、作作類類別別 方方法法名名稱稱 返返回回值值 類類型型 描描述述 Dimension ( ) Integer 返回幾何對象的維數。 GeometryType ( ) String 返回幾何對象的類型。 SRID ( ) Integer 返回幾何對象所屬的空間參考系ID。 Envelope( ) Geometry 返回幾何對象的最小外包矩形。 AsText( ) String 將幾何對象以WKT格式輸出。 AsBinary( ) Binary 將幾何對象以WKB格式輸出。 IsEmpty( ) Integer 如果幾何對象為空集， 則返回1 （為真， 下同） 。 IsSimple( ) Inte

17、ger 如果幾何對象是簡單的 （不自交） ， 則返回1。 基基本本操操作作 Boundary( ) Geometry 返回幾何對象的邊界。 272021/8/14Equals(anotherGeometry) Integer 如果兩個幾何對象的內部和邊界在空間上相等，則返回1。 Disjoint(anotherGeometry ) Integer 如果兩個幾何對象的內部和邊界在空間上都不相交，則返回1。 Intersects(anotherGeometry ) Integer 如果兩個幾何對象在空間上相交，則返回1。 Touches(anotherGeometry ) Integer 如果兩個

18、幾何對象邊界相交但內部不相交， 則返回1。 Crosses(anotherGeometry) Integer 如果一條線和面的內部相交，則返回1。 Within(anotherGeometry) Integer 如果這個幾何對象空間上位于另一個幾何對象內部，則返回1。 Contains(anotherGeometry) Integer 如果這個幾何對象空間上包含另一個幾何對象，則返回1。對于兩個幾何對象A、B，如果A.contains(B)為真 ，則 A.within(B)為真，即A.contains(B) = A.within(B)。 Overlaps(anotherGeometry:) I

19、nteger 如果幾何對象內部有非空交集，則返回1。 空空間間關關系系運運算算 Relate(anotherGeometry， intersectionPatternMatrix) Integer 如果這個幾何對象與另一個幾何對象的DE-9IM與intersectionPatternMatrix相匹配，則返回1。 282021/8/14Distance(anotherGeometry) Double 返回兩個幾何對象之間的最短距離。 Buffer(distance) Geometry 返回到給定幾何對象的距離小于或等于指定值的幾何對象的點的集合。 ConvexHull( ) Geometry

20、返回幾何對象的最小閉包。 Intersection(anotherGeometry) Geometry 返回由兩個幾何對象的交集構成的幾何對象。 Union(anotherGeometry) Geometry 返回由兩個幾何對象的并集構成的幾何對象。 Difference(anotherGeometry) Geometry 返回這個幾何對象與另一個幾何對象不相交的部分。 空空間間分分析析操操作作 SymDifference(anotherGeometry) Geometry 返回兩個幾何對象與對方互不相交的部分。 292021/8/141 1）SQL3SQL3（ SQL99SQL99）概覽）概

21、覽它詳細地描述了空間數據類型點、線、面在數據它詳細地描述了空間數據類型點、線、面在數據庫中的存儲方式，并能夠定義操作于空間數據的庫中的存儲方式，并能夠定義操作于空間數據的空間運算符。空間運算符。支持抽象數據類型（支持抽象數據類型（Abstract Data Type, ADT )Abstract Data Type, ADT ) 并且包括了指定拓撲操作和空間分析操作。并且包括了指定拓撲操作和空間分析操作。可以使用可以使用CREATE TYPECREATE TYPE語句來定義語句來定義ADT, ADTADT, ADT由一由一組屬性和訪問這些屬性的方法組成。組屬性和訪問這些屬性的方法組成。ADTADT可以作可以作為關系模式中某一列的類型。為關系模式中某一列的類型。二、對象二、對象關系查詢語言（關系查詢語言（OR-SQLOR-SQL） 302021/8/14擴展方案擴展方案ADT ADT ：二、對象二、對象關系查詢語言（關系查詢語言（OR-SQLOR-S