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

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

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

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

4、求其索引數(shù) 據(jù)的更新開銷不要很大，特別耍避免更新時(shí)w起的索引重組。a此，需?？紤]新增索4項(xiàng)和刪 除索引項(xiàng)時(shí)，索引結(jié)構(gòu)的快速更新能力。很難設(shè)計(jì)一種空問索引結(jié)構(gòu)同時(shí)能夠提供高效的存儲(chǔ)、高效的查詢和高效的更新，實(shí)際應(yīng) 用中總是犧牲某些方面的效率來換取另外方面的效率。索引結(jié)構(gòu)可分為靜態(tài)索引和動(dòng)態(tài)索引結(jié)構(gòu)。靜態(tài)索引結(jié)構(gòu)針對靜態(tài)不變的數(shù)裾，索引只建 一次，不需要更新，強(qiáng)調(diào)索引數(shù)據(jù)的存儲(chǔ)效率和查詢效率，不強(qiáng)調(diào)索引更新的效率。動(dòng)態(tài)索引 結(jié)構(gòu)強(qiáng)調(diào)數(shù)裾在動(dòng)態(tài)史新過程中保證較高的查詢效率和索引空間存儲(chǔ)效率，往往以犧牲索引史 新效率為代價(jià)，這種犧牲是宥限度的。索引結(jié)構(gòu)還分為內(nèi)存索引和外存索引，外存索引需要考慮磁盤頁而

5、訪問的效率瓶頸問題。 這里主要研究面向海a空問數(shù)據(jù)的、2d空問對象的外存索引結(jié)構(gòu)。7.1空間索引分類非空間數(shù)據(jù)庫中存儲(chǔ)的數(shù)據(jù)力結(jié)構(gòu)化數(shù)據(jù)，通常以主關(guān)鍵字建立索引文件，以非主屬性建 立倒排文件，索引項(xiàng)按自然數(shù)序列或字符順序排列。空間數(shù)據(jù)庫存儲(chǔ)的數(shù)據(jù)為結(jié)構(gòu)復(fù)雜、不能 完全結(jié)構(gòu)化的空間數(shù)據(jù)，為了支持基于位置的各類査洵和分析，需要以表示空間對象幾何形狀 的坐標(biāo)數(shù)據(jù)為索引字段來建立空間索引。非空間數(shù)據(jù)庫的索引結(jié)構(gòu)不能滿足空間數(shù)裾庫的索引 需求，必須研允和設(shè)計(jì)專用的空間索引結(jié)構(gòu)和基于索引的空間訪問方法（sam spatial accessmethod)7.1.1非空間索引與sam非空間索引結(jié)構(gòu)一般為b樹和

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

7、求空間索引是依據(jù)空間對象的空間位置、幾何形狀及空間分布特征，按一定順序排列的一種 數(shù)據(jù)結(jié)構(gòu)。空間訪問方法sam的設(shè)計(jì)基于b樹和hash表相同的假設(shè)，但b樹和hash表均不 適合于空間索引。sam應(yīng)滿足下列要求：1、時(shí)問復(fù)雜度：點(diǎn)選擇和區(qū)域查詢應(yīng)具有線性復(fù)雜度。sam訪問一個(gè)數(shù)據(jù)集合的子集所 用的吋間，應(yīng)小于以集合元素?cái)?shù)量的線性函數(shù)為«雜度的序列查找兌法。2、空問復(fù)雜度：如果被索引的集合占據(jù)n頁，索引的大小應(yīng)該是n級的。3、空問索引結(jié)構(gòu)必須考慮動(dòng)態(tài)性：適合于空問索引項(xiàng)的增加和刪除，大多數(shù)空間索引結(jié)構(gòu) 在索引查找方面是高效的，復(fù)雜度為被索引集合中元素?cái)?shù)量的對數(shù)。二、非空問數(shù)據(jù)庫中的b4樹

8、索引b+樹是b樹的一個(gè)變種，b+樹是一個(gè)平衡樹，所有葉子位于相同的深度。b+樹的每個(gè)結(jié) 點(diǎn)為一個(gè)索引單元，存貯多個(gè)索引項(xiàng)，對應(yīng)磁盤上一個(gè)物理頁，每個(gè)索引單元存貯索引項(xiàng)的數(shù) 量由物理頁容量和索引項(xiàng)大小來確定。結(jié)點(diǎn)上每個(gè)索引項(xiàng)的內(nèi)容力key，prtj,葉結(jié)點(diǎn)的prt 指向關(guān)鍵字為key的數(shù)據(jù)對象，非葉結(jié)點(diǎn)的prt指向孩子結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)中的索引項(xiàng)按關(guān)鍵 字升序排序，非葉結(jié)點(diǎn)中每個(gè)索引項(xiàng)左子樹中的關(guān)鍵字小于等于該索引項(xiàng)的關(guān)鍵字，右子樹中 的關(guān)鍵字大于該索引項(xiàng)的關(guān)鍵字。圖7.1為一個(gè)b+樹索引結(jié)構(gòu)的例子：例子：有一組關(guān)鍵字集合2, 3, 7, 9，10，13, 15構(gòu)成的索引文件，索引數(shù)據(jù)采用b+ 樹結(jié)

