高級(jí)數(shù)據(jù)庫(kù)技術(shù)-第10章 空間數(shù)據(jù)庫(kù)

1、2022-2-161第第10章章 空間數(shù)據(jù)庫(kù)空間數(shù)據(jù)庫(kù)10.1 空間數(shù)據(jù)庫(kù)概述空間數(shù)據(jù)庫(kù)概述2022-2-16210.1.1空間數(shù)據(jù)庫(kù)的意義空間數(shù)據(jù)庫(kù)的意義 從本體論的角度，研究和開(kāi)發(fā)空間數(shù)據(jù)庫(kù)的意義主要基于下述幾個(gè)方面。 1時(shí)間和空間是物質(zhì)存在的基本方式時(shí)間和空間是物質(zhì)存在的基本方式 2空間數(shù)據(jù)是某些重要應(yīng)用的基本形式空間數(shù)據(jù)是某些重要應(yīng)用的基本形式 3復(fù)雜的非空間數(shù)據(jù)可以作為空間數(shù)據(jù)處理復(fù)雜的非空間數(shù)據(jù)可以作為空間數(shù)據(jù)處理2022-2-16310.1.2空間數(shù)據(jù)基本特征空間數(shù)據(jù)基本特征 1數(shù)據(jù)量大數(shù)據(jù)量大 結(jié)構(gòu)復(fù)雜結(jié)構(gòu)復(fù)雜 數(shù)據(jù)聯(lián)系多樣化數(shù)據(jù)聯(lián)系多樣化 2查詢過(guò)程復(fù)雜查詢過(guò)程復(fù)雜 3空間對(duì)

2、象間難以定義次序空間對(duì)象間難以定義次序2022-2-16410.1.3空間數(shù)據(jù)庫(kù)作為常規(guī)數(shù)據(jù)庫(kù)擴(kuò)充空間數(shù)據(jù)庫(kù)作為常規(guī)數(shù)據(jù)庫(kù)擴(kuò)充 由于空間數(shù)據(jù)庫(kù)系統(tǒng)理論和技術(shù)還處于發(fā)展過(guò)程當(dāng)中，而實(shí)際應(yīng)用的需求又非常迫切，同時(shí)常規(guī)數(shù)據(jù)庫(kù)（關(guān)系數(shù)據(jù)庫(kù)）仍然是當(dāng)今主流數(shù)據(jù)庫(kù)，所以目前空間數(shù)據(jù)庫(kù)是作為常規(guī)、傳統(tǒng)數(shù)據(jù)庫(kù)的擴(kuò)充出現(xiàn)。在這種情況下，空間數(shù)據(jù)庫(kù)主要包括下述一些方面的內(nèi)容：2022-2-165 空間數(shù)據(jù)模型空間數(shù)據(jù)模型 基于實(shí)際應(yīng)用，引入各種必須的空間數(shù)據(jù)類(lèi)型，并討相應(yīng)的數(shù)據(jù)操作。 空間索引空間索引 由于空間對(duì)象之間難以合適的定義“序”，所以空間數(shù)據(jù)的索引就成為空間數(shù)據(jù)庫(kù)技術(shù)的一個(gè)重要課題，在這方面已經(jīng)取得了相

3、當(dāng)成熟的結(jié)果，并且應(yīng)用到其他的領(lǐng)域。 空間數(shù)據(jù)庫(kù)管理系統(tǒng)空間數(shù)據(jù)庫(kù)管理系統(tǒng) 空間數(shù)據(jù)模型和當(dāng)前主流數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型具有較大的差異，需要研究如何在RDBMS基礎(chǔ)上有效擴(kuò)充空間數(shù)據(jù)管理功能的問(wèn)題。2022-2-16610.2 空間數(shù)據(jù)模型空間數(shù)據(jù)模型 10.2.1空間數(shù)據(jù)模型空間數(shù)據(jù)模型 空間數(shù)據(jù)模型與其它數(shù)據(jù)模型相比，一個(gè)突出的特點(diǎn)就是其模型的提出、引入與相應(yīng)的實(shí)際應(yīng)用密切相關(guān)。 空間數(shù)據(jù)庫(kù)的一個(gè)重要應(yīng)用領(lǐng)域是GIS。人們通常就以GIS為應(yīng)用背景，介紹其中的基本空間數(shù)據(jù)類(lèi)型。我們這里的介紹主要以二維空間數(shù)據(jù)類(lèi)型為主，但完全可以推廣到三維以上的情形。2022-2-167 在GIS中，基本空間數(shù)

