空間索引與優(yōu)化分解課件

1、第五章 空間索引與查詢優(yōu)化 2013.4第五章 空間索引與查詢優(yōu)化第一節(jié) 空間索引第二節(jié) 空間查詢優(yōu)化一部工具書好比是一個微型數(shù)據(jù)庫；工具書的索引，就好比進(jìn)入它的數(shù)據(jù)庫的鑰匙。 數(shù)據(jù)庫的索引用來快速訪問一條特定查詢所請求的數(shù)據(jù)，而無需遍歷整個數(shù)據(jù)庫。 第一節(jié) 空間索引定義索引：索引是一種獨立的對象，用來快速地尋找那些具有特定值的記錄索引要占用存儲空間索引可以減少全表掃描，從而提高檢索速度例如：學(xué)生信息表student如下：學(xué)號姓名性別年齡系別001aaa男19計算機(jī)002bbb男20城環(huán)系003ccc女19城環(huán)系004ddd男18中文系005eee女18中文系006fff女20計算機(jī)查詢005

2、號學(xué)生的信息：SELECT * FROM student WHERE 學(xué)號=005學(xué)號姓名性別年齡系別001aaa男19計算機(jī)002bbb男20城環(huán)系003ccc女19城環(huán)系004ddd男18中文系005eee女18中文系006fff女20計算機(jī)學(xué)號姓名性別年齡系別001aaa男19計算機(jī)002bbb男20城環(huán)系003ccc女19城環(huán)系004ddd男18中文系005eee女18中文系006fff女20計算機(jī)建立索引學(xué)號位置001002003004005006例如：查找經(jīng)過河南省的所有河流。常規(guī)方法：檢查所有河流和河南省省界是否相交。 缺點：用實際空間對象比較，算法復(fù)雜，計算開銷大、IO開銷大。

3、索引方法：記錄河流和省界的外接矩形。用外接矩形進(jìn)行比較?？臻g屬性表描述要素的一般信息，空間索引表描述要素所在格網(wǎng)的信息，要素描述表描述要素的點數(shù)，范圍等信息，三張表通過FID（Feature ID）關(guān)聯(lián) 定義空間索引：空間索引就是指依據(jù)空間對象的位置和形狀或空間對象之間的某種空間關(guān)系，按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對象的概要信息，如對象的標(biāo)識、外接矩形及指向空間對象實體的指針。 空間索引的基本思想，也是空間查詢的基本思想，即近似體的使用。讓索引結(jié)構(gòu)按照一個或多個空間碼來管理對象，這些空間碼是比對象本事更簡單的幾何對象。常見的空間索引：對象范圍索引格網(wǎng)索引四叉樹索引R樹和R+樹索引

4、BSP樹索引一、對象范圍索引 在記錄每個空間實體的坐標(biāo)時，記錄包圍每個空間實體的外接矩形的最大最小坐標(biāo)。在檢索空間實體時，根據(jù)空間實體的最大最小范圍，預(yù)先排除那些沒有落入檢索窗口內(nèi)的空間實體，僅對那些外接矩形落在檢索窗口的空間實體作進(jìn)一步的判斷，真正落入窗口內(nèi)的空間實體。 ABCEFD 基于實體范圍的空間數(shù)據(jù)檢索這種方法沒有創(chuàng)建真正的空間索引文件，而是在空間對象的數(shù)據(jù)文件中增加了矩形范圍，主要依靠空間計算進(jìn)行判別。查詢時仍需要對整個數(shù)據(jù)文件的空間對象進(jìn)行檢索，只是某些對象可以通過矩形范圍予以直接判別，而有些對象仍需要進(jìn)行復(fù)雜計算才能判別。雖然該方法仍需要花費大量時間來進(jìn)行空間檢索，但隨著計算機(jī)

