空間索引結(jié)構(gòu)(學生)

1、第七章 空間索引結(jié)構(gòu)空間索引技術(shù)是從空間數(shù)據(jù)庫中獲取空間數(shù)據(jù)的有效方法，是提高空間數(shù)據(jù)查詢和各種空間分析效率的關(guān)鍵技術(shù)。建立空間索引是為了縮小空間數(shù)據(jù)的搜索范圍，以便在空間數(shù)據(jù)查詢時不必遍歷整個空間數(shù)據(jù)集，只訪問空間索引數(shù)據(jù)便可快速得到一條特定的空間查詢語句所請求的空間數(shù)據(jù)，或得到包含全部空間查詢結(jié)果的一個較小的空間數(shù)據(jù)集。索引文件中包含的數(shù)據(jù)稱為索引數(shù)據(jù)，索引結(jié)構(gòu)是索引數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)及索引創(chuàng)建與維護算法的總稱。空間索引結(jié)構(gòu)是按照空間數(shù)據(jù)在空間分布上的特性來組織和存儲索引數(shù)據(jù)的索引結(jié)構(gòu)。一種良好的空間索引結(jié)構(gòu)應滿足下列三個要求：一、存儲效率高：相對于被索引的數(shù)據(jù)集而言，索引數(shù)據(jù)的數(shù)據(jù)量應盡量小

2、。否則，訪問索引數(shù)據(jù)可能成為數(shù)據(jù)查詢與更新的效率瓶頸。二、查詢效率高：空間索引結(jié)構(gòu)需要選擇良好的索引數(shù)據(jù)結(jié)構(gòu)，設計具體的基于索引的空間訪問方法（SAM Spatial Access Method），必須能夠高效的實現(xiàn)以下幾種基于位置的查詢：1、點選擇：從數(shù)據(jù)集中找出包含給定點的所有空間對象。2、范圍查詢：查詢與給定對象間的距離小于某個給定值的所有空間對象。3、區(qū)域（窗口）查詢：查找含在區(qū)域內(nèi)、與區(qū)域相交或部分位于區(qū)域中的所有空間對象。窗口是一個特殊的區(qū)域，窗口查詢是GIS中最常用、最基本的查詢。4、K-最鄰近查詢：給定一個參照對象（點、線或區(qū)域），查詢距離參照對象最近的K ³ 1個空

3、間對象。5、空間關(guān)系查詢：相交、相鄰、包含等拓撲關(guān)系查詢，方位關(guān)系和基于距離的各種查詢。6、其他查詢：將滿足一定空間條件的兩個空間對象集合進行空間連接，空間集合運算等也是一種空間訪問。三、更新效率高：許多GIS應用中會涉及海量且不斷變化的空間數(shù)據(jù)集。數(shù)據(jù)集中數(shù)據(jù)對象的增加、修改和刪除將直接導致索引數(shù)據(jù)的更新，索引數(shù)據(jù)與被索引的數(shù)據(jù)集必須保持一致，才能保證基于索引數(shù)據(jù)的查詢結(jié)果的正確性。索引數(shù)據(jù)的更新操作包括：插入索引項，將新數(shù)據(jù)對象的索引項添加到索引數(shù)據(jù)中；刪除索引項，把數(shù)據(jù)對象的索引項從索引數(shù)據(jù)中刪除；修改索引項，在索引數(shù)據(jù)中先刪除再增加該數(shù)據(jù)對象的索引。數(shù)據(jù)集經(jīng)常變化時，要求其索引數(shù)據(jù)的更

4、新開銷不要很大，特別要避免更新時引起的索引重組。因此，需要考慮新增索引項和刪除索引項時，索引結(jié)構(gòu)的快速更新能力。很難設計一種空間索引結(jié)構(gòu)同時能夠提供高效的存儲、高效的查詢和高效的更新，實際應用中總是犧牲某些方面的效率來換取另外方面的效率。索引結(jié)構(gòu)可分為靜態(tài)索引和動態(tài)索引結(jié)構(gòu)。靜態(tài)索引結(jié)構(gòu)針對靜態(tài)不變的數(shù)據(jù)，索引只建一次，不需要更新，強調(diào)索引數(shù)據(jù)的存儲效率和查詢效率，不強調(diào)索引更新的效率。動態(tài)索引結(jié)構(gòu)強調(diào)數(shù)據(jù)在動態(tài)更新過程中保證較高的查詢效率和索引空間存儲效率，往往以犧牲索引更新效率為代價，這種犧牲是有限度的。索引結(jié)構(gòu)還分為內(nèi)存索引和外存索引，外存索引需要考慮磁盤頁面訪問的效率瓶頸問題。這里主要

5、研究面向海量空間數(shù)據(jù)的、2D空間對象的外存索引結(jié)構(gòu)。7.1空間索引分類非空間數(shù)據(jù)庫中存儲的數(shù)據(jù)為結(jié)構(gòu)化數(shù)據(jù)，通常以主關(guān)鍵字建立索引文件，以非主屬性建立倒排文件，索引項按自然數(shù)序列或字符順序排列?？臻g數(shù)據(jù)庫存儲的數(shù)據(jù)為結(jié)構(gòu)復雜、不能完全結(jié)構(gòu)化的空間數(shù)據(jù)，為了支持基于位置的各類查詢和分析，需要以表示空間對象幾何形狀的坐標數(shù)據(jù)為索引字段來建立空間索引。非空間數(shù)據(jù)庫的索引結(jié)構(gòu)不能滿足空間數(shù)據(jù)庫的索引需求，必須研究和設計專用的空間索引結(jié)構(gòu)和基于索引的空間訪問方法（SAM Spatial Access Method）。7.1.1非空間索引與SAM非空間索引結(jié)構(gòu)一般為B樹和hash文件結(jié)構(gòu)，這種索引結(jié)構(gòu)可以