9、構(gòu)來組織。假設(shè)每個(gè)結(jié)點(diǎn)最多存貯四個(gè)索引項(xiàng)，結(jié)果如圖7.1a所示。1、索引的查找索引查找從樹根開始，通過比較關(guān)鍵字大小，查找相應(yīng)的子樹，直到葉結(jié)點(diǎn)。一次查找中 讀入物理頁的數(shù)量等于樹的深度，復(fù)雜度是被索引數(shù)據(jù)集大小的對數(shù)。2、插入索引項(xiàng)插入新的索引項(xiàng)已=23, prt。i）從根結(jié)點(diǎn)搜索，該索引項(xiàng)應(yīng)插入到第二個(gè)葉子中。2）插入?yún)荚撊~結(jié)點(diǎn)滿了，必須分裂，原結(jié)點(diǎn)的一部分索引項(xiàng)保留在原索引單元內(nèi)（9, 10, 13）,另一部分索引項(xiàng)和e形成一個(gè)新的葉結(jié)點(diǎn)（15, 23）。3）按照b+樹的定義，應(yīng)將左邊葉結(jié)點(diǎn)（9，10，13）中最右邊一個(gè)關(guān)鍵字13插入父結(jié)點(diǎn) 中，插入新索引項(xiàng)后的b+樹如圖7.1b所示，仍

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

11、錯(cuò)綜復(fù)雜，表示幾何形狀的坐標(biāo)序列是變長的，直接以華標(biāo)序列力索 引字段建立的空間索引，其索引項(xiàng)很長且變長。為此，需要將空間對象的形狀進(jìn)行某種近似， 平行于坐標(biāo)軸的、包含特定空間對象的最小外接矩形mbb （minimal bounding box ）或 mbr（minimum bounding rectangle）就是空間對象兒何形狀的一種近似表示。以mbb，0id為索引字段建立空間索引，每個(gè)空間索引項(xiàng)具有固定的長度，最少包含 三種成分mbb, oid, prt, oid為對象標(biāo)識(shí)，mbb為相應(yīng)對象的最小外接矩形，prt為指 向幾何數(shù)據(jù)的指針，0id直接將mbb映射到存放幾何形狀和屬性的物理貞?？?/p>

12、閭索引介于空問計(jì)算算法與空|'uj數(shù)據(jù)之間，用于過濾大£1與空閬計(jì)算無關(guān)的數(shù)據(jù)，以提 高空間操作的效率。sam只加速了索引項(xiàng)中mbb的查找（過濾），在此基礎(chǔ)上還要對兒何圖形 進(jìn)行精確查找?；诳臻g索引的空間查詢分兩步完成，第一步利用空間索引結(jié)構(gòu)和空間訪問方 法sam對數(shù)據(jù)集進(jìn)行過濾（初選），在索引表中查找滿足査洵條件的mbb，結(jié)果為對象的一個(gè) 超集（多個(gè)oid）。第二步對初選結(jié)果進(jìn)行準(zhǔn)確查找，在超集中通過空間計(jì)算算法，求取滿足查 詢條件的精確對象。二、空間分割與空間索引單元?jiǎng)澐纸⒖臻g索引的第一步是按照一定的方式將被查詢空間分割成多個(gè)索引單元。冇兩種對空 間進(jìn)行劃分的方法，形

13、成兩大類空間索引結(jié)構(gòu)，很多sam都屬于這兩類結(jié)構(gòu)之一。1、空間驅(qū)動(dòng)結(jié)構(gòu)：采用基于空間位fi的分割方法，將研究區(qū)域的2d空間進(jìn)行完全劃分， 劃分力多個(gè)矩形或正方形范圍，毎個(gè)范圍定義力一個(gè)空間索引單元，對象在2d空間的分布是 獨(dú)立的，對象按一定原則分配到不同的矩形單元。也可將研究區(qū)域的2d空間劃分為多個(gè)凸多 邊形范圍，每個(gè)凸多邊形近似表示一個(gè)空間對象的幾何形狀。例如.將研究空間用規(guī)則的正方形格網(wǎng)進(jìn)行分割，每個(gè)正方形網(wǎng)格為一個(gè)空間索引單元， 索引多個(gè)空間對象?？臻g對象褪蓋多個(gè)相鄰的空間索引單元時(shí)，在其蒗蓋的每個(gè)索引單元中各 有一個(gè)索引項(xiàng)，索引項(xiàng)屮包含空間對象標(biāo)識(shí)o1d。2、數(shù)據(jù)驅(qū)動(dòng)結(jié)構(gòu)：是一種基于對

14、象的分割，對2d研究區(qū)域的空間分割直接由分布在其中 的空間對象來確定，對空間對象集合進(jìn)行分割。每個(gè)空間對象用它的最小外接矩形mbb近似 表示，每個(gè)空叫索引單元的形狀也是一個(gè)矩形區(qū)域，它包含多個(gè)空間對象的最小外接矩形mbb。 空間索引單元的面積大小取決于其索引的空間對象集合的而積、形狀和分布，索引單元中存儲(chǔ) 空閬對象的最小外接矩形mbb。基于對象的分割不是空閬的一種完全劃分。三、空間索引結(jié)構(gòu)的具體分類綜合現(xiàn)有研究及參考文獻(xiàn)，可將主要的空間索引技術(shù)分類如下：空間索引線性索引非線性索引線性on vm網(wǎng)格空間索引基丁樹的索引線性映射結(jié)構(gòu)點(diǎn)對象基于mbb基于約束基于凸多邊形網(wǎng)格文件pr樹r樹系列/gpr

15、樹cell系列bsp樹llr 樹 cell 樹 cp 樹 os-cell 樹樹rr+樹r*樹 r-link樹 qr樹 sr樹 tv樹 x樹 sdr樹圖7-2空間索引分類索引結(jié)構(gòu)中，如果將2d或3d分布的空間索引單元，按照一定的方式組織成線性形式，相 應(yīng)的索引稱為線性空間索引。相反，以非線性形式來組織空間索引單元，相應(yīng)的索引稱為非線 性空間索引。一、線性索引線性索引主要有線性映射結(jié)構(gòu)與線性四叉樹。1、線性映射結(jié)構(gòu)：首先，用均5j或不均勻的正方形格網(wǎng)對被索引空間區(qū)域進(jìn)行劃分；然后， 采用填充曲線對索引空間進(jìn)行填充（如hilbert curve曲線），取填充曲線編碼為索引單元的序號， 將索引單元按序

