1、空間索引結構空間索引結構 空間索引技術是提高空間數據查詢和各種空間索引技術是提高空間數據查詢和各種空間分析效率的關鍵技術。空間索引可縮小空間分析效率的關鍵技術。空間索引可縮小空間數據的搜索范圍，使訪問不需要遍歷整空間數據的搜索范圍，使訪問不需要遍歷整個空間數據集。個空間數據集。索引文件中的數據稱為索引數據，索引結索引文件中的數據稱為索引數據，索引結構是索引數據的數據結構及索引創建與維護構是索引數據的數據結構及索引創建與維護算法的總稱。算法的總稱。空間索引結構是按照空間數據在空間分布空間索引結構是按照空間數據在空間分布上的特性來組織和存儲索引數據的索引結構。上的特性來組織和存儲索引數據的索引結構

2、。空間索引結構空間索引結構 空間索引結構應滿足下列三個要求：空間索引結構應滿足下列三個要求：一、存儲效率高：一、存儲效率高：相對于被索引的數據集而言，索引數據的數相對于被索引的數據集而言，索引數據的數據量應盡量小。否則，訪問索引數據可能成為數據量應盡量小。否則，訪問索引數據可能成為數據查詢與更新的效率瓶頸。據查詢與更新的效率瓶頸。二、查詢效率高：二、查詢效率高：選擇良好的索引數據結構，設計具體的基于選擇良好的索引數據結構，設計具體的基于索引的空間訪問方法（索引的空間訪問方法（SAM Spatial Access Method），高效實現以下的查詢：），高效實現以下的查詢：1、點選擇：從數據集中

3、找出包含給定點的所、點選擇：從數據集中找出包含給定點的所有空間對象。有空間對象。2、范圍查詢：查詢與給定對象間的距離小于、范圍查詢：查詢與給定對象間的距離小于某個給定值的所有空間對象。某個給定值的所有空間對象。空間索引結構空間索引結構 3、區域（窗口）查詢：查找含在區域內、區域（窗口）查詢：查找含在區域內、與區域相交或部分位于區域中的所有空間對象，與區域相交或部分位于區域中的所有空間對象，窗口是一個特殊的區域。窗口是一個特殊的區域。 4、K-最鄰近查詢：給定一個參照對象（點、最鄰近查詢：給定一個參照對象（點、線或區域），查詢距離參照對象最近的線或區域），查詢距離參照對象最近的K 1個個空間對象

4、。空間對象。 5、空間關系查詢：相交、相鄰、包含等拓、空間關系查詢：相交、相鄰、包含等拓撲關系查詢，方位關系和基于距離的各種查詢。撲關系查詢，方位關系和基于距離的各種查詢。 6、其他查詢：將滿足一定空間條件的兩個、其他查詢：將滿足一定空間條件的兩個空間對象集合進行空間連接，空間集合運算等也空間對象集合進行空間連接，空間集合運算等也是一種空間訪問。是一種空間訪問。空間索引結構空間索引結構 三、更新效率高：三、更新效率高：數據對象的增加、修改和刪除將導致索引數據數據對象的增加、修改和刪除將導致索引數據更新，索引數據與被索引的數據集必須保持一致。更新，索引數據與被索引的數據集必須保持一致。索引數據的

5、更新操作包括：插入索引項、刪除索引數據的更新操作包括：插入索引項、刪除索引項和修改索引項（先刪除再增加）。數據集經索引項和修改索引項（先刪除再增加）。數據集經常變化時，需要考慮新增索引項和刪除索引項時，常變化時，需要考慮新增索引項和刪除索引項時，索引結構的快速更新能力。索引結構的快速更新能力。很難設計一種空間索引結構同時能提供高效的很難設計一種空間索引結構同時能提供高效的存儲、高效的查詢和高效的更新，實際應用中總是存儲、高效的查詢和高效的更新，實際應用中總是犧牲某些方面的效率來換取另外方面的效率。犧牲某些方面的效率來換取另外方面的效率。索引結構可分為靜態索引和動態索引結構，還索引結構可分為靜態