6、準確的定位和查找所需數(shù)據(jù)，復雜度為對數(shù)函數(shù)。一、索引的假設和要求（一）B樹和hash文件結(jié)構(gòu)遵從的假設1、被索引的數(shù)據(jù)集所占空間遠遠大于內(nèi)存空間；2、磁盤訪問比內(nèi)存訪問慢得多；3、對象按物理頁分組，頁是內(nèi)存和外存交換數(shù)據(jù)的單位（大小為1K到4K），讀/寫一頁為一次I/O操作。4、訪問一個具體對象時，該對象所在頁可能在內(nèi)存中，或不在內(nèi)存中需要調(diào)入內(nèi)存。非空間數(shù)據(jù)庫的索引操作中，CPU時間與I/O操作時間相比可忽略不計，訪問方法的效率用I/O數(shù)衡量?？臻g索引的操作中，有些情況下需考慮CPU時間，但不考慮頁的緩存，使用一頁時才調(diào)入內(nèi)存。（二）SAM應滿足的要求空間索引是依據(jù)空間對象的空間位置、幾何形

7、狀及空間分布特征，按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu)。空間訪問方法SAM的設計基于B樹和hash表相同的假設，但B樹和hash表均不適合于空間索引。SAM應滿足下列要求：1、時間復雜度：點選擇和區(qū)域查詢應具有線性復雜度。SAM訪問一個數(shù)據(jù)集合的子集所用的時間，應小于以集合元素數(shù)量的線性函數(shù)為復雜度的序列查找算法。2、空間復雜度：如果被索引的集合占據(jù)n頁，索引的大小應該是n級的。3、空間索引結(jié)構(gòu)必須考慮動態(tài)性：適合于空間索引項的增加和刪除，大多數(shù)空間索引結(jié)構(gòu)在索引查找方面是高效的，復雜度為被索引集合中元素數(shù)量的對數(shù)。二、非空間數(shù)據(jù)庫中的B+樹索引B+樹是B樹的一個變種，B+樹是一個平衡樹，所有葉子位于

8、相同的深度。B+樹的每個結(jié)點為一個索引單元，存貯多個索引項，對應磁盤上一個物理頁，每個索引單元存貯索引項的數(shù)量由物理頁容量和索引項大小來確定。結(jié)點上每個索引項的內(nèi)容為KEY，PRT，葉結(jié)點的PRT指向關(guān)鍵字為KEY的數(shù)據(jù)對象，非葉結(jié)點的PRT指向孩子結(jié)點。每個結(jié)點中的索引項按關(guān)鍵字升序排序，非葉結(jié)點中每個索引項左子樹中的關(guān)鍵字小于等于該索引項的關(guān)鍵字，右子樹中的關(guān)鍵字大于該索引項的關(guān)鍵字。圖7.1為一個B+樹索引結(jié)構(gòu)的例子： 例子：有一組關(guān)鍵字集合2，3，7，9，10，13，15構(gòu)成的索引文件，索引數(shù)據(jù)采用B+樹結(jié)構(gòu)來組織。假設每個結(jié)點最多存貯四個索引項，結(jié)果如圖7.1a所示。 圖7-1 B樹

9、：（a）插入23,OID前，(b) 插入23,OID后1、索引的查找索引查找從樹根開始，通過比較關(guān)鍵字大小，查找相應的子樹，直到葉結(jié)點。一次查找中讀入物理頁的數(shù)量等于樹的深度，復雜度是被索引數(shù)據(jù)集大小的對數(shù)。2、插入索引項插入新的索引項E = 23，PRT。1）從根結(jié)點搜索，該索引項應插入到第二個葉子中。2）插入時該葉結(jié)點滿了，必須分裂，原結(jié)點的一部分索引項保留在原索引單元內(nèi)（9，10，13），另一部分索引項和E形成一個新的葉結(jié)點（15，23）。3）按照B+樹的定義，應將左邊葉結(jié)點（9，10，13）中最右邊一個關(guān)鍵字13插入父結(jié)點中，插入新索引項后的B+樹如圖7.1b所示，仍然是平衡樹。B+樹

10、是一種較好的外存空間索引結(jié)構(gòu)，時間復雜度是數(shù)據(jù)集合中元素數(shù)量的對數(shù)，空間復雜度使索引空間的利用率為50%以上，動態(tài)性能支持隨機插入和刪除。B+樹的上述優(yōu)點是以關(guān)鍵字有序為基礎的，空間數(shù)據(jù)不具備這樣的特點，不能簡單照搬。7.1.2 空間索引分類空間索引技術(shù)的基本原理是采用基于空間位置或基于空間對象的分割方法，把研究查詢空間劃分為若干區(qū)域，每個區(qū)域為一個索引單元，存儲多個空間對象的索引項?？紤]到空間位置上的鄰近度，按照空間位置鄰近的對象其索引項的位置也應該鄰近的原則來組織空間索引數(shù)據(jù)。空間索引支持的最主要的查詢是定位查詢和窗口查詢。一、空間對象的近似空間對象的幾何形狀錯綜復雜，表示幾何形狀的坐標序