4、據(jù)類(lèi)型由下述三種空間對(duì)象組成： （1）點(diǎn)點(diǎn)（Point） 例如城市。點(diǎn)只表示其空間位置，不表示其范圍（extent） （2）線線（Line）例如河流、道路、管道、航線、等高線、等降雨線、通信或電力線路等。線不僅表示線上各點(diǎn)在空間的位置，而且還有長(zhǎng)度，即表示其在空間的延伸范圍。 （3）區(qū)域區(qū)域（Region）例如森林、湖泊、行政區(qū)域等。區(qū)域不但有位置，而且有面積、周長(zhǎng)等參數(shù)，以表示其覆蓋范圍。2022-2-168 以上三種是最基本空間數(shù)據(jù)類(lèi)型，以此為基礎(chǔ)，還可以導(dǎo)出下面兩種空間數(shù)據(jù)類(lèi)型： （4）劃分劃分（Partition）一個(gè)區(qū)域可以是按其自然、行政或其他特征，分成若干個(gè)區(qū)域。如果這些子區(qū)域互

5、不相交，但其“并”覆蓋該區(qū)域，則此子區(qū)域的集合就稱為該區(qū)域的一個(gè)劃分。國(guó)家行政區(qū)域劃分圖，土地利用圖等都是劃分的例子。劃分可嵌套，例如國(guó)家分成省市，省市分成縣區(qū)、縣區(qū)分成鄉(xiāng)鎮(zhèn)等。2022-2-169 （5）網(wǎng)絡(luò)網(wǎng)絡(luò)（Network）網(wǎng)絡(luò)是由若干點(diǎn)和一些點(diǎn)與點(diǎn)之間的聯(lián)線組成。例如公路網(wǎng)、河網(wǎng)、電力網(wǎng)、電話網(wǎng)、交通線路圖等都是網(wǎng)絡(luò)的例子。2022-2-161010.2.2空間對(duì)象所處的環(huán)境空間對(duì)象所處的環(huán)境 1.歐氏空間歐氏空間 設(shè)R表示實(shí)數(shù)域，V是R上向量的非空集合，如果在V上定義了滿足如下條件并稱之為內(nèi)積的一個(gè)二元函數(shù)，則稱V為R的歐氏空間： 非負(fù)性 0，=0 x=0， xV 對(duì)稱性 = 線性

6、性 = +，R；x，y，zV 直線R，平面R2和空間R3通過(guò)適當(dāng)?shù)亩x內(nèi)積都是歐氏空間。2022-2-1611 2.在歐氏空間中討論空間對(duì)象間的關(guān)系在歐氏空間中討論空間對(duì)象間的關(guān)系 我們主要在歐氏空間的環(huán)境中定義所有空間對(duì)象相互間關(guān)系的，這些關(guān)系可以分為基于集合、拓?fù)洹?方位和.度量的關(guān)系，我們?cè)谙旅娣謩e討論。2022-2-161210.2.3 空間對(duì)象之間關(guān)系空間對(duì)象之間關(guān)系 1.基于集合的關(guān)系基于集合的關(guān)系 基于集合的空間對(duì)象關(guān)系主要有元素與集合的屬于及不屬于的關(guān)系，集合與集合的包含、相交、并等關(guān)系。在空間對(duì)象間的層次關(guān)系就適合用集合的關(guān)系理論來(lái)討論，例如城市包含公園，公園包含樹(shù)林等。20

7、22-2-1613 2.基于拓?fù)涞年P(guān)系基于拓?fù)涞年P(guān)系 基于拓?fù)涞目臻g對(duì)象關(guān)系主要有鄰接（meet）、包含（within）和交疊（overlap），這三類(lèi)拓?fù)潢P(guān)系也是空間數(shù)據(jù)查詢中最有可能出現(xiàn)的情況?？臻g數(shù)據(jù)庫(kù)中，基于拓?fù)涞牟樵冃枰鉀Q這樣兩個(gè)問(wèn)題： 查詢所有與給定對(duì)象具有某種拓?fù)潢P(guān)系R的空間對(duì)象。 對(duì)象A和B具有怎樣的拓?fù)潢P(guān)系。2022-2-1614 在平面上，兩個(gè)對(duì)象A和B之間的二元拓?fù)潢P(guān)系時(shí)基于以下對(duì)象成分的相交（insection）關(guān)系： A的內(nèi)部A?，A的邊界A，A的外部A-。 B的內(nèi)部B?，B的邊界B，B的外部B-。2022-2-1615 對(duì)象的這六個(gè)部分分別構(gòu)成九種相交情況： A?