6、索引和動態索引結構，還分為內存索引和外存索引，外存索引需要考慮磁盤分為內存索引和外存索引，外存索引需要考慮磁盤頁面訪問的效率瓶頸問題。頁面訪問的效率瓶頸問題。 空間索引技術的基本原理空間索引技術的基本原理空間索引技術的基本原理是采用基于空間空間索引技術的基本原理是采用基于空間位置或基于空間對象的分割方法，把研究空間位置或基于空間對象的分割方法，把研究空間劃分為若干區域，每個區域為一個索引單元，劃分為若干區域，每個區域為一個索引單元，存儲多個空間索引項，按照空間位置鄰近的對存儲多個空間索引項，按照空間位置鄰近的對象其索引項的位置也應該鄰近的原則來組織空象其索引項的位置也應該鄰近的原則來組織空間索

7、引數據。間索引數據。空間索引按照對空間的劃分方式分為空間空間索引按照對空間的劃分方式分為空間驅動的索引和數據驅動的索引；按照索引文件驅動的索引和數據驅動的索引；按照索引文件的數據結構又分為線性索引和非線性索引。的數據結構又分為線性索引和非線性索引。空間索引技術的基本原理空間索引技術的基本原理空間對象的幾何形狀錯綜復雜，表示幾何形狀的坐空間對象的幾何形狀錯綜復雜，表示幾何形狀的坐標序列是變長的，直接以形狀數據為索引字段將導致索標序列是變長的，直接以形狀數據為索引字段將導致索引項很復雜。為此，首先將空間對象的幾何形狀采用某引項很復雜。為此，首先將空間對象的幾何形狀采用某種近似的簡單圖形來表示，平行

8、于坐標軸且包含特定空種近似的簡單圖形來表示，平行于坐標軸且包含特定空間對象的最小外接矩形間對象的最小外接矩形MBB（Minimal Bounding Box）或或MBR(Minimum Bounding Rectangle) 是空間對象幾是空間對象幾何形狀的一種近似表示。何形狀的一種近似表示。以以 MBB，OID，PRT為索引項建立空間索引，可為索引項建立空間索引，可使每個空間索引項具有固定長度。其中：使每個空間索引項具有固定長度。其中：OID為對象標為對象標識，識，MBB為對象的最小外接矩形，為對象的最小外接矩形，PRT為指向幾何數據為指向幾何數據的指針，的指針，OID直接將直接將MBB映射

9、到存放幾何形狀和屬性的映射到存放幾何形狀和屬性的物理頁。物理頁。 空間索引技術的基本原理空間索引技術的基本原理空間索引介于空間計算算法與空間數據之間，用于過空間索引介于空間計算算法與空間數據之間，用于過濾大量與空間計算無關的數據，以提高空間操作的效率。濾大量與空間計算無關的數據，以提高空間操作的效率。 SAM只加速了索引項中只加速了索引項中MBB的查找（過濾），在此基礎的查找（過濾），在此基礎上還要對幾何圖形進行精確查找。上還要對幾何圖形進行精確查找。基于空間索引的空間查詢分兩步完成：基于空間索引的空間查詢分兩步完成：第一步利用空間索引結構和空間訪問方法第一步利用空間索引結構和空間訪問方法SA

10、M對數據對數據集進行過濾（初選），在索引表中查找滿足查詢條件的集進行過濾（初選），在索引表中查找滿足查詢條件的MBB，結果為對象的一個超集（多個，結果為對象的一個超集（多個OID）。）。第二步對初選結果進行準確查找，在超集中通過空間第二步對初選結果進行準確查找，在超集中通過空間計算算法，求取滿足查詢條件的精確對象。計算算法，求取滿足查詢條件的精確對象。 空間驅動的索引結構空間驅動的索引結構空間驅動索引結構的主要特征是采用空間驅動索引結構的主要特征是采用某種格網對某種格網對2D空間進行劃分，將空間劃分空間進行劃分，將空間劃分成小區域，每個小區域為一個成小區域，每個小區域為一個索引單元索引單元，每