16、號排序建立線性索引結(jié)構(gòu)。這里，空間劃分是基于位置的完全劃分，建立的索 引為空間驅(qū)動(dòng)的、線性組織的、規(guī)則的網(wǎng)格空間索引結(jié)構(gòu)。2、線性四叉樹：毎一個(gè)空間對象用其mbb近似表示，對含有mbb集合的空間進(jìn)行四叉 樹劃分，劃分后的不均勻網(wǎng)格作為索引單元，每個(gè)單元分別編號，葉結(jié)點(diǎn)根據(jù)編號組織成b-樹 結(jié)構(gòu)，這種結(jié)構(gòu)叫線性四叉樹。二、非線性索弓i非線性空間s引按索引的邏輯組織方式分成網(wǎng)格空間索引和基于樹的空間索引。（一）網(wǎng)格空問索引網(wǎng)格空問索引簡稱稱m格索引，是基于位置的空m驅(qū)動(dòng)結(jié)構(gòu)。它將被索引空問用平行于坐 標(biāo)軸的橫豎線條劃分成大小相等或不等的網(wǎng)格，每個(gè)網(wǎng)格為一個(gè)索引單元，記錄每個(gè)網(wǎng)格所包 含的多個(gè)對象的

17、標(biāo)識(shí)?？諉柌樵儠r(shí)，先計(jì)算出對象所在的m格，然后在m格屮快速查詢對象。 網(wǎng)格索引分為均勻網(wǎng)格索引和網(wǎng)格文件索引，可以索引點(diǎn)對象及用mbb近似的其他類型的空 間對象。網(wǎng)格索引以二維數(shù)組結(jié)構(gòu)來存儲(chǔ)，是一種非線性空間索引結(jié)構(gòu)。（二）基于樹的空間索引基于樹的空間索引是一種基于對象的數(shù)據(jù)驅(qū)動(dòng)結(jié)構(gòu)。首先采用某種幾何形狀近似算法，將 被索引空間屮的空間對象表示為其近似體，然后將近似體按確定規(guī)則組織成樹形結(jié)構(gòu)?；跇?的空間索引按幾何形狀近似技術(shù)的不同可分力基于凸多邊形的空間索引、基于約束的空間索引 和基于mbb的空問索引。i、基于凸多邊形的空間索引基于凸多邊形的空間索引又稱劃分樹結(jié)構(gòu)，它將被索引空間劃分成凸多

18、邊形，然后w對凸 多邊形進(jìn)行同樣的劃分，直到該劃分滿足特定精度為止。用凸多邊形近似表示對象的形狀。(1) bsp樹bsp樹是一種二叉樹，它將被索引空間逐級進(jìn)行一分為二的劃分，形成一棵二叉樹bsp樹。(2) cell 樹、cp 樹、os-cell 樹cell樹與bsp樹相似，bsp樹將被索引空闖一分為二，cell樹則將被索引空問劃分成 多個(gè)a多邊形，然后依次再對每個(gè)ini多邊形進(jìn)行相似的劃分，直到到達(dá)預(yù)定的精度為止，cell 樹是一棵多義樹。cell樹與bsp樹的相同之處是子空間相互間不覆蓋，優(yōu)點(diǎn)是磁盤1/0次數(shù) 較少，但索引項(xiàng)中凸多邊形的存儲(chǔ)耑較多空問，且進(jìn)行兒何形狀的精確匹配時(shí)計(jì)算也較復(fù)雜。

19、cp樹是cell樹的一種變種樹，采用cell樹同樣的空問劃分方法，但允許子空間部分覆 蓋。特點(diǎn)是與r樹相比，具冇較小的子空間覆蓋面積，磁盤1/0次數(shù)較少，同樣索引項(xiàng)中對a 多邊形的存儲(chǔ)需較多的空間，且進(jìn)行空間對象的精確匹配時(shí)計(jì)算較復(fù)雜。os-cell樹也是cell樹的一種變種樹，只是針對cell樹中存在的特大空間對象，對 cell樹進(jìn)行改進(jìn)、完善和優(yōu)化。由于特大空間對象占據(jù)較大的被索引空間，其在cell樹中 可能會(huì)被分割成多個(gè)凸多邊形，當(dāng)特大空間對象較多時(shí)，cell樹的葉節(jié)點(diǎn)分裂會(huì)相當(dāng)頻繁， 使cell樹的重構(gòu)吋間增多，有效訪問速度變慢；每個(gè)特大空間對象可能存放到多個(gè)磁盤塊中， 增加cell樹

20、的尚度，從而增加磁盤1/0次數(shù)，惡化cell樹的搜索性能。os-cell樹分配特 大盤塊專用于存儲(chǔ)特大空間對象，在父節(jié)點(diǎn)中添加指向該特大盤塊的指針。對普通幾何對象而 言，os-cell樹的特點(diǎn)與cell樹相同。2、基于約朿的空間索引其代表o樹采用空間近似算法，將幾何對象按ax+by=c(a, b)，c (a, b) e (-1, 0, 1)表 示為一組約朿表達(dá)式，相應(yīng)于笛卡爾飧標(biāo)空間中的六條曲線中的某種組合，然后根據(jù)空間對象 間的空間關(guān)系建立空間索引樹。特點(diǎn)是能夠自然地表示空間對象間的空間關(guān)系，但對空間對象 的精確匹配需較多的計(jì)算。3、基于mbb的空間索引基于mbb的樹狀空間索引均將空間對象近

