第5章 空間索引與優(yōu)化

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

2、文系 006fff女20計算機 查詢005號學(xué)生的信息： SELECT * FROM student WHERE 學(xué)號=005 學(xué)號姓名性別年齡系別 001aaa男19計算機 002bbb男20城環(huán)系 003ccc女19城環(huán)系 004ddd男18中文系 005eee女18中文系 006fff女20計算機 學(xué)號 姓名 性別 年齡系別 001aaa男19計算機 002bbb男20城環(huán)系 003ccc女19城環(huán)系 004ddd男18中文系 005eee女18中文系 006fff女20計算機 學(xué)號 位置 001 002 003 004 005 006 例如：查找經(jīng)過河南省的所有河流。 常規(guī)方法：檢查所

3、有河流和河南省省 界是否相交。 缺點：用實際空間對象比較，算法復(fù)雜， 計算開銷大、IO開銷大。 索引方法：記錄河流和省界的外接矩 形。用外接矩形進行比較。 空間屬性表描述要素的一般信息， 空間索引表描述要素所在格網(wǎng)的信息， 要素描述表描述要素的點數(shù)，范圍等信息， 三張表通過FID（Feature ID）關(guān)聯(lián) 定義 空間索引： 空間索引就是指依據(jù)空間對象的位置和形狀或 空間對象之間的某種空間關(guān)系，按一定的順序 排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對象的概 要信息，如對象的標識、外接矩形及指向空間 對象實體的指針。 空間索引的基本思想，也是空間查詢的基 本思想，即近似體的使用。 讓索引結(jié)構(gòu)按照一個或多

4、個空間碼來管理 對象，這些空間碼是比對象本事更簡單的 幾何對象。 常見的空間索引： 對象范圍索引 格網(wǎng)索引 四叉樹索引 R樹和R+樹索引 BSP樹索引 一、對象范圍索引一、對象范圍索引 在記錄每個空間實體的坐標時，記錄包圍每 個空間實體的外接矩形的最大最小坐標。 在檢索空間實體時，根據(jù)空間實體的最大最 小范圍，預(yù)先排除那些沒有落入檢索窗口內(nèi) 的空間實體，僅對那些外接矩形落在檢索窗 口的空間實體作進一步的判斷，真正落入窗 口內(nèi)的空間實體。 A B C E F D 基于實體范圍的空間數(shù)據(jù)檢索基于實體范圍的空間數(shù)據(jù)檢索 這種方法沒有創(chuàng)建真正的空間索引文件，而是在 空間對象的數(shù)據(jù)文件中增加了矩形范圍，

5、主要依 靠空間計算進行判別。 查詢時仍需要對整個數(shù)據(jù)文件的空間對象進行檢 索，只是某些對象可以通過矩形范圍予以直接判 別，而有些對象仍需要進行復(fù)雜計算才能判別。 雖然該方法仍需要花費大量時間來進行空間檢索， 但隨著計算機的處理速度的加快，這種方法在一 定程度上能夠滿足查詢檢索的效率要求 對象范圍索引對象范圍索引 IDXmaxXminYmaxYmin 1 2 3 空間對象不被檢索 Xmax XW OR Xmin XE OR Ymax YS OR Ymin YN 空間對象被檢索 Xmax XW and XminXE AND Ymax YS and YminYN 空間對象集合 1 2 3 4 5 6

6、 檢索窗口檢索窗口 YN XW XE YS 4 xmaxxmin ymin ymax x y 在進行空間范圍查詢時，分為兩級過濾（篩選）： 初次過濾根據(jù)空間要素外包絡(luò)矩形來過濾掉大 部分不在查詢范圍的空間要素； 第二級過濾則用查詢空間范圍直接和初次過濾 結(jié)果集中空間要素的二進制邊界坐標比較，從 而得到查詢的準確結(jié)果。 對象范圍索引對象范圍索引 5 1 2 3 4 1 2 3 1 2 二、格網(wǎng)索引二、格網(wǎng)索引 將研究區(qū)域用橫豎線條劃分大小相等和不 等的格網(wǎng)，記錄每一個格網(wǎng)所包含的空間 實體 用戶進行空間查詢時，首先計算出用戶查 詢對象所在格網(wǎng)，然后再在該網(wǎng)格中快速 查詢所選空間實體 通常是把整個