11、列是變長的，直接以坐標序列為索引字段建立的空間索引，其索引項很長且變長。為此，需要將空間對象的形狀進行某種近似，平行于坐標軸的、包含特定空間對象的最小外接矩形MBB（Minimal Bounding Box）或MBR(Minimum Bounding Rectangle)就是空間對象幾何形狀的一種近似表示。以 MBB，OID 為索引字段建立空間索引，每個空間索引項具有固定的長度，最少包含三種成分MBB，OID，PRT，OID為對象標識，MBB為相應對象的最小外接矩形，PRT為指向幾何數(shù)據(jù)的指針，OID直接將MBB映射到存放幾何形狀和屬性的物理頁。 空間索引介于空間計算算法與空間數(shù)據(jù)之間，用于過

12、濾大量與空間計算無關(guān)的數(shù)據(jù)，以提高空間操作的效率。SAM只加速了索引項中MBB的查找（過濾），在此基礎上還要對幾何圖形進行精確查找?；诳臻g索引的空間查詢分兩步完成，第一步利用空間索引結(jié)構(gòu)和空間訪問方法SAM對數(shù)據(jù)集進行過濾（初選），在索引表中查找滿足查詢條件的MBB，結(jié)果為對象的一個超集（多個OID）。第二步對初選結(jié)果進行準確查找，在超集中通過空間計算算法，求取滿足查詢條件的精確對象。二、空間分割與空間索引單元劃分建立空間索引的第一步是按照一定的方式將被查詢空間分割成多個索引單元。有兩種對空間進行劃分的方法，形成兩大類空間索引結(jié)構(gòu)，很多SAM都屬于這兩類結(jié)構(gòu)之一。1、空間驅(qū)動結(jié)構(gòu)：采用基于空

13、間位置的分割方法，將研究區(qū)域的2D空間進行完全劃分，劃分為多個矩形或正方形范圍，每個范圍定義為一個空間索引單元，對象在2D空間的分布是獨立的，對象按一定原則分配到不同的矩形單元。也可將研究區(qū)域的2D空間劃分為多個凸多邊形范圍，每個凸多邊形近似表示一個空間對象的幾何形狀。例如：將研究空間用規(guī)則的正方形格網(wǎng)進行分割，每個正方形網(wǎng)格為一個空間索引單元，索引多個空間對象?？臻g對象覆蓋多個相鄰的空間索引單元時，在其覆蓋的每個索引單元中各有一個索引項，索引項中包含空間對象標識OID。2、數(shù)據(jù)驅(qū)動結(jié)構(gòu)：是一種基于對象的分割，對2D研究區(qū)域的空間分割直接由分布在其中的空間對象來確定，對空間對象集合進行分割。每

14、個空間對象用它的最小外接矩形MBB近似表示，每個空間索引單元的形狀也是一個矩形區(qū)域，它包含多個空間對象的最小外接矩形MBB?？臻g索引單元的面積大小取決于其索引的空間對象集合的面積、形狀和分布，索引單元中存儲空間對象的最小外接矩形MBB?；趯ο蟮姆指畈皇强臻g的一種完全劃分。三、空間索引結(jié)構(gòu)的具體分類綜合現(xiàn)有研究及參考文獻，可將主要的空間索引技術(shù)分類如下：R樹點對象線性四叉樹空間索引非線性索引線性索引網(wǎng)格空間索引基于樹的索引基于凸多邊形基于約束基于MBBR樹系列樹CELL系列BSP樹CELL樹CP樹OS-CELL樹PR樹GPR樹LUR樹R+樹R*樹R-Link樹Qr樹Sr樹TV樹X樹SDR樹線性

15、映射結(jié)構(gòu)網(wǎng)格文件圖7-2 空間索引分類索引結(jié)構(gòu)中，如果將2D或3D分布的空間索引單元，按照一定的方式組織成線性形式，相應的索引稱為線性空間索引。相反，以非線性形式來組織空間索引單元，相應的索引稱為非線性空間索引。一、線性索引線性索引主要有線性映射結(jié)構(gòu)與線性四叉樹。1、線性映射結(jié)構(gòu)：首先，用均勻或不均勻的正方形格網(wǎng)對被索引空間區(qū)域進行劃分；然后，采用填充曲線對索引空間進行填充（如Hilbert Curve曲線），取填充曲線編碼為索引單元的序號，將索引單元按序號排序建立線性索引結(jié)構(gòu)。這里，空間劃分是基于位置的完全劃分，建立的索引為空間驅(qū)動的、線性組織的、規(guī)則的網(wǎng)格空間索引結(jié)構(gòu)。2、線性四叉樹：每一