21、似為其mbb,根據(jù)mbb間的空間關(guān)系建立相 應(yīng)的樹形結(jié)構(gòu)，這類空問索引主要指r樹系列。自1984年guttman提出r樹以來，學(xué)者根據(jù) 不同應(yīng)用對r樹的需求，對r樹進(jìn)行了各種改進(jìn)，形成了諸多r樹的變種，如圖7-2所示。當(dāng)前主要的空間索引結(jié)構(gòu)歸納為網(wǎng)格索引、線性網(wǎng)叉樹、r樹結(jié)構(gòu)、劃分樹結(jié)構(gòu)和線性映 射結(jié)構(gòu)等類型。本章主要探討這兒類空問索引的索引結(jié)構(gòu)，索引建立和簡單的查詢操作。7.2空間驅(qū)動(dòng)的索引結(jié)構(gòu)空問驅(qū)動(dòng)索引結(jié)構(gòu)的主要特征是采用某種格網(wǎng)對2d空間進(jìn)行劃分，將空問劃分成小區(qū)域， 每個(gè)小區(qū)域?yàn)橐粋€(gè)索引單元，每個(gè)索引單元索引多個(gè)空間對象。索引單元按照一定的數(shù)據(jù)結(jié)構(gòu) 來組織，如果組織成線性結(jié)構(gòu)，則相應(yīng)

22、的空間索引為線性索引，如果組織成非線性結(jié)構(gòu)，則相 應(yīng)的空間索引力非線性索引。即空間驅(qū)動(dòng)結(jié)構(gòu)既包含線性索引，也包含非線性索引，非線性結(jié) 構(gòu)主要宥網(wǎng)格索引，線性結(jié)構(gòu)有線性四叉樹和線性映射結(jié)構(gòu)。7.2.1網(wǎng)格索引網(wǎng)格索引是一種空間驅(qū)動(dòng)的非線性索引結(jié)構(gòu)，其基本特征是用正方形或矩形格網(wǎng)對研究區(qū) 域的2d空間進(jìn)行劃分，每個(gè)網(wǎng)格單元為一個(gè)索引單元，索引多個(gè)空間對象，索引單元按行列 號組織成2d目錄。網(wǎng)格索引包栝均勻網(wǎng)格索引和網(wǎng)格文件索引，均勻網(wǎng)格適合于索引空間點(diǎn) 對象；網(wǎng)格文件是均勻網(wǎng)格的改進(jìn)，是一種多關(guān)鍵字索引，可索引點(diǎn)對象和對象的mbb，能夠 與b+樹簡單集成，在商用數(shù)據(jù)庫oracle屮已實(shí)現(xiàn)。一、均勻

23、網(wǎng)格(一) 均勻網(wǎng)格的特征設(shè)兒何對象均為點(diǎn)對象。研究區(qū)域?yàn)橐粋€(gè)sa.xsy大小的空問，將其劃分為na. x/7y個(gè)相同大小的網(wǎng)格，每個(gè)網(wǎng)格的邊長為sv/na.xsv/nv,起始坐標(biāo)為(xq,%)。每個(gè)網(wǎng)格為一個(gè)索 引單元，對應(yīng)于磁盤上一個(gè)物理頁，每個(gè)m格屮的點(diǎn)存入相應(yīng)的磁盤頁屮。如圖7-3,索引目錄表為一個(gè)2d數(shù)組dir1:z7a.，1:/2、.,每個(gè)g錄項(xiàng)diri, jl含宥頁標(biāo)識(shí)pageld拳b1參參 籲&/j%n7索引目錄物理頁 vx0 xi x2 x3 x4(a, b) 讎(k，l)圖7-3均勻網(wǎng)格(二) 基于均勻網(wǎng)格索引的空間訪問1、插入新點(diǎn)：假設(shè)新點(diǎn)的染標(biāo)為(x，y)，計(jì)算

24、新點(diǎn)所在網(wǎng)格(索引單元)的行列號 z=(x-%0)/(5r/?,)+!, y = (y-y0)/(sv/ziv) + u 新點(diǎn)的索引目錄項(xiàng)為 diri, j,假設(shè)對應(yīng)的磁盤頁diri, j.pageid為(a, b)所在的頁p(a, b),將新點(diǎn)插入p(a, b)頁屮。2、點(diǎn)查詢：假設(shè)鼠標(biāo)當(dāng)前位置的坐標(biāo)為(x，y)，計(jì)算鼠標(biāo)位置所屬索引單元的行列號/=(x-x0)/(st /nr)+10 j = (y - y0)/(sy /ny) +1 ,讀入對應(yīng)的磁盤頁 diri, j.pageid，掃描該頁屮所有點(diǎn)對象，判斷哪些點(diǎn)對象與(x, y)點(diǎn)重疊。3、窗u查詢：計(jì)算窗uw覆蓋的網(wǎng)格集合s=c小對s

25、中的每個(gè)讀取diri，jl.pageid,返回這些頁中包含的所有點(diǎn)對象，即為窗口 w范圍內(nèi)包含的點(diǎn)對象。如果目錄在內(nèi)存屮，點(diǎn)查詢只需一次i/o。窗口查詢的i/o數(shù)與窗口覆蓋的格數(shù)成正比。 格網(wǎng)分辨率的選擇取決于被索引點(diǎn)對象的數(shù)量。假設(shè)共冇n個(gè)點(diǎn)對象，每頁存儲(chǔ)的最大點(diǎn)數(shù)為m,則至少需要有n/m個(gè)網(wǎng)格。如果某個(gè)網(wǎng)格中的點(diǎn)數(shù)超過m,多出的點(diǎn)放到溢出區(qū)， 溢出區(qū)與索引區(qū)域用指針相連。如圖7-4中例子，每個(gè)網(wǎng)格所存的最大點(diǎn)數(shù)m=4, k，l，m，n，o五 個(gè)點(diǎn)對象位于同一*個(gè)網(wǎng)格中，對應(yīng)于磁盤頁p。將k，l,m，n叫個(gè)點(diǎn)放入p頁，()放入溢出區(qū)，將 溢出區(qū)與p貞相連。所有的網(wǎng)格共用一個(gè)溢出區(qū)，溢出區(qū)可能