8、B， A?B，A? B- ； AB?，A B，A B-； A- B? ， A-B， A-B-。2022-2-1616 考慮到0，1取值情況0，1，可以確定有29=512種二元拓?fù)潢P(guān)系，這里，人們研究其中的八種彼此互斥關(guān)系： 相離（disjoint），鄰接（meet），交疊（overlap），相等（equal），包含（contain），在內(nèi)部（inside），覆蓋（cover）和被覆蓋（covered by）。2022-2-1617 3.基于方位的關(guān)系基于方位的關(guān)系 絕對(duì)方位 即在全球定位系統(tǒng)背景下定義的方位，例如東、西、南、北，東南、西南、東北等。 相對(duì)方位 即根據(jù)與給定目標(biāo)的方向來(lái)定義的方位

9、，例如左右、前后、上下等。 基于觀察者的方位 即按照專門(mén)指定的稱為觀察者參照對(duì)象來(lái)定義的方位。2022-2-1618 4.基于度量的關(guān)系基于度量的關(guān)系 設(shè)有一個(gè)集合E，如果在E上定義了一個(gè)二元函數(shù)d（x，y），x，yE，滿足如下條件： （1）非負(fù)性非負(fù)性 d（x，y）0 （2）對(duì)稱性對(duì)稱性 d（x，y）= d（y，x） （3）三角不等性三角不等性 d（x，y）d（x，z）+ d（z，y） 則稱V是一個(gè)度量空間，d（x，y）稱為V上的度量函數(shù)。2022-2-1619 考察一個(gè)空間的“測(cè)度”，例如線段的長(zhǎng)度，平面圖形的面積，空間立體的體積，以及一個(gè)空間對(duì)象相對(duì)于另一個(gè)空間對(duì)象的距離等都是基于度量的

10、關(guān)系。2022-2-162010.2.4空間數(shù)據(jù)操作的謂詞描述空間數(shù)據(jù)操作的謂詞描述 從理論上講，空間數(shù)據(jù)操作特別是空間數(shù)據(jù)查詢的基礎(chǔ)是空間對(duì)象之間的相互關(guān)系，從實(shí)際上看，由于空間數(shù)據(jù)類(lèi)型取決于實(shí)際應(yīng)用，空間數(shù)據(jù)操作主要也由現(xiàn)實(shí)中的應(yīng)用所決定。下面主要介紹一些從空間對(duì)象相互關(guān)系角度考慮的相對(duì)比較基本的通用操作，而由應(yīng)用的多樣性，與應(yīng)用密切相關(guān)的操作不擬一一介紹?？臻g數(shù)據(jù)操作的描述可以有謂詞形式、集合形式和代數(shù)形式三種。 2022-2-1621 1.基本符號(hào)基本符號(hào) 先定義空間數(shù)據(jù)操作中的一些記號(hào)。 SDT 空間數(shù)據(jù)類(lèi)型 ZS 大小為零（zero size）空間數(shù)據(jù)類(lèi)型，例如點(diǎn) NZS 大小非零

11、（non-zero size）的空間數(shù)據(jù)類(lèi)型，例如線、區(qū)域等 ADT 原子（atomic）空間數(shù)據(jù)類(lèi)型 例如點(diǎn)、線、區(qū)域 CDT 集合型（collection）空間數(shù)據(jù)類(lèi)型，例如網(wǎng)絡(luò)、劃分等2022-2-1622 PT 點(diǎn) LN 線 RG 區(qū)域 PTN 劃分 NTW 網(wǎng)絡(luò)2022-2-1623 2.基于拓?fù)涞拿枋龌谕負(fù)涞拿枋?兩個(gè)同類(lèi)型空間數(shù)據(jù)是否相等（= 或 ） PTPT Bool LNLN Bool RGRG Bool 空間數(shù)據(jù)SDT是否在區(qū)域RG中（INSERT） SDT RG Bool2022-2-1624 兩個(gè)大小非零的空間數(shù)據(jù)是否相交（INTERSECTS） NZS NSZ Bo