7、數(shù)據(jù)庫數(shù)值空間劃分成3232 （或6464）的正方形網(wǎng)格，建立另一個倒 排文件柵格索引。 每一個網(wǎng)格在柵格索引中有一個索引條目(記 錄)，在這個記錄中登記所有位于或穿過該網(wǎng)格 的物體的關(guān)鍵字。 A B C D E F 2123293153556163 2022283052546062 1719252749515759 1618242648505658 57131537394547 46121436384446 1391133354143 0281032344042 Peano鍵鍵空間對象空間對象 7B 12E 13E 14E 15E 24E 25A,E 26E 27E 32D 33D 35D,

8、F 37E 38D 39E 45E 50E 51E 54C 55C 空間對象空間對象Peano鍵集鍵集 A25-25 B7-7 C54-55 C60-60 D32-33 D35-35 D38-38 E12-15 E24-27 E37-37 E39-39 E48-51 E45-45 空空 間間 索索 引引 對對 象象 索索 引引 u檢索原理： 第一階段（RDBMS完成）： 接收SQL語句，獲取空間過濾器的封裝邊界 檢測空間過濾器的封裝邊界跨越的網(wǎng)格 到空間索引表中檢索出封裝邊界所在網(wǎng)格內(nèi)的要素 第二階段： 幾何過濾器的封裝邊界與第一階段檢索出的要素的邊界相比較， 找出具有重疊關(guān)系的要素 第三階段

9、 幾何過濾器的坐標與第二階段檢索出的要素的邊界比較，找出邊 界在幾何過濾器內(nèi)的要素 第四階段： 幾何過濾器的坐標與第三階段檢索出的要素的比較，找出最終在 幾何過濾器內(nèi)的要素類 A B C D E F G H 671315 451214 13911 02810 A B C D E F G H 671315 451214 13911 02810 第一階段: (1)接收SQL 語句，獲取 空間過濾器 的封裝邊界 (2)檢測空間 過濾器的封 裝邊界跨越 的網(wǎng)格 (3)到空間索 引表中檢索 出封裝邊界 所在網(wǎng)格內(nèi) 的要素 C E F G H 671315 451214 13911 02810 第二階段:

10、 幾何過濾器的封 裝邊界與第一階 段檢索出的要素 的邊界相比較， 找出具有重疊關(guān) 系的要素 E F G H 671315 451214 13911 02810 第三階段: 幾何過濾器的坐 標與第二階段檢 索出的要素的邊 界比較，找出邊 界在幾何過濾器 內(nèi)的要素 E F G H 671315 451214 13911 02810 第四階段: 幾何過濾器的坐 標與第三階段檢 索出的要素的坐 標比較，找出最 終在幾何過濾器 內(nèi)的要素類 按格網(wǎng)法對空間數(shù)據(jù)進行索引時，所劃分 的格網(wǎng)數(shù)不能太多，否則，索引表本身太 大而不利于數(shù)據(jù)的索引和檢索 三、四叉樹索引三、四叉樹索引 二維空間范圍被劃分為一系列大小相

11、等的 棋盤狀矩形，即將地理空間的長和寬在X和 Y方向上進行2N等分，形成2N2N的網(wǎng)格， 并以此建立N級四叉樹。 四叉樹是具有一個根節(jié)點,其中的每個中間 節(jié)點都有四個孩子。四叉樹的每個節(jié)點對 應(yīng)一個正方形。 四叉樹及其子分割 在建立四叉樹索引時，根據(jù)所有空間對象 覆蓋的范圍，進行四叉樹分割，使每個子 塊中包含單個實體，然后根據(jù)包含每個實 體的子塊層數(shù)或子塊大小，建立相應(yīng)的索 引。 在四叉樹索引中，大區(qū)域空間實體更靠近 樹的根部，小實體位于葉端，以不同的分 辨率來描述不同實體的可檢索性 用線性四叉樹組織的空間索引 57 E 1315 G B 461214 13 02 8 A F D C Pean

12、o邊長空間對象 04E 02D 01A 41F 82C 151G,B 第一階段（RDBMS完成）： 接收SQL語句，獲取空間過濾器的封裝邊界 將空間索引四等分，每一份與空間過濾器的封裝邊界的邊界比較， 取出與空間過濾器的封裝邊界沒有重疊的網(wǎng)格（這些網(wǎng)格不再分） 將得到的部分繼續(xù)四等分，與空間過濾器的封裝邊界的邊界比較。 第二階段： 幾何過濾器的封裝邊界與第一階段檢索出的要素的邊界相比較， 找出具有重疊關(guān)系的要素 第三階段 幾何過濾器的坐標與第二階段檢索出的要素的邊界比較，找出邊 界在幾何過濾器內(nèi)的要素 第四階段： 幾何過濾器的坐標與第三階段檢索出的要素的比較，找出最終在 幾何過濾器內(nèi)的要素類