26、由多個(gè)磁盤頁連接成溢出區(qū)鏈。 如果o點(diǎn)存儲(chǔ)在溢出區(qū)鏈的第q貞，則點(diǎn)查詢的i/o數(shù)為q。最壞的情況下，所冇點(diǎn)都位于同一 網(wǎng)格屮，索引結(jié)構(gòu)為磁盤貞的線性列。點(diǎn)的頻繁插入會(huì)導(dǎo)致較長的溢出鏈，而點(diǎn)刪除會(huì)導(dǎo)致空 貞。對于某些具體分布，這種索引不能滿足磁盤存儲(chǔ)的要求。索引目錄(a, b, c, d)(k, 1, m, n)溢出區(qū) 垂(o)圖7-4均勻m格屮的溢出頁二、點(diǎn)對象的格網(wǎng)文件格網(wǎng)文件與均勻格m的相同之處是采用平行于華標(biāo)軸的格m對空間進(jìn)行完全劃分，每個(gè)網(wǎng) 格單元為一個(gè)索引單元，索引單元組織成2d 0錄形式。與均勻格網(wǎng)不同的是，每次發(fā)生溢出 時(shí)，動(dòng)態(tài)的將m格單元在橫向或縱向上分裂為兩個(gè)單元，可根裾網(wǎng)格

27、單元屮點(diǎn)對象的分布情況 來選擇進(jìn)行縱向還是橫向劃分；網(wǎng)格文件中的網(wǎng)格單元為大小不相同的矩形單元，多個(gè)網(wǎng)格單 元可對應(yīng)同一個(gè)磁盤頁。（一）格網(wǎng)文件的數(shù)據(jù)結(jié)構(gòu)格網(wǎng)文件由三種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，索引目錄dir是一種與均勻網(wǎng)格中的索引目錄類似的2d數(shù)組，差別是兩個(gè)相鄰單元可共享同一磁盤頁；sa.，sv是兩個(gè)線性數(shù)組，表示沿兩坐標(biāo)軸的劃分。圖7-5中的例子描述了這種結(jié)構(gòu)，假設(shè)網(wǎng)格的最大容量m=4。sx物理頁 繼圖7-5均勻網(wǎng)格文件的插入（二）構(gòu)建網(wǎng)格文件的步驟第一步：只有四個(gè)對象，目錄中只有一個(gè)網(wǎng)格c指向pi頁。第二步：插入點(diǎn)a、b、c。1、在網(wǎng)格（：插入a時(shí)，pi溢出。2、在中的&處將網(wǎng)格c垂直劃

28、分成兩個(gè)單元q和c2,將c中原冇的4個(gè)點(diǎn)劃分到和c2兩個(gè)單元中。3、創(chuàng)建一個(gè)新磁盤頁p2，q指向pi頁，c2指向p2頁。4、將a和b插入q單元對應(yīng)的pi頁，c插入c2單元對應(yīng)的p2頁。第三步：插入d1、在q單元中插入點(diǎn)d時(shí)pi溢出。2、在s、.中的 ，,處將;,和（：2單元進(jìn)行水平劃分，水平劃分為6和2。3、創(chuàng)建一個(gè)新磁盤頁p3，將pi中原有4個(gè)點(diǎn)劃分到pi和p3中，chl指向pl： c12指向 p3。將點(diǎn)d插入單元對應(yīng)的pi頁。此時(shí)，水平線將沒溢出的單元&也水平劃分為兩個(gè)單 元c23和c2,2: c21和c2 2指向同一個(gè)磁盤頁p2。第四步：插入e和f兩點(diǎn)。1、將e和f分別插入c21

29、和c2 2單元，c2 l和c2 2沒溢出，而p2溢出。2、分配一個(gè)新頁p4。e2,存入p4，c2 2存入p2。（三）插入一個(gè)點(diǎn)時(shí)可能的三種情況1、網(wǎng)格單元不分裂：磁盤頁沒滿，只需讀入頁，插入點(diǎn)。2、網(wǎng)格單元不分裂但磁盤頁溢出：點(diǎn)n插入單元c吋，與c相關(guān)聯(lián)的磁盤頁p滿了，但p 由多個(gè)單元引用。此時(shí)分配一個(gè)新頁/?，將p頁中含在c單元莖的點(diǎn)和新點(diǎn)n分配給新頁/9, c單元的索引目錄指向/。3、單元分裂且磁盤頁溢出：新點(diǎn)插入時(shí)磁盤頁滿，且該頁只有一個(gè)網(wǎng)格單元引用，此時(shí)網(wǎng) 格單元沿x或y分裂。以沿x軸分裂為例：（1）&在'+|處分成和1;（該列的所冇單元均分為兩個(gè)），將分裂點(diǎn)的位置&#

30、39;.+1插 入么中。（2）創(chuàng)建一個(gè)新物理頁p,將原來中的點(diǎn)和新插入的點(diǎn)分配到.和c/+u中，分別指 向p和廠。（3）dir中所冇列號i的列，都將列號+1。創(chuàng)建一個(gè)索引列兮為“i+1”的新索引項(xiàng)。對 所有j*的行，新單元么,與么指向相同的物理頁。格網(wǎng)文件克服了均勻網(wǎng)格的主要缺陷，點(diǎn)查詢通過兩次i/o操作就可完成（訪問目錄對應(yīng) 的頁和讀貞數(shù)據(jù)）。該結(jié)構(gòu)是動(dòng)態(tài)的，缺點(diǎn)是對于大數(shù)據(jù)集，目錄會(huì)大到內(nèi)存放不下的程度。三、格網(wǎng)文件索引mbb用網(wǎng)格文件對mbb進(jìn)行索弓i，最簡單的惜況是每個(gè)覆蓋mbb的m格單元都保存該mbb 的索引項(xiàng)。mbb與網(wǎng)格單元的關(guān)系有三種：mbb包含網(wǎng)格單元、網(wǎng)格單元與mbb相交、