12、ol 兩個(gè)區(qū)域是否鄰接（ISNEIGHBOROF） RGRGBool2022-2-1625 3.基于集合運(yùn)算的描述基于集合運(yùn)算的描述 （1）相交（Intersection） 兩條線相交為點(diǎn)的集合 LNLNPT 線與區(qū)域相交為線的集合 LNRGLN 區(qū)域與區(qū)域相交為區(qū)域的集合 RGRGRG2022-2-1626 （2）重疊（OVERLAP） PTNPTNFG （3）中心點(diǎn)（CENTER） NZSPT2022-2-1627 4.基于度量的描述基于度量的描述 兩點(diǎn)間距離（DIST） PTPT NUM DIST 兩空間圖形間的最大、最小距離（MAXDIST，MINDIST） SDTSDTNUM MAX

13、DIST或MINDIST2022-2-1628 多點(diǎn)的直徑（DIAMETER） PT NUMDIAMETER 線的長(zhǎng)度（LENGTH） LN NUM LENGTH 區(qū)域的周長(zhǎng)（PERIMETER）或面積（AREA） RG NUM PERIMETER 或AREA2022-2-162910.2.5空間關(guān)系的集合描述與判斷空間關(guān)系的集合描述與判斷 在空間數(shù)據(jù)庫(kù)中，空間關(guān)系主要用于查詢。為了獲得可以接受的查詢效率，常常把空間對(duì)象用點(diǎn)、矩形和方盒等簡(jiǎn)單，規(guī)則的圖形表示。因此，只需要討論這些規(guī)則幾何圖形的空間關(guān)系即可。這里，規(guī)則的幾何圖形可以看做空間中標(biāo)準(zhǔn)的“點(diǎn)集合”，因此，空間數(shù)據(jù)操作的集合描述就是這些

14、標(biāo)準(zhǔn)集合間關(guān)系的描述。 2022-2-1630 1.一維空間中兩個(gè)線段的關(guān)系一維空間中兩個(gè)線段的關(guān)系 一維空間中兩個(gè)線段的7種可能的關(guān)系，分別用記號(hào)“=、%、/、|、”表示。圖10-4表示了這些關(guān)系，其中，（1）（5）是相交關(guān)系，（6）（7）是非相交關(guān)系。 設(shè)A、B線段的起點(diǎn)和終點(diǎn)分別為x1A，x2A，x1B，x2B，則（1）（5）的關(guān)系可以歸納為maxx1A，x1Bminx2B，x2B2022-2-16312022-2-1632 2.二維空間中邊平行于坐標(biāo)軸矩形間的關(guān)系二維空間中邊平行于坐標(biāo)軸矩形間的關(guān)系 設(shè)A、B為這種矩形，其左下角坐標(biāo)和右上角坐標(biāo)分別為（x1A，y1A），（x2A，y2A

15、）和（x1B，y1 B），（x2 B，y2 B）。可以得到，如果A和B在x軸和y軸上的投影分別相交，則A、B相交。因此，A，B相交的條件可以表示為 max x1A，x1B min x2A，x2B 和max y1A，y1B min y2A，y2B 2022-2-163310.2.6空間關(guān)系的代數(shù)描述與運(yùn)算空間關(guān)系的代數(shù)描述與運(yùn)算 空間代數(shù)運(yùn)算的特點(diǎn)在于選擇條件或連接條件中出現(xiàn)空間謂詞。投影、集合運(yùn)算不涉及空間謂詞，與關(guān)系代數(shù)沒(méi)有本質(zhì)區(qū)別。下面討論空間選擇和空間連接。2022-2-1634 1.空間選擇空間選擇 例例10-1 寫(xiě)出下列空間選擇表達(dá)式。 選擇廣東省所有城市： F（城市）其中，F(xiàn)=CE

16、NTER（城市地圖）INSIDE 廣東; 城市是關(guān)系名，其中有屬性“城市名”、“人口”、“城市地圖”。城市地圖表示市區(qū)及其周邊地區(qū)，“廣東”是一個(gè)區(qū)域名稱。顯然，如果城市中心點(diǎn)在廣東省區(qū)域內(nèi)，則該城市一定屬于廣東省 2022-2-1635 選擇廣東省的所有河流： F（河流）其中 F=ROUTE（河流）INSIDE廣東; “河流”是關(guān)系名，其中有屬性“河流流域圖”。ROUTE是空間數(shù)據(jù)庫(kù)中的一個(gè)函數(shù)，計(jì)算河流、道路等的中心線。 選擇距離廣州小于等于100000米，人口大于等于50萬(wàn)的所有城市： F（城市，廣東區(qū)域圖）其中F=DIST（城市名，廣州）500000; 城市是個(gè)關(guān)系，“廣州”是城市名，