16、個空間對象用其MBB近似表示，對含有MBB集合的空間進行四叉樹劃分，劃分后的不均勻網(wǎng)格作為索引單元，每個單元分別編號，葉結(jié)點根據(jù)編號組織成B-樹結(jié)構(gòu)，這種結(jié)構(gòu)叫線性四叉樹。二、非線性索引非線性空間索引按索引的邏輯組織方式分成網(wǎng)格空間索引和基于樹的空間索引。（一）網(wǎng)格空間索引網(wǎng)格空間索引簡稱稱網(wǎng)格索引，是基于位置的空間驅(qū)動結(jié)構(gòu)。它將被索引空間用平行于坐標軸的橫豎線條劃分成大小相等或不等的網(wǎng)格，每個網(wǎng)格為一個索引單元，記錄每個網(wǎng)格所包含的多個對象的標識?？臻g查詢時，先計算出對象所在的網(wǎng)格，然后在網(wǎng)格中快速查詢對象。網(wǎng)格索引分為均勻網(wǎng)格索引和網(wǎng)格文件索引，可以索引點對象及用MBB近似的其他類型的空間

17、對象。網(wǎng)格索引以二維數(shù)組結(jié)構(gòu)來存儲，是一種非線性空間索引結(jié)構(gòu)。（二）基于樹的空間索引基于樹的空間索引是一種基于對象的數(shù)據(jù)驅(qū)動結(jié)構(gòu)。首先采用某種幾何形狀近似算法，將被索引空間中的空間對象表示為其近似體，然后將近似體按確定規(guī)則組織成樹形結(jié)構(gòu)?；跇涞目臻g索引按幾何形狀近似技術(shù)的不同可分為基于凸多邊形的空間索引、基于約束的空間索引和基于MBB的空間索引。1、基于凸多邊形的空間索引基于凸多邊形的空間索引又稱劃分樹結(jié)構(gòu)，它將被索引空間劃分成凸多邊形，然后再對凸多邊形進行同樣的劃分，直到該劃分滿足特定精度為止。用凸多邊形近似表示對象的形狀。（1）BSP樹 BSP樹是一種二叉樹，它將被索引空間逐級進行一分為

18、二的劃分，形成一棵二叉樹BSP樹。（2）CELL樹、CP樹、OS-CELL樹 CELL樹與BSP樹相似，BSP樹將被索引空間一分為二，CELL樹則將被索引空間劃分成多個凸多邊形，然后依次再對每個凸多邊形進行相似的劃分，直到到達預定的精度為止，CELL樹是一棵多叉樹。CELL樹與BSP樹的相同之處是子空間相互間不覆蓋，優(yōu)點是磁盤1/0次數(shù)較少，但索引項中凸多邊形的存儲需較多空間，且進行幾何形狀的精確匹配時計算也較復雜。 CP樹是CELL樹的一種變種樹，采用CELL樹同樣的空間劃分方法，但允許子空間部分覆蓋。特點是與R樹相比，具有較小的子空間覆蓋面積，磁盤1/0次數(shù)較少，同樣索引項中對凸多邊形的存

19、儲需較多的空間，且進行空間對象的精確匹配時計算較復雜。 OS-CELL樹也是CELL樹的一種變種樹，只是針對CELL樹中存在的特大空間對象，對CELL樹進行改進、完善和優(yōu)化。由于特大空間對象占據(jù)較大的被索引空間，其在CELL樹中可能會被分割成多個凸多邊形，當特大空間對象較多時，CELL樹的葉節(jié)點分裂會相當頻繁，使CELL樹的重構(gòu)時間增多，有效訪問速度變慢；每個特大空間對象可能存放到多個磁盤塊中，增加CELL樹的高度，從而增加磁盤1/ 0次數(shù)，惡化CELL樹的搜索性能。OS-CELL樹分配特大盤塊專用于存儲特大空間對象，在父節(jié)點中添加指向該特大盤塊的指針。對普通幾何對象而言，OS-CELL樹的特

20、點與CELL樹相同。2、基于約束的空間索引其代表O樹采用空間近似算法，將幾何對象按axby=c(a，b)，c (a，b) (-1，0，1)表示為一組約束表達式，相應于笛卡爾坐標空間中的六條曲線中的某種組合，然后根據(jù)空間對象間的空間關(guān)系建立空間索引樹。特點是能夠自然地表示空間對象間的空間關(guān)系，但對空間對象的精確匹配需較多的計算。3、基于MBB的空間索引基于MBB的樹狀空間索引均將空間對象近似為其MBB，根據(jù)MBB間的空間關(guān)系建立相應的樹形結(jié)構(gòu)，這類空間索引主要指R樹系列。自1984年Guttman提出R樹以來，學者根據(jù)不同應用對R樹的需求，對R樹進行了各種改進，形成了諸多R樹的變種，如圖7-2所