13、u檢索原理： A B C D E 四、BSP樹索引 BSP樹（Binary Space Partition Tree）： 空間二叉樹算法 對于要處理的一組空間對象，選擇一個平面， 將該對象分成兩組（如果某個對象與該平面相 交，則用這個平面將這個對象分成兩個對象）， 作為該節(jié)點的兩個孩子，然后分別對兩個對象 用相同的方法，直到滿足一個特定的條件（通 常是到節(jié)點上只有一個對象）為止。一般來說， 選擇的平面盡量不要把同一對象分成兩個。 原理： 第一階段 （1）接收查詢語句，從中獲取空間過濾器的封裝邊 界； （2）以空間過濾器封裝邊界的第一條邊為界，將空 間索引表分成兩部分，取空間過濾器一側(cè)的要素進

14、行索引； （3）按某一方向，選擇第二條、第三條和第四條邊 為邊界，分別除去在封裝邊界外測的要素 第二階段 將空間過濾器的幾何坐標和第一階段選擇出的要素 的封裝邊界進行比較，得到索引結(jié)果 第三階段 將空間過濾器的幾何坐標和第二階段選擇出的要素 的幾何坐標進行比較，得到最終的索引結(jié)果。 B樹 對于一維升序或降序數(shù)據(jù)序列（假設(shè)其個 數(shù)為N）來說，可以采用兩分檢索的方法來 迅速地找到需要插入或刪除元素的位置。 順序表： 插入一個元素，需要將其以下的數(shù)據(jù)均進行后 移 刪除一個元素，需要將以下的數(shù)據(jù)進行前移。 提高插入和刪除的工作效率，研究者提出 了多種解決方法，B樹就是其中較好的一種 方案。 B樹是由一