17、F中的第一個(gè)謂詞是空間謂詞，要用到廣東省地圖。2022-2-1636 2.空間連接空間連接 例例10-2 對(duì)每條河流找出沿河10000米的所有城市 設(shè)“河流”、“城市”是兩個(gè)關(guān)系。在關(guān)系“河流”中，有屬性“河流流域圖”。如果城市中心距離河流小于等于10000米，則該城市和河流匹配?？梢杂每臻g連接表示如下： 河流名，城市名（河流 F城市） 其中，F(xiàn)=Mindist（城市名，ROUTE（河流流域圖）100002022-2-163710.2.7空間數(shù)據(jù)查詢語(yǔ)言空間數(shù)據(jù)查詢語(yǔ)言 一般在SQL語(yǔ)言基礎(chǔ)上擴(kuò)充空間數(shù)據(jù)類(lèi)型及其操作和相應(yīng)的保留字。由于這些擴(kuò)充與應(yīng)用有關(guān)，目前還未形成標(biāo)準(zhǔn)，以下列舉一些例子予以

18、說(shuō)明。2022-2-1638 例例 10-3 選擇廣東省所有城市及其人口： select 城市名，人口 from 城市 where center（城市地圖）inside廣東?。?022-2-1639 選擇流經(jīng)廣東省所有河流的河流名及其在廣東省境內(nèi)的長(zhǎng)度： select 河流名，length（intersection（route（河流流域圖），廣東） from 河流 where route（河流流域圖）intersects廣東；2022-2-1640 選擇距離廣州小于等于100000米，人口大于等于50萬(wàn)的所有城市： select 城市名，人口 from 城市，廣東區(qū)域圖 where dist（

19、城市名，廣州）500000；2022-2-1641 例例10-4 將例10-2表示的查詢用SQL風(fēng)格表示出來(lái) select 河流名，城市名 from 河流，城市 where mindist（城市名，ROUTE（河流流域圖）=100002022-2-164210.3 空間索引空間索引 空間數(shù)據(jù)庫(kù)查詢的開(kāi)銷(xiāo)一般比關(guān)系數(shù)據(jù)庫(kù)大，特別是空間謂詞求值的開(kāi)銷(xiāo)遠(yuǎn)比數(shù)值或字符串的比較要大。若采用順序掃描方法進(jìn)行查詢，則效率就會(huì)很低，因此采取空間索引十分必要的。2022-2-164310.3.1空間索引概述空間索引概述 1.空間索引的思路空間索引的思路 為了減少開(kāi)銷(xiāo)，通常是采用近似規(guī)則圖形例如邊平行于坐標(biāo)軸的最

20、小矩形來(lái)代替不規(guī)則土星進(jìn)行查詢。這種矩形就稱為不規(guī)則區(qū)域的最小限定矩形（minimum bounding rectangle ，MBR）。設(shè)MBR左下角坐標(biāo)為（x1，y1），右上角為（x2，y2），則x1，y1就分別為空間對(duì)象的最小橫坐標(biāo)和縱坐標(biāo)，x2，y2分別為空間對(duì)象的最大橫坐標(biāo)和縱坐標(biāo)。不但區(qū)域可以用MBR近似表示，線也可以用MBR近似表示；進(jìn)一步，不但單個(gè)空間對(duì)象可以用MBR近似表示，有時(shí)MBR還可以包含多個(gè)空間對(duì)象。最小限定矩形如下圖所示。2022-2-16442022-2-1645 如果一個(gè)MBR還含有另外的MBR，則稱其為目錄MBR，否則就稱為對(duì)象MBR。 如果兩個(gè)空間對(duì)象相交，