21、示。當前主要的空間索引結(jié)構(gòu)歸納為網(wǎng)格索引、線性四叉樹、R樹結(jié)構(gòu)、劃分樹結(jié)構(gòu)和線性映射結(jié)構(gòu)等類型。本章主要探討這幾類空間索引的索引結(jié)構(gòu)，索引建立和簡單的查詢操作。7.2 空間驅(qū)動的索引結(jié)構(gòu)空間驅(qū)動索引結(jié)構(gòu)的主要特征是采用某種格網(wǎng)對2D空間進行劃分，將空間劃分成小區(qū)域，每個小區(qū)域為一個索引單元，每個索引單元索引多個空間對象。索引單元按照一定的數(shù)據(jù)結(jié)構(gòu)來組織，如果組織成線性結(jié)構(gòu)，則相應的空間索引為線性索引，如果組織成非線性結(jié)構(gòu)，則相應的空間索引為非線性索引。即空間驅(qū)動結(jié)構(gòu)既包含線性索引，也包含非線性索引，非線性結(jié)構(gòu)主要有網(wǎng)格索引，線性結(jié)構(gòu)有線性四叉樹和線性映射結(jié)構(gòu)。7.2.1網(wǎng)格索引網(wǎng)格索引是一種空

22、間驅(qū)動的非線性索引結(jié)構(gòu)，其基本特征是用正方形或矩形格網(wǎng)對研究區(qū)域的2D空間進行劃分，每個網(wǎng)格單元為一個索引單元，索引多個空間對象，索引單元按行列號組織成2D目錄。網(wǎng)格索引包括均勻網(wǎng)格索引和網(wǎng)格文件索引，均勻網(wǎng)格適合于索引空間點對象；網(wǎng)格文件是均勻網(wǎng)格的改進，是一種多關(guān)鍵字索引，可索引點對象和對象的MBB，能夠與B+樹簡單集成，在商用數(shù)據(jù)庫Oracle中已實現(xiàn)。一、均勻網(wǎng)格（一）均勻網(wǎng)格的特征設幾何對象均為點對象。研究區(qū)域為一個大小的空間，將其劃分為個相同大小的網(wǎng)格，每個網(wǎng)格的邊長為，起始坐標為。每個網(wǎng)格為一個索引單元，對應于磁盤上一個物理頁，每個網(wǎng)格中的點存入相應的磁盤頁中。如圖7-3，索引目

23、錄表為一個2D數(shù)組DIR，每個目錄項DIRi，j含有頁標識PageID。圖7-3 均勻網(wǎng)格（二）基于均勻網(wǎng)格索引的空間訪問1、插入新點：假設新點的坐標為（x，y），計算新點所在網(wǎng)格（索引單元）的行列號，。新點的索引目錄項為DIRi，j，假設對應的磁盤頁DIRi，j.PageID為(a，b)所在的頁P(a，b)，將新點插入P(a，b)頁中。2、點查詢：假設鼠標當前位置的坐標為 (x，y)，計算鼠標位置所屬索引單元的行列號和，讀入對應的磁盤頁DIRi，j.PageID，掃描該頁中所有點對象，判斷哪些點對象與(x，y)點重疊。3、窗口查詢：計算窗口W覆蓋的網(wǎng)格集合S=，對S中的每個讀取DIRi，j.

24、PageID，返回這些頁中包含的所有點對象，即為窗口W范圍內(nèi)包含的點對象。 如果目錄在內(nèi)存中，點查詢只需一次I/O。窗口查詢的I/O數(shù)與窗口覆蓋的網(wǎng)格數(shù)成正比。格網(wǎng)分辨率的選擇取決于被索引點對象的數(shù)量。假設共有N個點對象，每頁存儲的最大點數(shù)為M，則至少需要有N/M個網(wǎng)格。如果某個網(wǎng)格中的點數(shù)超過M，多出的點放到溢出區(qū)，溢出區(qū)與索引區(qū)域用指針相連。如圖7-4中例子，每個網(wǎng)格所存的最大點數(shù)M=4，k,l,m,n,o五個點對象位于同一個網(wǎng)格中，對應于磁盤頁P。將k,l,m,n四個點放入P頁，o放入溢出區(qū)，將溢出區(qū)與P頁相連。所有的網(wǎng)格共用一個溢出區(qū)，溢出區(qū)可能由多個磁盤頁連接成溢出區(qū)鏈。如果o點存儲

25、在溢出區(qū)鏈的第q頁，則點查詢的I/O數(shù)為q。最壞的情況下，所有點都位于同一網(wǎng)格中，索引結(jié)構(gòu)為磁盤頁的線性列。點的頻繁插入會導致較長的溢出鏈，而點刪除會導致空頁。對于某些具體分布，這種索引不能滿足磁盤存儲的要求。圖7-4 均勻網(wǎng)格中的溢出頁二、點對象的格網(wǎng)文件格網(wǎng)文件與均勻格網(wǎng)的相同之處是采用平行于坐標軸的格網(wǎng)對空間進行完全劃分，每個網(wǎng)格單元為一個索引單元，索引單元組織成2D目錄形式。與均勻格網(wǎng)不同的是，每次發(fā)生溢出時，動態(tài)的將網(wǎng)格單元在橫向或縱向上分裂為兩個單元，可根據(jù)網(wǎng)格單元中點對象的分布情況來選擇進行縱向還是橫向劃分；網(wǎng)格文件中的網(wǎng)格單元為大小不相同的矩形單元，多個網(wǎng)格單元可對應同一個磁盤