11、個索引單元每個索引單元包含多個索引項，包含多個索引項，每個索引每個索引項項索引一個空間對象索引一個空間對象。索引單元按照一定的索引單元按照一定的數據結構數據結構來組織。來組織。如果組織成線性結構，則相應的空間索引如果組織成線性結構，則相應的空間索引為線性索引，如果組織成非線性結構，則為線性索引，如果組織成非線性結構，則相應的空間索引為非線性索引。相應的空間索引為非線性索引。網格索引網格索引網格索引是一種空間驅動的非線性索引結網格索引是一種空間驅動的非線性索引結構，其基本特征是用正方形或矩形格網對研究構，其基本特征是用正方形或矩形格網對研究區域的區域的2D空間進行劃分，每個網格單元為一空間進行劃

12、分，每個網格單元為一個索引單元，索引多個空間對象，索引單元按個索引單元，索引多個空間對象，索引單元按行列號組織成行列號組織成2D目錄。目錄。網格索引包括均勻網格索引和網格文件索網格索引包括均勻網格索引和網格文件索引，均勻網格適合于索引空間點對象；網格文引，均勻網格適合于索引空間點對象；網格文件是均勻網格的改進，是一種多關鍵字索引，件是均勻網格的改進，是一種多關鍵字索引，可索引點對象和對象的可索引點對象和對象的MBB，能夠與，能夠與B+樹簡樹簡單集成，在商用數據庫單集成，在商用數據庫Oracle中已實現。中已實現。 均勻網格索引均勻網格索引 一、均勻網格的特征一、均勻網格的特征 設幾何對象均為點

13、對象。研究區域為一個設幾何對象均為點對象。研究區域為一個Sx*Sy大小的空間，將其劃分為大小的空間，將其劃分為nx*ny個相同大個相同大小的網格，每個網格的邊長為小的網格，每個網格的邊長為Sx/nx*Sy/ny，起始，起始坐標為坐標為(Xo,Yo)。每個網格為一個索引單元，對應于磁盤上一個每個網格為一個索引單元，對應于磁盤上一個物理頁，每個網格中的點存入相應的磁盤頁中。物理頁，每個網格中的點存入相應的磁盤頁中。每個索引單元包含的索引項數量是有限制的，每個索引單元包含的索引項數量是有限制的，不能超過一個物理頁的存儲容量。不能超過一個物理頁的存儲容量。 均勻網格索引均勻網格索引圖圖7-3 均勻網格

14、均勻網格 如圖如圖7-3，索引組織成，索引組織成2D數組數組DIR1:nx,1:ny形式的目形式的目錄表，每個目錄項錄表，每個目錄項DIRi，j 對應一個索引單元。一個索引對應一個索引單元。一個索引單元包含形式為單元包含形式為OID, PageID的多個索引項，存儲為一個的多個索引項，存儲為一個物理頁。物理頁。OID為空間對象的主碼，為空間對象的主碼，PageID為該索引單元對為該索引單元對應的物理頁標識。應的物理頁標識。均勻網格索引均勻網格索引（二）基于均勻網格索引的空間訪問（二）基于均勻網格索引的空間訪問1、插入新點：假設新點的坐標為（、插入新點：假設新點的坐標為（x，y），計算新點），計

15、算新點所在網格（索引單元）的行列號。新點的索引目錄項為所在網格（索引單元）的行列號。新點的索引目錄項為DIRi，j，假設對應的磁盤頁，假設對應的磁盤頁DIRi，j.PageID為為(a，b)所所在的頁在的頁P(a，b)，將新點插入，將新點插入P(a，b)頁中。頁中。2、點查詢：假設鼠標當前位置的坐標為、點查詢：假設鼠標當前位置的坐標為 (x，y)，計算，計算鼠標位置所屬索引單元的行列號鼠標位置所屬索引單元的行列號i=(X-Xo)/(Sx/nx)+1和和j=(Y-Yo)/(Sy/ny) +1，讀入對應的磁盤頁，讀入對應的磁盤頁DIRi，j.PageID，掃，掃描該頁中所有點對象，判斷哪些點對象與