31、網(wǎng) 格單元包含mbb。前兩種情況，每個(gè)網(wǎng)格單元都建立mbb的索引項(xiàng)，一個(gè)mbb有多項(xiàng)索引。例子：有15個(gè)mbb，毎頁的最大容量為4。圖7-6為用均勻網(wǎng)格建立的索引：y371y0m118ii151 121i6|123aszltjxo xi x2 x3 x4索引目錄p11物理頁 pnj p8, 12籌 馨11, 1516圖7-6基于mbb的均勻網(wǎng)格索引 圖7-7為用網(wǎng)格文件建立的索引：yzlel&iii12-廣驚vl目錄10<<，5 6|ezj9.10.13 8.11.12.13jf!x20 xo圖7-7基于網(wǎng)格文件的mbb索引對象的插入、刪除與點(diǎn)索引相同，只是一個(gè)mbb可能具

32、冇多個(gè)索引項(xiàng)，分裂會(huì)更頻繁。(一) 索引項(xiàng)插入1、插入對象14如圖7-8，將對象14插入圖7-7中的索引單元dir1, 3時(shí),dirfl, 3中的索引項(xiàng)超過4 項(xiàng)，對應(yīng)的磁盤頁p5也溢出。在x3處對dir1, 3進(jìn)行水平分裂，將x3存入sa.中，現(xiàn)有3* (2+1)=9個(gè)目錄項(xiàng)。目錄單元dir1, 1和dirr，1同指句pi頁，dir1, 2和dir2, 2同指句 p3貞。原來p5頁中的對象由于對象14的插入，分裂成了 p5和p6兩貞，dirll, 3j指向p5, dir2, 3指向p6。對象5有兩個(gè)索引項(xiàng)分別存儲(chǔ)在p5和p6兩貞中，對象6有四個(gè)索引項(xiàng)分別存儲(chǔ)在p5、p6和p3中。ld廠d32

33、113rj j 6lrhale=312_11 k) 1a!x2xfl x3 xl x2 xo ao圖7-8對象14的插入2、插入對象15圖7-9力0澩不分裂而磁盤頁溢出的情況。插入前d1r3, 2和dir3, 3同指向p4,將對象15分別插入dir3，2和dir3，3中。 插入后dir13, 2j和dir13, 3j中的索引項(xiàng)均不超過4個(gè)，目錄不用分裂，但磁盤頁p4溢出。 創(chuàng)建新頁 p7, dir3, 2指向 p4, dir3, 3指向 p7。|，|q3fi6ez3=1ucb o jd)xiy2 -3jwl21聲2 圃1i5卜2,5,6 | 5a14卜】1j5 |p5pe| 9, 10, 13

34、| 8j2j3j5xoxl x2目錄xp2 p4圖7-9對象15的插入（二）點(diǎn)查詢算法 1、工作過程第一步：給定點(diǎn)坐標(biāo)p（xp，yp）,查找含有p的網(wǎng)格單元。對于均勻網(wǎng)格索引來說是常數(shù)時(shí) 間，若用網(wǎng)格文件則分x，y兩個(gè)方向查找，復(fù)雜度是對數(shù)函數(shù)。第二步：進(jìn)行一次磁盤操作將這個(gè)索引單元對應(yīng)的磁盤貞調(diào)入內(nèi)存，讀取該頁所存對象的 （mbb, oid）,構(gòu)成集合e。對e中的每個(gè)對象e，測試e.mbb是否含有點(diǎn)p。第三步：對于包含點(diǎn)p的e.mbb,通過e.oid獲取其兒何邊界數(shù)據(jù)，精確測試p是否位于e.oid 的幾何邊界之內(nèi)。2、例子圖7-10為一個(gè)格網(wǎng)文件點(diǎn)查詢的例子。點(diǎn)p位于dir3, 2范圍之內(nèi)，