26、頁。 （一）格網(wǎng)文件的數(shù)據(jù)結(jié)構(gòu) 格網(wǎng)文件由三種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，索引目錄DIR是一種與均勻網(wǎng)格中的索引目錄類似的2D數(shù)組，差別是兩個相鄰單元可共享同一磁盤頁；是兩個線性數(shù)組，表示沿兩坐標軸的劃分。圖7-5中的例子描述了這種結(jié)構(gòu)，假設網(wǎng)格的最大容量M=4。圖7-5均勻網(wǎng)格文件的插入（二）構(gòu)建網(wǎng)格文件的步驟第一步：只有四個對象，目錄中只有一個網(wǎng)格c指向p1頁。第二步：插入點a、b、c。1、在網(wǎng)格c插入a時，p1溢出。2、在中的處將網(wǎng)格c垂直劃分成兩個單元和，將c中原有的4個點劃分到和兩個單元中。3、創(chuàng)建一個新磁盤頁p2，指向 p1頁，指向p2頁。4、將a和b插入單元對應的p1頁，c插入單元對應的p2

27、頁。 第三步：插入d1、在單元中插入點d時p1溢出。2、在中的處將和單元進行水平劃分，水平劃分為和。3、創(chuàng)建一個新磁盤頁p3，將p1中原有4個點劃分到p1和p3中，指向p1，指向p3。將點d插入單元對應的p1頁。此時，水平線將沒溢出的單元也水平劃分為兩個單元和，和指向同一個磁盤頁p2。第四步：插入e和f兩點。1、將e和f分別插入和單元，和沒溢出，而p2溢出。2、分配一個新頁p4。存入p4，存入p2。 （三）插入一個點時可能的三種情況 1、網(wǎng)格單元不分裂：磁盤頁沒滿，只需讀入頁，插入點。 2、網(wǎng)格單元不分裂但磁盤頁溢出：點n插入單元c時，與c相關(guān)聯(lián)的磁盤頁p滿了，但p由多個單元引用。此時分配一個

28、新頁，將p頁中含在c單元里的點和新點n分配給新頁，c單元的索引目錄指向。 3、單元分裂且磁盤頁溢出：新點插入時磁盤頁滿，且該頁只有一個網(wǎng)格單元引用，此時網(wǎng)格單元沿x或y分裂。以沿x軸分裂為例：（1）在處分成和（該列的所有單元均分為兩個），將分裂點的位置插入中。（2）創(chuàng)建一個新物理頁，將原來中的點和新插入的點分配到和中，分別指向p和。（3）DIR中所有列號> i的列，都將列號+1。創(chuàng)建一個索引列號為“i +1”的新索引項。對所有的行，新單元與指向相同的物理頁。格網(wǎng)文件克服了均勻網(wǎng)格的主要缺陷，點查詢通過兩次I/O操作就可完成（訪問目錄對應的頁和讀頁數(shù)據(jù)）。該結(jié)構(gòu)是動態(tài)的，缺點是對于大數(shù)據(jù)集

29、，目錄會大到內(nèi)存放不下的程度。三、格網(wǎng)文件索引MBB用網(wǎng)格文件對MBB進行索引，最簡單的情況是每個覆蓋MBB的網(wǎng)格單元都保存該MBB的索引項。MBB與網(wǎng)格單元的關(guān)系有三種：MBB包含網(wǎng)格單元、網(wǎng)格單元與MBB相交、網(wǎng)格單元包含MBB。前兩種情況，每個網(wǎng)格單元都建立MBB的索引項，一個MBB有多項索引。例子：有15個MBB，每頁的最大容量為4。圖7-6為用均勻網(wǎng)格建立的索引：圖7-6 基于MBB的均勻網(wǎng)格索引圖7-7為用網(wǎng)格文件建立的索引：圖7-7 基于網(wǎng)格文件的MBB索引對象的插入、刪除與點索引相同，只是一個MBB可能具有多個索引項，分裂會更頻繁。（一）索引項插入1、插入對象14如圖7-8，將

30、對象14插入圖7-7中的索引單元DIR1，3時，DIR1，3中的索引項超過4項，對應的磁盤頁p5也溢出。在處對DIR1，3進行水平分裂，將存入中，現(xiàn)有3*（2+1）= 9 個目錄項。目錄單元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為目錄不分裂而磁盤頁溢出的情況。插入前DIR3，2和DIR3，3同指向p4，將

31、對象15分別插入DIR3，2和DIR3，3中。插入后DIR3，2和DIR3，3中的索引項均不超過4個，目錄不用分裂，但磁盤頁p4溢出。創(chuàng)建新頁p7，DIR3，2 指向p4，DIR3，3 指向p7。圖7-9 對象15的插入（二）點查詢算法1、工作過程第一步：給定點坐標P(xp，yp)，查找含有P的網(wǎng)格單元。對于均勻網(wǎng)格索引來說是常數(shù)時間，若用網(wǎng)格文件則分X，Y兩個方向查找，復雜度是對數(shù)函數(shù)。第二步：進行一次磁盤操作將這個索引單元對應的磁盤頁調(diào)入內(nèi)存，讀取該頁所存對象的(MBB，OID)，構(gòu)成集合E。對E中的每個對象e，測試e.mbb是否含有點P。第三步：對于包含點P的e.mbb，通過e.oid獲