15、系列節(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.66 0.66 例如：插入數(shù)據(jù)0.10 由此可以看出： B樹中同一鍵值不會出現(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)鍵碼均是

16、下一層相應(yīng)結(jié)點中最大 關(guān)鍵碼的復(fù)寫 B+樹的鍵在非葉結(jié)點中也有可能重復(fù)出現(xiàn)，以 維持B+樹的平衡。 R樹 R 樹（Reference Tree） R樹是處理空間數(shù)據(jù)的B +樹的改進，它像B + 樹一樣，是一個高度平衡的數(shù)據(jù)結(jié)構(gòu)。 R 樹算法是由美國加州大學(xué)的Antomm Guttman 教授在1984 年提出的一種空間數(shù)據(jù) 庫動態(tài)索引算法，現(xiàn)已成為空間數(shù)據(jù)庫索引中 應(yīng)用最廣泛的算法之一。 R 樹較好地解決了許多傳統(tǒng)算法未解決的空間 數(shù)據(jù)動態(tài)索引問題。 R樹 R樹： 稱為參考樹，是以空間要素的封裝邊界作為參考， 從樹根（也就是所有空間對象的幾何）開始，對 空間要素進行分組，每一組作為根節(jié)點的孩子

17、節(jié) 點，依此類推，直到不可再分（即分到單個要素 作為孩子節(jié)點，也就是葉節(jié)點）。 全部分組過程中，每一分組的數(shù)量視空間對象的 分布情況（即各封裝邊界的組合程度）確定。 R樹的每個結(jié)點不存放空間要素的值： 葉結(jié)點 由多個(Rect ,OID) 數(shù)據(jù)項組成 存儲該結(jié)點對應(yīng)的空間要素的外接矩形和空間要素標 識。 其中OID為指向空間對象的具體數(shù)據(jù)指針 Rect 為對象OID的MBR 非葉結(jié)點 由多個(Rect ,child) 結(jié)構(gòu)的數(shù)據(jù)項組成 存放其子女結(jié)點集合的整體外接矩形和指向其子女結(jié) 點的指針。 child 為子結(jié)點指針 Rect 為與子結(jié)點child 相關(guān)的MBR。 讓空間上靠近的空間對象擁有

18、盡可能近的 共同祖先, 能提高R 樹的查詢效率。 因此在組織R 樹的時候, 盡可能的讓空間對 象的空間位置的遠近體現(xiàn)在其最近共同祖 先的遠近。 形象的說就是讓聚集在一起空間對象盡可 能早的組合在一起。 R樹結(jié)構(gòu)示意圖 原理 第一階段（RDBMS完成）： 接收查詢語句，獲取空間過濾器的封裝邊界 從樹根R開始，將空間過濾器的封裝邊界與要素的封裝 邊界相比較，首先選出R 繼續(xù)遍歷，找出具有重疊關(guān)系的R1 依此類推，直至遍歷到樹的葉節(jié)點 第二階段： 幾何過濾器的坐標與第一階段檢索出的要素的邊界比 較，找出邊界在幾何過濾器內(nèi)的要素 第三階段 幾何過濾器的坐標與第二階段檢索出的要素的比較， 找出最終在幾何

19、過濾器內(nèi)的要素類 插入： 向R 樹中插入一個數(shù)據(jù),實際上是插入該數(shù)據(jù)的 MBR。當所插入的葉結(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é)點從樹中刪除,然后重新插入,如果在刪除完 成之后根結(jié)點只有一個子結(jié)點的話,則這個子結(jié) 點就成為新的根結(jié)點,樹的高度減1。 R 樹允許結(jié)點相互覆蓋,這種覆蓋可以使R 樹保持較高的空間(內(nèi)存/ 磁盤) 利用率和保 持樹

20、的平衡。 但另一個方面,過多覆蓋可能會造成查詢效 率的降低,最壞的情況下對某一對象的查詢 可能造成對整個樹的搜索,當然在實際數(shù)據(jù) 集中這種情況很少出現(xiàn) 由于R樹具有動態(tài)平衡的特性，因此處理空間對 象時具有很大的靈活性和較高的效率，但也正是 為了保持其動態(tài)平衡性， 樹的插入刪除過程較為 復(fù)雜，在插入、刪除頻繁時可能產(chǎn)生振蕩的現(xiàn)象， 反而降低了效率。 此外，樹有一個重要的特點就是兄弟節(jié)點對應(yīng)的 空間區(qū)域可以互相重疊，使空間搜索的效率降低。 因為區(qū)域之間有重疊，可能要對多條路徑進行搜 索后才能得到最后的結(jié)果。 R+樹 R+ 樹樹 為克服在R 樹中當兄弟結(jié)點出現(xiàn)交叉時搜 索效率低的問題,Sellis

21、在1987 年提出了R+ 樹。在R+ 樹中,空間對象的MBR 可能被樹 中非葉結(jié)點的矩形分割。 R+ 樹有如下特點 (1) 對于中間結(jié)點的每個項( I ,child2pointer) ,當且僅當 R被I 覆蓋時,以child2pointer 指向的結(jié)點為根的子樹包 括一個矩形R。唯一的例外是當I 是一個葉結(jié)點的矩形。 在這種情況下,R 與I 只交疊。 (2) 對中間結(jié)點的任何兩個項( I1 , child2pointer1 ) 和 ( I2 ,child2pointer2) ,I1 與I2 之間的交疊是零。 (3) 根至少有兩個子結(jié)點,除非它是葉結(jié)點。 (4) 所有的葉結(jié)點都在同一層。 中間結(jié)

22、點的所有矩形都是不相交的，因而 中間結(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 樹略 差。 R*樹樹 R*樹樹 德國不萊梅大學(xué)的Beckmann 兼顧局部優(yōu)化

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

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

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

26、數(shù)據(jù)寫入數(shù)據(jù)文件，而且它還 要把這些改動寫入索引文件。 第二節(jié) 空間查詢優(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ù)進行優(yōu)化所獲得的性 能提升，全部加起來占性能提升的40 %左右，其 余的60 %性能優(yōu)化則來自對應(yīng)用程序的優(yōu)化 空間查詢優(yōu)化策略 優(yōu)化查詢算法 選擇查詢路徑 緩存查詢結(jié)果 一、優(yōu)化查詢算法 通過盡可能少的復(fù)雜幾何計算就能得到正 確的查詢結(jié)果、提高查詢執(zhí)行的效率是優(yōu) 化查詢處理算法的主要目標。 初 次 過 濾 二 次 篩 選 空間 數(shù)據(jù)庫 不 準 確 的 候 選 集合 最 終 查 詢結(jié)果 經(jīng)過初次后產(chǎn)生的候選集合越小，精確查 詢時參與比較的空間對象就越少，越能夠 提高查詢效率。因此，初次不精確查詢技 術(shù)是優(yōu)化的重點。不精確查詢中經(jīng)常使用 空間對象的相近外部邊界來實現(xiàn)