5、的處理速度的加快，這種方法在一定程度上能夠滿足查詢檢索的效率要求 對象范圍索引 IDXmaxXminYmaxYmin123空間對象不被檢索Xmax XW OR Xmin XE OR Ymax YS OR Ymin YN空間對象被檢索Xmax XW and XminXE AND Ymax YS and YminYN空間對象集合123456檢索窗口YNXWXEYS4xmaxxminyminymaxxy在進(jìn)行空間范圍查詢時，分為兩級過濾（篩選）：初次過濾根據(jù)空間要素外包絡(luò)矩形來過濾掉大部分不在查詢范圍的空間要素；第二級過濾則用查詢空間范圍直接和初次過濾結(jié)果集中空間要素的二進(jìn)制邊界坐標(biāo)比較，從而得到查

6、詢的準(zhǔn)確結(jié)果。對象范圍索引 5123412312二、格網(wǎng)索引 將研究區(qū)域用橫豎線條劃分大小相等和不等的格網(wǎng)，記錄每一個格網(wǎng)所包含的空間實體用戶進(jìn)行空間查詢時，首先計算出用戶查詢對象所在格網(wǎng)，然后再在該網(wǎng)格中快速查詢所選空間實體通常是把整個數(shù)據(jù)庫數(shù)值空間劃分成3232（或6464）的正方形網(wǎng)格，建立另一個倒排文件柵格索引。 每一個網(wǎng)格在柵格索引中有一個索引條目(記錄)，在這個記錄中登記所有位于或穿過該網(wǎng)格的物體的關(guān)鍵字。ABCDEF21232931535561632022283052546062171925274951575916182426485056585713153739454746121

7、43638444613911333541430281032344042Peano鍵空間對象7B12E13E14E15E24E25A,E26E27E32D33D35D,F37E38D39E45E50E51E54C55C56E57E60C空間對象Peano鍵集A25-25B7-7C54-55C60-60D32-33D35-35D38-38E12-15E24-27E37-37E39-39E48-51E45-45E56-57F35-35空 間 索 引對 象 索 引檢索原理：第一階段（RDBMS完成）：接收SQL語句，獲取空間過濾器的封裝邊界檢測空間過濾器的封裝邊界跨越的網(wǎng)格到空間索引表中檢索出封裝邊界

8、所在網(wǎng)格內(nèi)的要素第二階段：幾何過濾器的封裝邊界與第一階段檢索出的要素的邊界相比較，找出具有重疊關(guān)系的要素第三階段幾何過濾器的坐標(biāo)與第二階段檢索出的要素的邊界比較，找出邊界在幾何過濾器內(nèi)的要素第四階段：幾何過濾器的坐標(biāo)與第三階段檢索出的要素的比較，找出最終在幾何過濾器內(nèi)的要素類ABCDEFGH6713154512141391102810ABCDEFGH6713154512141391102810第一階段:(1)接收SQL語句，獲取空間過濾器的封裝邊界(2)檢測空間過濾器的封裝邊界跨越的網(wǎng)格(3)到空間索引表中檢索出封裝邊界所在網(wǎng)格內(nèi)的要素CEFGH6713154512141391102810第二

9、階段:幾何過濾器的封裝邊界與第一階段檢索出的要素的邊界相比較，找出具有重疊關(guān)系的要素EFGH6713154512141391102810第三階段:幾何過濾器的坐標(biāo)與第二階段檢索出的要素的邊界比較，找出邊界在幾何過濾器內(nèi)的要素EFGH6713154512141391102810第四階段:幾何過濾器的坐標(biāo)與第三階段檢索出的要素的坐標(biāo)比較，找出最終在幾何過濾器內(nèi)的要素類按格網(wǎng)法對空間數(shù)據(jù)進(jìn)行索引時，所劃分的格網(wǎng)數(shù)不能太多，否則，索引表本身太大而不利于數(shù)據(jù)的索引和檢索 三、四叉樹索引二維空間范圍被劃分為一系列大小相等的棋盤狀矩形，即將地理空間的長和寬在X和Y方向上進(jìn)行2N等分，形成2N2N的網(wǎng)格，并以