32、取其幾何邊界數(shù)據(jù)，精確測試P是否位于e.oid的幾何邊界之內(nèi)。2、例子圖7-10為一個格網(wǎng)文件點查詢的例子。點P位于DIR3，2范圍之內(nèi)，對應的磁盤頁p4中含有4個索引項。將p4頁調(diào)入內(nèi)存，對其包含的4個mbb分別進行測試，其中8和12的mbb中包含了點P。根據(jù)對象標識8和12取出各自的幾何邊界數(shù)據(jù)，精確測試對象8和12，求出包含點P的對象。點查詢的I/O數(shù)是常數(shù)。圖7-10 基于網(wǎng)格文件的點查詢（三）窗口查詢算法工作過程如下：第一步：計算所有覆蓋窗口的索引單元。第二步：掃描每一個索引單元，調(diào)入相應的磁盤頁。讀入每個磁盤頁中的對象，排序并去掉重復對象。求出那些落入窗口中，或與窗口相交的mbb。

33、第三步：根據(jù)各自的對象標識取出這些mbb對應的幾何邊界，精確檢測每個對象是否位于窗口中或與窗口相交。窗口查詢的I/Os與窗口的面積成正比。（四）總結(jié)用網(wǎng)格文件索引MBB，大多數(shù)情況下比較理想，但也存在很多問題：1、對象的多重索引增加了索引表的容量，數(shù)據(jù)集越大越嚴重，索引單元接近MBB大小時，情況就更嚴重。2、索引表容量越大，查詢重復項的代價越高。3、算法的效率依賴于索引表位于內(nèi)存中的假設，如果索引表很大，一部分要存入磁盤，管理將變得復雜，效率會受影響。7. 3數(shù)據(jù)驅(qū)動的索引結(jié)構(gòu)空間驅(qū)動的索引結(jié)構(gòu)將整個空間劃分成小區(qū)域，每個小區(qū)域定義為一個索引單元，直接索引其中的空間對象或索引對象的MBB。數(shù)據(jù)

34、驅(qū)動的索引結(jié)構(gòu)則按照空間對象的位置、范圍和分布，來確定索引單元的位置和范圍，索引單元的全集不一定覆蓋整個空間。這里主要介紹R樹系列和劃分樹。7.3.1 R樹 R樹是一種數(shù)據(jù)驅(qū)動的索引結(jié)構(gòu)，是B樹的擴展。與B樹相比，R樹是一棵由多層嵌套的外接矩形構(gòu)成的平衡樹，即R樹的每個結(jié)點以范圍矩形mbb或目錄矩形dr的形式表示一個空間范圍，它界定了一個空間索引區(qū)域，定義為一個空間索引單元。R樹的每個結(jié)點都是一個空間索引單元，非葉結(jié)點包含其多顆子樹的索引項，葉結(jié)點包含多個數(shù)據(jù)對象的索引項，本結(jié)點的范圍矩形作為自身索引項的一部分存儲在它的上層結(jié)點中。R樹的每個結(jié)點對應一個物理頁，每個結(jié)點只能包含k個索引項，mk

35、M，M是R樹結(jié)點中包含索引項的最大數(shù)目，m是R樹結(jié)點中包含索引項的最小數(shù)目，并限制2 £ m £ M/2。一、原始的R樹R樹的基本結(jié)構(gòu)是一棵多層嵌套的、由外接矩形構(gòu)成的平衡樹。每個結(jié)點的索引區(qū)域表示成一個范圍矩形，每個結(jié)點為一個空間索引單元，每個索引單元有k個索引項。葉結(jié)點的范圍矩形為其內(nèi)部多個數(shù)據(jù)對象mbb的最小外接矩形，非葉結(jié)點的范圍矩形為其多個子結(jié)點范圍矩形mbb的最小外接矩形。葉結(jié)點中存放多個數(shù)據(jù)對象的索引項，每個索引項的形式為ptr，mbb，oid，其中oid是數(shù)據(jù)對象的標識，mbb是數(shù)據(jù)對象的外接矩形，ptr指向存儲該對象幾何形狀數(shù)據(jù)的磁盤位置。非葉結(jié)點中存放多

36、個子結(jié)點索引項，每個索引項的形式為ptr，mbb，nodeid，其中nodeid是指向子結(jié)點的指針，mbb為子樹的目錄矩形dr，ptr是子結(jié)點對應的磁盤頁地址。（一）R樹的性質(zhì)1、根結(jié)點至少有兩個子結(jié)點；2、所有的葉結(jié)點都處于同一層；3、除根結(jié)點外，R樹中所有結(jié)點包含的索引項數(shù)目均在m，M之間，并限制2 £m£M/2。圖7-26顯示一棵m=2，M=4的R樹。M的大小取決于索引項大小Size(E)和磁盤頁大小Size(P)，。通常oid大于nodeid，因而，非葉結(jié)點和葉結(jié)點的M不同。給定M和m后，一個深度為d的R樹最少可索引個對象，至多可索引個對象。相反，要索引N個對象，R

37、樹的深度最大為，最小為。假設頁的大小為4K，索引項的大小為20B（16B為mbb，4B為oid），m設為頁容量的40%，則，。這種情況下，深度為1時可索引至少81*81=6561個對象，深度為2可索引81*81*81=531441到204*204*204=8489664個對象。對于million個對象，只需要三層，即訪問三個磁盤頁就可到達樹葉，再讀取相應的對象即可。（二）R樹查詢效率的優(yōu)化R樹允許兄弟結(jié)點間有區(qū)域重疊，因此，查詢一個對象可能要訪問多個分支，這是影響R樹查詢效率的主要因素。對R樹查詢效率的優(yōu)化可考慮如下參數(shù)：1、查詢區(qū)域：查詢條件所覆蓋的區(qū)域。2、重疊區(qū)域：兄弟結(jié)點間范圍矩形相互

