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

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

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

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

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

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

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

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

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

10、此建立N級(jí)四叉樹。四叉樹是具有一個(gè)根節(jié)點(diǎn),其中的每個(gè)中間節(jié)點(diǎn)都有四個(gè)孩子。四叉樹的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)正方形。四叉樹及其子分割在建立四叉樹索引時(shí)，根據(jù)所有空間對(duì)象覆蓋的范圍，進(jìn)行四叉樹分割，使每個(gè)子塊中包含單個(gè)實(shí)體，然后根據(jù)包含每個(gè)實(shí)體的子塊層數(shù)或子塊大小，建立相應(yīng)的索引。在四叉樹索引中，大區(qū)域空間實(shí)體更靠近樹的根部，小實(shí)體位于葉端，以不同的分辨率來描述不同實(shí)體的可檢索性 用線性四叉樹組織的空間索引57E1315GB46121413028AFDCPeano邊長(zhǎng)空間對(duì)象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）：空間二叉樹算法對(duì)于要處理的一組空間對(duì)象，選擇一個(gè)平面，將該對(duì)象分成兩組（如果某個(gè)對(duì)象

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

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

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

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

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

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

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

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

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

21、略差。R*樹R*樹德國(guó)不萊梅大學(xué)的Beckmann 兼顧局部?jī)?yōu)化和整體優(yōu)化,于1990 年提出了R*樹是R 樹發(fā)展過程中的一個(gè)重要里程碑。R*樹局部?jī)?yōu)化的地方是分裂結(jié)點(diǎn)和選取最優(yōu)子樹的衡量指標(biāo)的多元化,除采用面積指標(biāo)外,還引入了周長(zhǎng)和重迭部分面積作為判定指標(biāo)R*樹對(duì)R 樹的插入算法和分裂算法進(jìn)行了改進(jìn),主要體現(xiàn)在以下兩點(diǎn)第一,提出了強(qiáng)制重新插入的概念;第二,當(dāng)結(jié)點(diǎn)進(jìn)行分裂的時(shí)候,不僅要考慮分裂后兩個(gè)新結(jié)點(diǎn)的面積,還要考慮分裂后結(jié)點(diǎn)周長(zhǎng)以及該層結(jié)點(diǎn)的重疊面積等因素。以上技術(shù)從一定程度上擴(kuò)大了重新組織數(shù)據(jù)時(shí)所應(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)一個(gè)節(jié)點(diǎn)在插入過程中發(fā)生了溢出，并不急于進(jìn)行分裂，而是保留節(jié)點(diǎn)中最相鄰的一部分MBR ，其余的按照插入算法重新插入。盡管R*樹的構(gòu)造過程時(shí)間開銷有所增加，其檢索性能和空間利用率都得到了較大的提高。也就是說,R*樹以增加少量的構(gòu)造時(shí)間開銷換取了更高的查找性能。不過，R*樹中存在的多路徑查找依然是制約檢索性能的瓶頸。不同索引方法性能的比較空間數(shù)據(jù)索引是空間數(shù)據(jù)庫(kù)技術(shù)的重要組成部分,由于至今還未找到比較完美的數(shù)據(jù)結(jié)構(gòu)來索引空間數(shù)據(jù),空間數(shù)據(jù)索引研究仍是當(dāng)前研究的熱點(diǎn)總結(jié)空間索引技術(shù)大致

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

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