10、此建立N級四叉樹。四叉樹是具有一個根節(jié)點,其中的每個中間節(jié)點都有四個孩子。四叉樹的每個節(jié)點對應(yīng)一個正方形。四叉樹及其子分割在建立四叉樹索引時，根據(jù)所有空間對象覆蓋的范圍，進(jìn)行四叉樹分割，使每個子塊中包含單個實體，然后根據(jù)包含每個實體的子塊層數(shù)或子塊大小，建立相應(yīng)的索引。在四叉樹索引中，大區(qū)域空間實體更靠近樹的根部，小實體位于葉端，以不同的分辨率來描述不同實體的可檢索性 用線性四叉樹組織的空間索引57E1315GB46121413028AFDCPeano邊長空間對象04E02D01A41F82C151G,B第一階段（RDBMS完成）：接收SQL語句，獲取空間過濾器的封裝邊界將空間索引四等分，每一

11、份與空間過濾器的封裝邊界的邊界比較，取出與空間過濾器的封裝邊界沒有重疊的網(wǎng)格（這些網(wǎng)格不再分）將得到的部分繼續(xù)四等分，與空間過濾器的封裝邊界的邊界比較。第二階段：幾何過濾器的封裝邊界與第一階段檢索出的要素的邊界相比較，找出具有重疊關(guān)系的要素第三階段幾何過濾器的坐標(biāo)與第二階段檢索出的要素的邊界比較，找出邊界在幾何過濾器內(nèi)的要素第四階段：幾何過濾器的坐標(biāo)與第三階段檢索出的要素的比較，找出最終在幾何過濾器內(nèi)的要素類檢索原理：ABCDE四、BSP樹索引BSP樹（Binary Space Partition Tree）：空間二叉樹算法對于要處理的一組空間對象，選擇一個平面，將該對象分成兩組（如果某個對象

12、與該平面相交，則用這個平面將這個對象分成兩個對象），作為該節(jié)點的兩個孩子，然后分別對兩個對象用相同的方法，直到滿足一個特定的條件（通常是到節(jié)點上只有一個對象）為止。一般來說，選擇的平面盡量不要把同一對象分成兩個。原理：第一階段（1）接收查詢語句，從中獲取空間過濾器的封裝邊界；（2）以空間過濾器封裝邊界的第一條邊為界，將空間索引表分成兩部分，取空間過濾器一側(cè)的要素進(jìn)行索引；（3）按某一方向，選擇第二條、第三條和第四條邊為邊界，分別除去在封裝邊界外測的要素第二階段將空間過濾器的幾何坐標(biāo)和第一階段選擇出的要素的封裝邊界進(jìn)行比較，得到索引結(jié)果第三階段將空間過濾器的幾何坐標(biāo)和第二階段選擇出的要素的幾何坐

13、標(biāo)進(jìn)行比較，得到最終的索引結(jié)果。B樹對于一維升序或降序數(shù)據(jù)序列（假設(shè)其個數(shù)為N）來說，可以采用兩分檢索的方法來迅速地找到需要插入或刪除元素的位置。 順序表：插入一個元素，需要將其以下的數(shù)據(jù)均進(jìn)行后移刪除一個元素，需要將以下的數(shù)據(jù)進(jìn)行前移。提高插入和刪除的工作效率，研究者提出了多種解決方法，B樹就是其中較好的一種方案。B樹是由一系列節(jié)點所構(gòu)成它的每一個節(jié)點均由2m個數(shù)據(jù)域和2m+1個指針域所構(gòu)成每個節(jié)點的數(shù)據(jù)從左向右成升序排列一般情況下，B樹的每個節(jié)點中的數(shù)據(jù)域不一定存放滿數(shù)據(jù)，但基本上每個節(jié)點存放的數(shù)據(jù)數(shù)大于m個。 例如：插入數(shù)據(jù)0.660.66例如：插入數(shù)據(jù)0.10由此可以看出：B樹中同一鍵