21、則相應(yīng)的MBR也相交；如果兩個(gè)MBR不相交，則對(duì)應(yīng)的兩個(gè)空間對(duì)象也不相交。這樣，用MBR代替空間對(duì)象檢查相交情況，就可以排除一批不相交的對(duì)象。 2022-2-1646 當(dāng)然，兩個(gè)MBR相交，并不能得出對(duì)應(yīng)的空間對(duì)象一定相交，此時(shí)還需要用精確方法對(duì)MBR相交的空間對(duì)象逐個(gè)進(jìn)行檢驗(yàn)，找出真正相交的情形。先用高效率的近似方法進(jìn)行粗選，再用精確方法 進(jìn)行精選，這是空間數(shù)據(jù)庫(kù)中常用的搜索方式。2022-2-16472.空間索引的特點(diǎn)空間索引的特點(diǎn) （1）索引對(duì)象的無(wú)序性）索引對(duì)象的無(wú)序性 （2）索引對(duì)象的不規(guī)則性）索引對(duì)象的不規(guī)則性 （3）索引對(duì)象的交叉性）索引對(duì)象的交叉性2022-2-164810.3

22、.2空間對(duì)象的近似表示空間對(duì)象的近似表示 1.點(diǎn)點(diǎn) 點(diǎn)不但是基本的空間數(shù)據(jù)類(lèi)型之一，而且多屬性的檢索也相當(dāng)于多維空間點(diǎn)的搜索。有些規(guī)則圖形也可以用高維空間的點(diǎn)表示。例如一維空間的線段a,b可以用二維空間的點(diǎn)（a，b）表示。二維空間的邊平行于坐標(biāo)軸的矩形（x1，y1），（x2，y2）可以用四維空間的點(diǎn)（x1，y1，x2，y2）表示，式中（x1，y1），（x2，y2）分別為矩形的左下角和右上角坐標(biāo)。2022-2-1649 2.矩形或方盒矩形或方盒 矩形和方盒不但是近似表示不規(guī)則空間對(duì)象的簡(jiǎn)單、有效手段，也是劃分子空間的首選圖形。2022-2-1650 3.柵格（柵格（grid） 用柵格表示空間對(duì)象

23、，類(lèi)似于用點(diǎn)陣、像素陣列表示二維圖像，原則上可以推廣到高維空間，但主要用于二維空間2022-2-16512022-2-16522022-2-1653 每個(gè)區(qū)域都可以近似表示為二進(jìn)制串的集合。這種二進(jìn)制串的集合稱為該區(qū)域的Z元素（Z-element）。要檢查兩個(gè)區(qū)域是否相交或包含，可以按序比較兩個(gè)區(qū)域的Z元素。比較時(shí)，如果一個(gè)二進(jìn)制串是另一個(gè)二進(jìn)制串的前綴，則后者所代表的區(qū)域必然包含于前者所代表的區(qū)域中，例如100101一定包含在1001中。 2022-2-1654 用Z次序的柵格表示區(qū)域，可以把本是二維的空間對(duì)象，用一維的有序二進(jìn)制串序列表示。因此，空間對(duì)象所占的區(qū)域，可以用二進(jìn)制串作為索引鍵

24、，組成一個(gè)B樹(shù)。下面是A，B區(qū)域的Z元素，經(jīng)掃描比較，可以找出它們的重疊部分。2022-2-1655 重疊部分：（A1,B1）, （A1,B2）（A1,B3），（B1,A2），（B1,A3），。 在上面的重疊欄中，二元組的第一項(xiàng)覆蓋第二項(xiàng)。2022-2-165610.3.3 基于大小非零空間對(duì)象查詢的基于大小非零空間對(duì)象查詢的R樹(shù)樹(shù) 空間索引按照其操作對(duì)象的不同可以分為兩類(lèi)。 以空間點(diǎn)為查詢對(duì)象的索引 例如kd樹(shù)和G-樹(shù)技術(shù)（kd樹(shù)和G樹(shù)可以參考有關(guān)的空間數(shù)據(jù)庫(kù)書(shū)籍）。 以非點(diǎn)的空間圖形為查詢對(duì)象的索引，例如R-樹(shù)等技術(shù)。 下面，我們主要討論基于測(cè)度非零的空間圖形的R-樹(shù)技術(shù)。2022-2-1

25、657 R樹(shù)主要以矩形（Rectangle）為檢索對(duì)象，這就是R樹(shù)命名的 由來(lái)。R樹(shù)是由Guttmann于1984年提出。與B+樹(shù)相似，G樹(shù)是一種平衡多分樹(shù)；與B+樹(shù)不同，R樹(shù)不是通過(guò)逐級(jí)比較索引鍵的值來(lái)搜索要找的對(duì)象。而是通過(guò)逐級(jí)縮小搜索的空間范圍來(lái)定位要找的對(duì)象。搜索的空間范圍在二維空間中就用MRB表示。 2022-2-1658 如果一個(gè)MRB中含有其他的MRB，則稱其為目錄MRB，否則就稱為對(duì)象MRB。在R樹(shù)中，每個(gè)索引項(xiàng)都是一個(gè)二元組（r，p），其中r表示MBR，p表示相應(yīng)指針。對(duì)于葉結(jié)點(diǎn)，p指向r所近似表示的空間對(duì)象；在非葉結(jié)點(diǎn)，p指向含有r的子節(jié)點(diǎn)。2022-2-1659 一個(gè)結(jié)點(diǎn)