35、對應(yīng)的磁盤頁p4中 含有4個(gè)索引項(xiàng)。將p4頁調(diào)入內(nèi)存，對其包含的4個(gè)mbb分別進(jìn)行測試，其中8和12的mbb 中包含了點(diǎn)p。根據(jù)對象標(biāo)識(shí)8和12取出各自的幾何邊界數(shù)據(jù)，精確測試對象8和12,求出包 含點(diǎn)p的對象。點(diǎn)查詢的i/o數(shù)是常數(shù)。ldczr6 jit3cm(zz3l2_j多k» 1o xoxi*1x2jx，2/>3a'一z11/>»/>2.-123«f |b2a6| 5, 6,148? 11,15 |p5p6r 1i 9, 10, 13 | 8,12, 13, 15 |0x3x1 x2目錄p2 p4圖7-10基于網(wǎng)格文件的點(diǎn)查詢（三

36、）窗口査詢算法工作過程如下：第一步：計(jì)算所有褪蓋窗u的索引單元。第二步：掃描每一個(gè)索引單元，調(diào)入相應(yīng)的磁盤貞。讀入每個(gè)磁盤頁中的對象，排序并去 掉重復(fù)對象。求出那些落入窗口屮，或與窗口相交的mbb。第三步：根據(jù)各自的對象標(biāo)識(shí)取出這些mbb對應(yīng)的兒何邊界，精確檢測每個(gè)對象是否位于 窗口屮或與窗口相交。窗口査詢的i/os與窗口的面積成正比。(四) 總結(jié)用網(wǎng)格文件索引mbb,大多數(shù)情況下比較理想，但也存在很多問題：1、對象的多重索引增加了索引表的容量，數(shù)據(jù)集越大越嚴(yán)重，索引單元接近mbb大小吋， 情況就更嚴(yán)重。2、索引表容量越大，查詢重復(fù)項(xiàng)的代價(jià)越高。3、算法的效率依賴于索引表位于內(nèi)存中的假設(shè)，如果

37、索引表很大，一部分要存入磁盤，管 理將變得s雜，效率會(huì)受影響。7. 3數(shù)據(jù)驅(qū)動(dòng)的索引結(jié)構(gòu)空間驅(qū)動(dòng)的索引結(jié)構(gòu)將整個(gè)空間劃分成小區(qū)域，每個(gè)小區(qū)域定義為一個(gè)索引單元，直接索 引其中的空間對象或索引對象的mbbc數(shù)據(jù)驅(qū)動(dòng)的索引結(jié)構(gòu)則按照空間對象的位置、范圍和分 布，來確定索引單元的位a和范圍，索引單元的全集不一定覆蓋整個(gè)空間。這里主要介紹r樹 系列和劃分樹。7.3.1 r 樹r樹是一種數(shù)據(jù)驅(qū)動(dòng)的索引結(jié)構(gòu)，是b樹的擴(kuò)展。與b樹相比，r樹是一棵由多層嵌套的 外接矩形構(gòu)成的平衡樹，即r樹的每個(gè)結(jié)點(diǎn)以范圍矩形mbb或目錄矩形dr的形式表示一個(gè)空 間范圍，它界定了一個(gè)空問索引區(qū)域，定義為一個(gè)空問索引單元。r樹的

38、每個(gè)結(jié)點(diǎn)都是一個(gè)空 間索引單元，非葉結(jié)點(diǎn)包含其多顆子樹的索引項(xiàng)，葉結(jié)點(diǎn)包含多個(gè)數(shù)據(jù)對象的索引項(xiàng)，木結(jié)點(diǎn) 的范圍矩形作為自身索引項(xiàng)的一部分存儲(chǔ)在它的上層結(jié)點(diǎn)中。r樹的每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)物理頁，每個(gè)結(jié)點(diǎn)只能包含k個(gè)索引項(xiàng)，m<k<m，m是r樹結(jié) 點(diǎn)中包含索引項(xiàng)的最大數(shù)0，m是r樹結(jié)點(diǎn)中包含索引項(xiàng)的最小數(shù)0，并限制2smm/2。一、原始的r樹r樹的基本結(jié)構(gòu)是一棵多層嵌套的、由外接矩形構(gòu)成的平衡樹。每個(gè)結(jié)點(diǎn)的索引區(qū)域表示 成一個(gè)范圍矩形，每個(gè)結(jié)點(diǎn)為一個(gè)空間索引單元，每個(gè)索引單元有k個(gè)索引項(xiàng)。葉結(jié)點(diǎn)的范圍 矩形為其內(nèi)部多個(gè)數(shù)據(jù)對象mbb的最小外接矩形，非葉結(jié)點(diǎn)的范圍矩形為其多個(gè)子結(jié)點(diǎn)范圍矩 形

39、mbb的最小外接矩形。葉結(jié)點(diǎn)中存放多個(gè)數(shù)據(jù)對象的索引項(xiàng)，每個(gè)索引項(xiàng)的形式為iptr，mbb, oid,其屮oid是數(shù)據(jù)對象的標(biāo)識(shí)，mbb是數(shù)據(jù)對象的外接矩形，ptr指向存儲(chǔ)該對象兒何形狀 數(shù)據(jù)的磁盤位置。非葉結(jié)點(diǎn)中存放多個(gè)子結(jié)點(diǎn)索引項(xiàng)，每個(gè)索引項(xiàng)的形式為ptr，mbb, nodeid, 其中nodeid是指向子結(jié)點(diǎn)的指針，mbb為子樹的目錄矩形dr，ptr是子結(jié)點(diǎn)對應(yīng)的磁盤頁地址。(一) r樹的性質(zhì)1、根結(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn)；2、所有的葉結(jié)點(diǎn)都處于同一層；3、除根結(jié)點(diǎn)外，r樹中所龜結(jié)點(diǎn)鈕含的索引項(xiàng)數(shù)目均在m，ml之間，并限制圖7-26顯示一棵m=2, m=4的r樹。m的大小取決于索引項(xiàng)大小si

40、ze(e)和磁盤頁大小 sizc(p), a/= |_size(p)/size(e)。通常oid大于nodeid，w而，非葉結(jié)點(diǎn)和葉結(jié)點(diǎn)的m不同。給定m和m后，一個(gè)深度為d的r樹最少可索引/7?+1個(gè)對象，至多可索引個(gè)對象。相 反，要索引n個(gè)對象，r樹的深度最大為llog,（/v）-1, ®小為llog，w（ao_j l。假設(shè)頁的大小為4k,索引項(xiàng)的大小為20bc16b為mbb，4b為oid），m設(shè)為頁容量的40%， 則似=l496/20= 204，/h = l204x40%j = 81 o這種惜況下，深度為1時(shí)可索引至少81*81=6561 個(gè)對象，深度為2可索引81*81*81=

41、531441到204*204*204=8489664個(gè)對象。對于million個(gè)對 象，只需要三層，即訪問三個(gè)磁盤頁就可到達(dá)樹葉，再讀取相應(yīng)的對象即可。（二）r樹查詢效率的優(yōu)化r樹允許兄弟結(jié)點(diǎn)間有區(qū)域重疊，因此，查詢一個(gè)對象可能要訪問多個(gè)分支，這是影響r 樹查詢效率的主要因素。對r樹查詢效率的優(yōu)化可考慮如下參數(shù)：1、查詢區(qū)域：查詢條件所覆蓋的區(qū)域。2、重疊區(qū)域：兄弟結(jié)點(diǎn)間范圍矩形相互重疊的區(qū)域。重疊區(qū)域減少時(shí)，查詢區(qū)域與重疊區(qū) 域相交的概率減少，可減少查詢時(shí)訪問的分支數(shù)。3、死區(qū)域：被結(jié)點(diǎn)范圍矩形覆蓋但不被其子結(jié)點(diǎn)范圍矩形覆蓋的區(qū)域。死區(qū)域減少時(shí)，屬 于結(jié)點(diǎn)范m內(nèi)的查詢區(qū)域與其子結(jié)點(diǎn)范m矩形相