14、值不會出現(xiàn)多次并且它有可能出現(xiàn)在葉結(jié)點，也有可能出現(xiàn)在非葉結(jié)點中。因為B樹鍵位置不定，且在整個樹結(jié)構(gòu)中只出現(xiàn)一次，雖然可以節(jié)省存儲空間，但使得在插入、刪除操作復(fù)雜度明顯增加。B+樹B+樹是B樹的變形要求所有的信息都在葉子節(jié)點上 B+樹的所有關(guān)鍵字都出現(xiàn)在葉結(jié)點上，上面各層結(jié)點中的關(guān)鍵碼均是下一層相應(yīng)結(jié)點中最大關(guān)鍵碼的復(fù)寫 B+樹的鍵在非葉結(jié)點中也有可能重復(fù)出現(xiàn)，以維持B+樹的平衡。 R樹R 樹（Reference Tree）R樹是處理空間數(shù)據(jù)的B +樹的改進(jìn)，它像B +樹一樣，是一個高度平衡的數(shù)據(jù)結(jié)構(gòu)。R 樹算法是由美國加州大學(xué)的Antomm Guttman 教授在1984 年提出的一種空間數(shù)

15、據(jù)庫動態(tài)索引算法，現(xiàn)已成為空間數(shù)據(jù)庫索引中應(yīng)用最廣泛的算法之一。R 樹較好地解決了許多傳統(tǒng)算法未解決的空間數(shù)據(jù)動態(tài)索引問題。R樹R樹：稱為參考樹，是以空間要素的封裝邊界作為參考，從樹根（也就是所有空間對象的幾何）開始，對空間要素進(jìn)行分組，每一組作為根節(jié)點的孩子節(jié)點，依此類推，直到不可再分（即分到單個要素作為孩子節(jié)點，也就是葉節(jié)點）。全部分組過程中，每一分組的數(shù)量視空間對象的分布情況（即各封裝邊界的組合程度）確定。 R樹的每個結(jié)點不存放空間要素的值： 葉結(jié)點由多個(Rect ,OID) 數(shù)據(jù)項組成存儲該結(jié)點對應(yīng)的空間要素的外接矩形和空間要素標(biāo)識。其中OID為指向空間對象的具體數(shù)據(jù)指針Rect 為

16、對象OID的MBR非葉結(jié)點由多個(Rect ,child) 結(jié)構(gòu)的數(shù)據(jù)項組成存放其子女結(jié)點集合的整體外接矩形和指向其子女結(jié)點的指針。child 為子結(jié)點指針Rect 為與子結(jié)點child 相關(guān)的MBR。讓空間上靠近的空間對象擁有盡可能近的共同祖先, 能提高R 樹的查詢效率。因此在組織R 樹的時候, 盡可能的讓空間對象的空間位置的遠(yuǎn)近體現(xiàn)在其最近共同祖先的遠(yuǎn)近。形象的說就是讓聚集在一起空間對象盡可能早的組合在一起。R樹結(jié)構(gòu)示意圖原理第一階段（RDBMS完成）：接收查詢語句，獲取空間過濾器的封裝邊界從樹根R開始，將空間過濾器的封裝邊界與要素的封裝邊界相比較，首先選出R繼續(xù)遍歷，找出具有重疊關(guān)系的R

17、1依此類推，直至遍歷到樹的葉節(jié)點第二階段：幾何過濾器的坐標(biāo)與第一階段檢索出的要素的邊界比較，找出邊界在幾何過濾器內(nèi)的要素第三階段幾何過濾器的坐標(biāo)與第二階段檢索出的要素的比較，找出最終在幾何過濾器內(nèi)的要素類插入：向R 樹中插入一個數(shù)據(jù),實際上是插入該數(shù)據(jù)的MBR。當(dāng)所插入的葉結(jié)點中已經(jīng)沒有足夠的空間存放下要插入的數(shù)據(jù)時,要發(fā)生分裂,如果在其父結(jié)點同樣出現(xiàn)了溢出,也要產(chǎn)生分裂,如此下去直至根結(jié)點,如果根結(jié)點也發(fā)生了分裂,則生成一個新根結(jié)點,樹的高度增加1。刪除：在R 樹中刪除一個數(shù)據(jù),若發(fā)生結(jié)點下溢(即結(jié)點中元素個數(shù)小于規(guī)定的下限) ,則需要將相關(guān)結(jié)點從樹中刪除,然后重新插入,如果在刪除完成之后根