26、最多可有M個(gè)索引項(xiàng)，至少有m個(gè)索引項(xiàng)。M一般在2與M/2之間選擇。由于R樹(shù)在分裂時(shí)涉及到區(qū)域的優(yōu)化與調(diào)整，開(kāi)銷(xiāo)較大，為了減少分裂概率，m宜選擇較低數(shù)值。有實(shí)驗(yàn)結(jié)果，m在0.4M左右可以獲得較好的性能。2022-2-1660 R樹(shù)具有如下基本性質(zhì) 根結(jié)點(diǎn)至少有兩個(gè)索引項(xiàng)，除非個(gè)結(jié)點(diǎn)是R樹(shù)的唯一結(jié)點(diǎn)； 每個(gè)非葉結(jié)點(diǎn)有m到M個(gè)索引項(xiàng)； 在上述約束條件下，保持樹(shù)的平衡。 下圖（a）表示了外包矩形的取法，（b）是其對(duì)應(yīng)的R樹(shù)的取法。2022-2-16612022-2-16622022-2-1663 2.R樹(shù)的查詢樹(shù)的查詢 設(shè)給定矩形Rq=（x1，y1），（x2，y2），其中（x1，y1），（x2，y2）

27、分別為Rq的左下角和右上角坐標(biāo)，要查詢其中所包含的空間對(duì)象。在查詢時(shí)，首先從R樹(shù)的根結(jié)點(diǎn)開(kāi)始。2022-2-1664 如果根結(jié)點(diǎn)中的索引項(xiàng)是對(duì)象，由于這些索引項(xiàng)是無(wú)序的，需要逐個(gè)檢查每個(gè)對(duì)象MBR是否包含在Rq中，如果包含在Rq中，則此對(duì)象就是選中的對(duì)象之一。設(shè)對(duì)象MBR為R0=（x3，y3），（x4，y4），式中（x3，y3），（x4，y4），分別為R0的左下角和右上角坐標(biāo)。R0包含在Rq中的條件為 x3x1 and y3y1 and x4x2 and y4y22022-2-1665 如果根結(jié)點(diǎn)中的索引項(xiàng)是目錄MBR，則逐個(gè)檢查個(gè)目錄MBR是否與Rq相交。如果相交，則此目錄MBR中的對(duì)象MB

28、R就有可能包含在Rq中，需要沿此目錄MBR繼續(xù)搜索；如果目錄MBR與Rq不相交，則其中的對(duì)象MBR就不可能包含在Rq中，就不必沿此目錄繼續(xù)向下搜索，相交的條件參見(jiàn)前述小節(jié)。當(dāng)搜索到葉結(jié)點(diǎn)時(shí)，則與前面一樣，逐個(gè)檢查其中對(duì)象MBR是否包含在中。如果目錄MBR之間有重疊，雖然重疊區(qū)中的對(duì)象只屬于一個(gè)目錄MBR，但是判定它屬于哪一個(gè)目錄MBR，仍然需要多路搜索。2022-2-1666 3.R樹(shù)的插入樹(shù)的插入 插入是R樹(shù)中開(kāi)銷(xiāo)最大的操作，對(duì)其性能影響很大，因而研究較多。設(shè)（R1，p）是待插入的對(duì)象MBR及其指向?qū)ο蟮闹羔?。與R+樹(shù)不同，插入哪個(gè)葉結(jié)點(diǎn)以及在葉結(jié)點(diǎn)的次序不是唯一的。R1插入哪個(gè)葉結(jié)點(diǎn)決定于它屬于哪個(gè)目錄MBR，至于它在葉結(jié)點(diǎn)中的次序是無(wú)關(guān)緊要的，因?yàn)榭臻g對(duì)象本來(lái)是無(wú)序的。R1可能與多個(gè)目錄MBR相交或相鄰，這些目錄MBR只要其中的對(duì)象MBR不超過(guò)最大值，經(jīng)過(guò)