16、描該頁中所有點對象，判斷哪些點對象與(x，y)點重疊。點重疊。3、窗口查詢：計算窗口、窗口查詢：計算窗口W覆蓋的網格集合覆蓋的網格集合S=Ci,j，對對S中的每個讀取中的每個讀取DIRi，j.PageID，返回這些頁中包含的，返回這些頁中包含的所有點對象，即為窗口所有點對象，即為窗口W范圍內包含的點對象。范圍內包含的點對象。 均勻網格索引均勻網格索引格網分辨率的選擇取決于被索引點對象的數量。格網分辨率的選擇取決于被索引點對象的數量。假設共有假設共有N個點對象，每頁存儲的最大點數為個點對象，每頁存儲的最大點數為M，則至少需要有則至少需要有N/M個網格。如果某個網格中的點數個網格。如果某個網格中的

17、點數超過超過M，多出的點放到溢出區，溢出區與索引區域，多出的點放到溢出區，溢出區與索引區域用指針相連。用指針相連。所有的網格共用一個溢出區，溢出區可能由多所有的網格共用一個溢出區，溢出區可能由多個磁盤頁連接成溢出區鏈。如果個磁盤頁連接成溢出區鏈。如果o點存儲在溢出區鏈點存儲在溢出區鏈的第的第q頁，則點查詢的頁，則點查詢的I/O數為數為q。最壞的情況下，所。最壞的情況下，所有點都位于同一網格中，索引結構為磁盤頁的線性有點都位于同一網格中，索引結構為磁盤頁的線性列。點的頻繁插入會導致較長的溢出鏈，而點刪除列。點的頻繁插入會導致較長的溢出鏈，而點刪除會導致空頁。對于某些具體分布，這種索引不能滿會導致

18、空頁。對于某些具體分布，這種索引不能滿足磁盤存儲的要求足磁盤存儲的要求。均勻網格索引均勻網格索引如圖如圖7-4中例子，每個網格所存的最大點數中例子，每個網格所存的最大點數M=4，k,l,m,n,o五個點對象位于同一個網格中，對應于磁盤五個點對象位于同一個網格中，對應于磁盤頁頁P。將。將k,l,m,n四個點放入四個點放入P頁，頁，o放入溢出區，將溢放入溢出區，將溢出區與出區與P頁相連。頁相連。圖圖7-4 均勻網格中的溢出頁均勻網格中的溢出頁 網格文件索引網格文件索引二、點對象的格網文件二、點對象的格網文件格網文件與均勻格網的相同之處是采用平行于坐標軸的格網格網文件與均勻格網的相同之處是采用平行于

19、坐標軸的格網對空間進行完全劃分，每個網格單元為一個索引單元，索引單元對空間進行完全劃分，每個網格單元為一個索引單元，索引單元組織成組織成2D目錄形式。與均勻格網不同的是，每次發生溢出時，動目錄形式。與均勻格網不同的是，每次發生溢出時，動態的將網格單元在橫向或縱向上分裂為兩個單元，可根據網格單態的將網格單元在橫向或縱向上分裂為兩個單元，可根據網格單元中點對象的分布情況來選擇進行縱向還是橫向劃分；網格文件元中點對象的分布情況來選擇進行縱向還是橫向劃分；網格文件中的網格單元為大小不相同的矩形單元，多個網格單元可對應同中的網格單元為大小不相同的矩形單元，多個網格單元可對應同一個磁盤頁。一個磁盤頁。 （

20、一）格網文件的數據結構（一）格網文件的數據結構 格網文件由三種數據結構來實現，索引目錄格網文件由三種數據結構來實現，索引目錄DIR是一種與均是一種與均勻網格中的索引目錄類似的勻網格中的索引目錄類似的2D數組，差別是兩個相鄰單元可共享數組，差別是兩個相鄰單元可共享同一磁盤頁；同一磁盤頁；Sx,Sy是兩個線性數組，表示沿兩坐標軸的劃分。是兩個線性數組，表示沿兩坐標軸的劃分。圖圖7-5中的例子描述了這種結構，假設網格的最大容量中的例子描述了這種結構，假設網格的最大容量M=4。 網格文件索引網格文件索引圖7-5均勻網格文件的插入 網格文件索引網格文件索引網格文件索引網格文件索引網格文件索引網格文件索引