18、結(jié)點只有一個子結(jié)點的話,則這個子結(jié)點就成為新的根結(jié)點,樹的高度減1。R 樹允許結(jié)點相互覆蓋,這種覆蓋可以使R 樹保持較高的空間(內(nèi)存/ 磁盤) 利用率和保持樹的平衡。但另一個方面,過多覆蓋可能會造成查詢效率的降低,最壞的情況下對某一對象的查詢可能造成對整個樹的搜索,當(dāng)然在實際數(shù)據(jù)集中這種情況很少出現(xiàn)由于R樹具有動態(tài)平衡的特性，因此處理空間對象時具有很大的靈活性和較高的效率，但也正是為了保持其動態(tài)平衡性， 樹的插入刪除過程較為復(fù)雜，在插入、刪除頻繁時可能產(chǎn)生振蕩的現(xiàn)象，反而降低了效率。此外，樹有一個重要的特點就是兄弟節(jié)點對應(yīng)的空間區(qū)域可以互相重疊，使空間搜索的效率降低。因為區(qū)域之間有重疊，可能要

19、對多條路徑進(jìn)行搜索后才能得到最后的結(jié)果。R+樹R+ 樹為克服在R 樹中當(dāng)兄弟結(jié)點出現(xiàn)交叉時搜索效率低的問題,Sellis 在1987 年提出了R+ 樹。在R+ 樹中,空間對象的MBR 可能被樹中非葉結(jié)點的矩形分割。R+ 樹有如下特點(1) 對于中間結(jié)點的每個項( I ,child2pointer) ,當(dāng)且僅當(dāng)R被I 覆蓋時,以child2pointer 指向的結(jié)點為根的子樹包括一個矩形R。唯一的例外是當(dāng)I 是一個葉結(jié)點的矩形。在這種情況下,R 與I 只交疊。(2) 對中間結(jié)點的任何兩個項( I1 , child2pointer1 ) 和( I2 ,child2pointer2) ,I1 與I2

20、 之間的交疊是零。(3) 根至少有兩個子結(jié)點,除非它是葉結(jié)點。(4) 所有的葉結(jié)點都在同一層。中間結(jié)點的所有矩形都是不相交的，因而中間結(jié)點項之間產(chǎn)生零交疊。如果一個對象的MBR 被兩個或多個R+ 樹高層結(jié)點中的矩形分割,那么與這些非葉結(jié)點中矩形相聯(lián)系的每個項都有指向這個對象的一個后繼葉結(jié)點。這樣,樹的高度增加(雖然只是輕微的) ,但搜索操作的性能會有很大提高。R+ 樹克服了R 樹中結(jié)點空間之間互相重疊的問題,從而保證了點查詢時只搜索一條路徑。但因此也帶來了葉結(jié)點的冗余,而且隨著數(shù)據(jù)庫內(nèi)容的增加,冗余有遞增的趨勢,難以控制。經(jīng)對照發(fā)現(xiàn),R+ 樹在對象較小時性能優(yōu)于R 樹而在對象較大時性能比R 樹

21、略差。R*樹R*樹德國不萊梅大學(xué)的Beckmann 兼顧局部優(yōu)化和整體優(yōu)化,于1990 年提出了R*樹是R 樹發(fā)展過程中的一個重要里程碑。R*樹局部優(yōu)化的地方是分裂結(jié)點和選取最優(yōu)子樹的衡量指標(biāo)的多元化,除采用面積指標(biāo)外,還引入了周長和重迭部分面積作為判定指標(biāo)R*樹對R 樹的插入算法和分裂算法進(jìn)行了改進(jìn),主要體現(xiàn)在以下兩點第一,提出了強(qiáng)制重新插入的概念;第二,當(dāng)結(jié)點進(jìn)行分裂的時候,不僅要考慮分裂后兩個新結(jié)點的面積,還要考慮分裂后結(jié)點周長以及該層結(jié)點的重疊面積等因素。以上技術(shù)從一定程度上擴(kuò)大了重新組織數(shù)據(jù)時所應(yīng)考慮的數(shù)據(jù)空間的范圍,因此R 樹的性能得到了很大的改善,但R*樹的算法復(fù)雜度高于標(biāo)準(zhǔn)R