38、重疊的區(qū)域。重疊區(qū)域減少時，查詢區(qū)域與重疊區(qū)域相交的概率減少，可減少查詢時訪問的分支數(shù)。3、死區(qū)域：被結(jié)點范圍矩形覆蓋但不被其子結(jié)點范圍矩形覆蓋的區(qū)域。死區(qū)域減少時，屬于結(jié)點范圍內(nèi)的查詢區(qū)域與其子結(jié)點范圍矩形相交的概率增大，在該分支上找到目標數(shù)據(jù)的概率也增大，提高了分支選擇的準確性。4、范圍矩形周長：結(jié)點范圍矩形四邊長度之和。對于面積固定的矩形，周長越小，其形狀越接近正方形，正方形的空間聚簇性好，易于填滿父結(jié)點的范圍矩形，所以減少子結(jié)點的范圍矩形周長可減少父結(jié)點的死區(qū)域。5、結(jié)點利用率：結(jié)點的實際子結(jié)點數(shù)（或數(shù)據(jù)對象數(shù)）與最大子結(jié)點數(shù)（或數(shù)據(jù)對象數(shù)）之比。提高結(jié)點利用率可降低樹的平均高度，對于

39、大區(qū)域查詢，滿足條件的數(shù)據(jù)對象數(shù)目很大，結(jié)點利用率高可在很大程度上減少結(jié)點訪問數(shù)，從而提高查詢效率。上述優(yōu)化參數(shù)有些相容，有些互斥。一般來說，減少死區(qū)域的同時可能也減少了重疊區(qū)域，兩者是相容的。而為了減少死區(qū)域，則要求結(jié)點的子結(jié)點數(shù)目能更自由，結(jié)點利用率可能會降低。減少死區(qū)域和減少重疊區(qū)域都要求結(jié)點外接矩形的形狀更自由，結(jié)點范圍就可能無法接近正方形。對于任意幾何形狀，減少周長一般也會影響到結(jié)點利用率，接近正方形的外接矩形更容易填滿父結(jié)點范圍矩形，也容易提高結(jié)點利用率。對于大區(qū)域查詢，結(jié)點利用率對查詢的影響遠遠大于其他三個因素。（三）基于R樹的查詢點查詢和窗口查詢幾乎完全一樣，這里只介紹點查詢。

40、函數(shù)RTpointQuery實現(xiàn)兩步：1、在每一層中查找各結(jié)點中所有含P點的子結(jié)點，因為外接矩形可以重疊，滿足條件的子結(jié)點可能有多個，相同的方法直到葉結(jié)點。訪問每個結(jié)點時可能發(fā)生兩種情況：（1）該結(jié)點不包含P，即P落在非葉結(jié)點范圍矩形的死區(qū)域，查找終止。（2）P點包含在該結(jié)點多個子結(jié)點的mbb中，這時要搜索每一棵子樹，直到葉結(jié)點。2、順序掃描第一步得到的所有葉結(jié)點，所有包含P點的數(shù)據(jù)對象的索引項mbb即為所求。圖7-26顯示了點查詢的例子，查詢訪問了R，b，c，d四個結(jié)點，P點含在對象8和12的mbb中。圖7-26 基于R-樹的點查詢（三）R樹的插入操作1、插入步驟（1）從根結(jié)點向葉子搜索，如

41、某個結(jié)點的范圍矩形包含被插入對象的mbb，則繼續(xù)查找其子樹，如果不包含則終止，重復此過程直到葉結(jié)點。（2）如果葉結(jié)點未滿，則將新對象的mbb，oid插入葉結(jié)點；如果葉結(jié)點已滿，則將葉結(jié)點分為裂為兩頁（重構(gòu)的范圍矩形），將M+1個索引項分配到兩頁中，在父結(jié)點f中修改的索引項（的范圍矩形有變化），并插入的索引項。如果父結(jié)點f也滿了，則重復上述的分裂，最壞的情況是直到根，此時樹的深度增加一級。圖7-27 對象15的插入2、插入舉例（設M=4）（1）在圖7-26中插入對象15：葉結(jié)點d的范圍矩形中包含對象15的mbb，d中原有的索引項為11，12，13，將對象15直接插入葉結(jié)點d中，重構(gòu)d結(jié)點的范圍矩形，并改變d結(jié)點在根結(jié)點R中的索引項，插入結(jié)果如圖7-27所示。（2）在圖7-27中插入對象16：葉結(jié)點b的范圍矩形中包含對象16的mbb，將對象16插入到葉結(jié)點b中。b中原有的索引項為3，4，7，10，b結(jié)點滿了，應分裂為b和e兩個結(jié)點，將3，4，7分配在b中，10，16分配在e中。重構(gòu)結(jié)點b的范圍矩形，修改b在根結(jié)點R中的索引項。生成e的范圍矩形，將e的索引項插入根結(jié)點R中。此時根結(jié)點R已滿，將根結(jié)點R