21、三、格網文件索引三、格網文件索引MBB用網格文件對用網格文件對MBB進行索引，最簡單的情況是每個覆蓋進行索引，最簡單的情況是每個覆蓋MBB的的網格單元都保存該網格單元都保存該MBB的索引項。的索引項。MBB與網格單元的關系有三種：與網格單元的關系有三種：MBB包含網格單元、網格單元與包含網格單元、網格單元與MBB相交、網格單元包含相交、網格單元包含MBB。前兩。前兩種情況，每個網格單元都建立種情況，每個網格單元都建立MBB的索引項，一個的索引項，一個MBB有多項索引。有多項索引。例子：有例子：有15個個MBB，每頁的最大容量為，每頁的最大容量為4。圖。圖7-6為用均勻網格建為用均勻網格建立的索

22、引：立的索引： 圖圖7-6 基于基于MBB的均勻網格索引的均勻網格索引 網格文件索引網格文件索引圖圖7-7為用網格文件建立的索引：為用網格文件建立的索引： 圖圖7-7 基于網格文件的基于網格文件的MBB索引索引 網格文件索引網格文件索引（一）索引項插入（一）索引項插入1、插入對象、插入對象14如圖如圖7-8，將對象，將對象14插入圖插入圖7-7中的索引單元中的索引單元DIR1，3時，時，DIR1，3中的索中的索引項超過引項超過4項，對應的磁盤頁項，對應的磁盤頁p5也溢出。在也溢出。在X3處對處對DIR1，3進行水平分裂，將進行水平分裂，將X3存入存入Sx中，現有中，現有3*（2+1）= 9 個

23、目錄項。目錄單元個目錄項。目錄單元DIR1，1和和DIR2，1 同指同指向向p1頁，頁，DIR1，2和和DIR2，2同指向同指向p3頁。原來頁。原來p5頁中的對象由于對象頁中的對象由于對象14的插的插入，分裂成了入，分裂成了p5和和p6兩頁，兩頁，DIR1，3指向指向p5，DIR2，3指向指向p6。對象。對象5有兩個有兩個索引項分別存儲在索引項分別存儲在p5和和p6兩頁中，對象兩頁中，對象6 有四個索引項分別存儲在有四個索引項分別存儲在p5、p6和和p3中。中。 圖圖7-8 對象對象14的插入的插入 網格文件索引網格文件索引2、插入對象、插入對象15圖圖7-9為目錄不分裂而磁盤頁溢出的情況。為

24、目錄不分裂而磁盤頁溢出的情況。插入前插入前DIR3，2和和DIR3，3同指向同指向p4，將對象，將對象15分別插入分別插入DIR3，2和和DIR3，3中。插入后中。插入后DIR3，2和和DIR3，3中的索引中的索引項均不超過項均不超過4個，目錄不用分裂，但磁盤頁個，目錄不用分裂，但磁盤頁p4溢出。創建新頁溢出。創建新頁p7，DIR3，2 指向指向p4，DIR3，3 指向指向p7。 圖圖7-9 對象對象15的插入的插入 網格文件索引網格文件索引（二）點查詢算法（二）點查詢算法 1、工作過程、工作過程 第一步：給定點坐標第一步：給定點坐標P(xp，yp)，沿，沿X，Y兩個兩個方向在方向在Sx和和S

25、y中查找中查找P(xp，yp)位置，得到含有位置，得到含有P的網格單元。的網格單元。第二步：進行一次磁盤操作將這個索引單元對第二步：進行一次磁盤操作將這個索引單元對應的磁盤頁調入內存，讀取該頁所存對象的應的磁盤頁調入內存，讀取該頁所存對象的(MBB，OID)，構成集合，構成集合E。對。對E中的每個對象中的每個對象e，測試，測試e.mbb是否含有點是否含有點P。第三步：對于包含點第三步：對于包含點P的的e.mbb，通過，通過e.oid獲取獲取其幾何邊界數據，精確測試其幾何邊界數據，精確測試P是否位于是否位于e.oid的幾何的幾何邊界之內。邊界之內。 網格文件索引網格文件索引2、例子：圖、例子：圖7-10為一個格網文件點查詢的例子。點為一個格網文件點查詢的例子。點P位于位于DIR3，2范圍之