22、樹。R*樹在結(jié)構(gòu)上與R樹完全相同,在樹的構(gòu)造、插入、刪除、檢索算法上也基本相同。區(qū)別在于：提出了強(qiáng)制插入的概念，即當(dāng)一個節(jié)點在插入過程中發(fā)生了溢出，并不急于進(jìn)行分裂，而是保留節(jié)點中最相鄰的一部分MBR ，其余的按照插入算法重新插入。盡管R*樹的構(gòu)造過程時間開銷有所增加，其檢索性能和空間利用率都得到了較大的提高。也就是說,R*樹以增加少量的構(gòu)造時間開銷換取了更高的查找性能。不過，R*樹中存在的多路徑查找依然是制約檢索性能的瓶頸。不同索引方法性能的比較空間數(shù)據(jù)索引是空間數(shù)據(jù)庫技術(shù)的重要組成部分,由于至今還未找到比較完美的數(shù)據(jù)結(jié)構(gòu)來索引空間數(shù)據(jù),空間數(shù)據(jù)索引研究仍是當(dāng)前研究的熱點總結(jié)空間索引技術(shù)大致

23、分為如下幾類,其中主流方法都是采用樹索引結(jié)構(gòu)對象范圍索引格網(wǎng)索引四叉樹索引B樹索引R樹索引到目前為止，我們討論的都是索引的優(yōu)點。事實上，索引也是有缺點的。濫用索引不僅會浪費空間，還反而減低查詢速度。缺點：首先，索引要占用磁盤空間。通常情況下，這個問題不是很突出。但是，如果你創(chuàng)建每一種可能列組合的索引，索引文件體積的增長速度將遠(yuǎn)遠(yuǎn)超過數(shù)據(jù)文件。如果你有一個很大的表，索引文件的大小可能達(dá)到操作系統(tǒng)允許的最大文件限制。第二，對于需要寫入數(shù)據(jù)的操作，比如DELETE、UPDATE以及INSERT操作，索引會降低它們的速度。這是因為不僅要把改動數(shù)據(jù)寫入數(shù)據(jù)文件，而且它還要把這些改動寫入索引文件。 第二節(jié)

24、 空間查詢優(yōu)化查詢效率的提高主要來自兩個方面：外部環(huán)境應(yīng)用程序。外部環(huán)境的升級對查詢優(yōu)化的效果是非常明顯的，據(jù)統(tǒng)計，對大型關(guān)系數(shù)據(jù)來說，從網(wǎng)絡(luò)、硬件配置、操作系統(tǒng)、數(shù)據(jù)庫參數(shù)進(jìn)行優(yōu)化所獲得的性能提升，全部加起來占性能提升的40 %左右，其余的60 %性能優(yōu)化則來自對應(yīng)用程序的優(yōu)化 空間查詢優(yōu)化策略優(yōu)化查詢算法 選擇查詢路徑 緩存查詢結(jié)果 一、優(yōu)化查詢算法 通過盡可能少的復(fù)雜幾何計算就能得到正確的查詢結(jié)果、提高查詢執(zhí)行的效率是優(yōu)化查詢處理算法的主要目標(biāo)。 初次過濾二次篩選空間數(shù)據(jù)庫不準(zhǔn)確的候選集合最終查詢結(jié)果經(jīng)過初次后產(chǎn)生的候選集合越小，精確查詢時參與比較的空間對象就越少，越能夠提高查詢效率。因此，初次不精確查詢技術(shù)是優(yōu)化的重點。不精確查詢中經(jīng)常使用空間對象的相近外部邊界來實現(xiàn)。二、選擇查詢路徑1、分離查詢條件 將WHE