42、交的概率增大，在該分支上找到s標(biāo)數(shù)據(jù)的概 率也增大，提高了分支選擇的準(zhǔn)確性。4、范圍矩形周長：結(jié)點(diǎn)范圍矩形四邊長度之和。對于而積固定的矩形，周長越小，其形狀 越接近正方形，正方形的空間聚簇性好，易于填滿父結(jié)點(diǎn)的范圍矩形，所以減少子結(jié)點(diǎn)的范圍 矩形周長可減少父結(jié)點(diǎn)的死區(qū)域。5、結(jié)點(diǎn)利用率：結(jié)點(diǎn)的實(shí)際子結(jié)點(diǎn)數(shù)（或數(shù)據(jù)對象數(shù)）與最大子結(jié)點(diǎn)數(shù)（或數(shù)據(jù)對象數(shù)） 之比。提高結(jié)點(diǎn)利用率可降低樹的平均高度，對于大區(qū)域查詢，滿足條件的數(shù)據(jù)對象數(shù)b很大， 結(jié)點(diǎn)利用率高可在很大程度上減少結(jié)點(diǎn)訪問數(shù)，從而提高查詢效率。上述優(yōu)化參數(shù)有些相容，有些互斥。一般來說，減少死區(qū)域的同時(shí)可能也減少了重疊區(qū)域， 兩者是相容的。而為

43、了減少死區(qū)域，則要求結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)0能更自由，結(jié)點(diǎn)利用率可能會(huì)降 低。減少死區(qū)域和減少重疊區(qū)域都要求結(jié)點(diǎn)外接矩形的形狀更自由，結(jié)點(diǎn)范圍就可能無法接近 正方形。對于任意幾何形狀，減少周長一般也會(huì)影響到結(jié)點(diǎn)利用率，接近正方形的外接矩形更 容易填滿父結(jié)點(diǎn)范圍矩形，也容易提島結(jié)點(diǎn)利用率。對于大區(qū)域查詢，結(jié)點(diǎn)利用率對查詢的影 響遠(yuǎn)遠(yuǎn)大于其他三個(gè)因素。（三）基于r樹的查詢點(diǎn)查詢和窗口查詢幾乎完全一樣，這里只介紹點(diǎn)査詢。函數(shù)rtpointquery實(shí)現(xiàn)兩步：1、在每一層中查找各結(jié)點(diǎn)屮所有含p點(diǎn)的子結(jié)點(diǎn)，因?yàn)橥饨泳匦慰梢灾丿B，滿足條件的子 結(jié)點(diǎn)可能有多個(gè)，相同的方法直到葉結(jié)點(diǎn)。訪問毎個(gè)結(jié)點(diǎn)時(shí)可能發(fā)牛.兩種情況

44、：（1）該結(jié)點(diǎn)不包含p,即p落在非葉結(jié)點(diǎn)范圍矩形的死區(qū)域，查找終止。（2）p點(diǎn)包含在該結(jié)點(diǎn)多個(gè)子結(jié)點(diǎn)的mbb中，這時(shí)要搜索每一棵子樹，直到葉結(jié)點(diǎn)。2、順序掃描第一步得到的所有葉結(jié)點(diǎn)，所有包含p點(diǎn)的數(shù)據(jù)對象的索引項(xiàng)mbb即為所求。圖7-26顯示了點(diǎn)查詢的例子，査詢訪問了 r，b，c，d四個(gè)結(jié)點(diǎn)，p點(diǎn)含在對象8和12的mbb 中。r圖7-26基于r-樹的點(diǎn)查詢（三）r樹的插入操作1、插入步驟（1）從根結(jié)點(diǎn)向葉子搜索，如某個(gè)結(jié)點(diǎn)的范圍矩形包含被插入對象的mbb，則繼續(xù)查找其 子樹，如果不包含則終止，重復(fù)此過程直到葉結(jié)點(diǎn)/。（2）如果葉結(jié)點(diǎn)/未滿，則將新對象的mbb, oid插入葉結(jié)點(diǎn)/;如果葉結(jié)點(diǎn)/

45、已滿，則將 葉結(jié)點(diǎn)/分為裂為/利1/'兩頁（重構(gòu)/兩!/的范圍矩形），將m+1個(gè)索引項(xiàng)分配到兩頁中，在父結(jié) 點(diǎn)f中修改/的索引項(xiàng)（/的范w矩形有變化），并插入/|的索引項(xiàng)。如果父結(jié)點(diǎn)f也滿了，貝幢圖7-27對象15的插入2、插入舉例（設(shè)m=4）（1）在圖7-26屮插入對象15:葉結(jié)點(diǎn)d的范圍矩形屮包含對象15的mbb，d屮原有的索 引項(xiàng)為11，12，13，將對象15直接插入葉結(jié)點(diǎn)d中，重構(gòu)d結(jié)點(diǎn)的范圍矩形，并改變d結(jié)點(diǎn) 在根結(jié)點(diǎn)r中的索引項(xiàng)，插入結(jié)果如圖7-27所示。（2）在圖7-27中插入對象16:葉結(jié)點(diǎn)b的范圍矩形中包含對象16的mbb,將對象16插 入到葉結(jié)點(diǎn)b中。b中原有的索引項(xiàng)為3, 4, 7, 10，b結(jié)點(diǎn)滿了，應(yīng)分裂為b和e兩個(gè)結(jié)點(diǎn)， 將3, 4, 7分配在b中，10，16分配在e屮。重構(gòu)結(jié)點(diǎn)b的范圍矩形，修改b在根結(jié)點(diǎn)r中 的索引項(xiàng)。生成e的范圍矩形，將e的索引