海量瓦片數(shù)據(jù)管理和優(yōu)化方案

1、.海量瓦片數(shù)據(jù)管理及優(yōu)化方案海量瓦片數(shù)據(jù)的管理瓦片數(shù)據(jù)的特點瓦片數(shù)據(jù)是應用地圖瓦片技術(shù)對地圖數(shù)據(jù)進行切片所得到的,其對數(shù)據(jù)的切分規(guī)則通常是按照固定的若干個比例尺瓦片級別和指定圖片尺寸,切成若干行、列的正方形圖片,并以指定的格式保存為圖片文件,再按一定的命名規(guī)則與組織方式存儲到目錄系統(tǒng)中或關(guān)系數(shù)據(jù)庫里。地圖切圖所獲得的地圖切圖也叫瓦片,瓦片金字塔是瓦片數(shù)據(jù)的一種多分辨率層次模型,從金字塔底層到頂層,數(shù)據(jù)分辨率越來越低,但是其表示的地理范圍不變。瓦片數(shù)據(jù)是改進系統(tǒng)性能的最佳選擇,它通過對地圖數(shù)據(jù)預先渲染、切片,有效減輕服務(wù)器處理壓力,減少網(wǎng)絡(luò)負載和響應延遲。但是,瓦片地圖服務(wù)都基于文件方式進行圖片

2、緩存,這種方式實現(xiàn)簡單,但因瓦片數(shù)據(jù)動輒幾百至上千萬個文件,且文件很小,導致磁盤存儲碎片化嚴重,影響性能,且數(shù)據(jù)可遷移性差,無論是數(shù)據(jù)備份、遷移或是恢復都耗時漫長。如何優(yōu)化瓦片技術(shù),減小數(shù)據(jù)冗余,提高訪問效率和管理效率是當前我們急需解決的問題。海量瓦片數(shù)據(jù)的管理目前很多GIS平臺對數(shù)據(jù)的管理方式雖然類似但也不盡相同?？偨Y(jié)起來大概有三種方式。一是基于文件系統(tǒng)凡人管理,對切分后的數(shù)據(jù)按照瓦片數(shù)據(jù)的切分規(guī)則分別用文件夾存儲管理,即地圖瓦片數(shù)據(jù)的組織方式采用數(shù)據(jù)集、層、行目錄結(jié)構(gòu)描述,并基于文件系統(tǒng)的方式進行調(diào)度；此方法調(diào)度簡單,檢索過程依賴文件系統(tǒng)的文件查詢方式和訪問方式,容易實現(xiàn),但效率不高,維護

3、=復雜,同時存在數(shù)據(jù)的安全隱患。圖 SEQ 圖 * ARABIC 1 瓦片文件組織二是采用大型的關(guān)系數(shù)據(jù)引擎：此種方式通常將預處理后凡人瓦片數(shù)據(jù)以一條獨立記錄的形式存放于數(shù)據(jù)庫中,通?？梢愿鶕?jù)瓦片切分的層級或則金字塔結(jié)構(gòu)分表存儲以提高數(shù)據(jù)的檢索效率。這種方式可以利用數(shù)據(jù)庫的安全機制有效的解決基于文件系統(tǒng)管理存在的安全隱患,但是由于關(guān)系型的數(shù)據(jù)庫對于此類數(shù)據(jù)很難建立快速的索引機制,所以相對調(diào)度效率較低,但是實現(xiàn)相對容易。三是基于GIS自身為滿足空間數(shù)據(jù)檢索而開發(fā)的一些專用數(shù)據(jù)庫管理引擎,如GFS等等,這類引擎能夠較好的解決數(shù)據(jù)調(diào)度的效率同時也能有效的避免文件系統(tǒng)存在的各種安全隱患,但實現(xiàn)復雜。瓦

4、片數(shù)據(jù)的調(diào)度數(shù)據(jù)的格網(wǎng)分割由于影像等數(shù)據(jù)通常都是以一個大的數(shù)據(jù)文件格式的形式存在的,而如此龐大的文件不可能也不需要一次性的全部加載到GIS系統(tǒng)中來,更多的時候是我們僅僅需要加載我們所關(guān)心的部分數(shù)據(jù)。因此,此類數(shù)據(jù)在使用之前需要進行一些列的處理,即大的數(shù)據(jù)分割為小塊的數(shù)據(jù),這樣在調(diào)度時僅僅需要調(diào)度用戶需要的那部分數(shù)據(jù)即可。目前絕大多數(shù)GIS采用的分割方式是以固定大小的網(wǎng)格分割,在關(guān)系數(shù)據(jù)庫中,對于數(shù)值和字符的索引已經(jīng)比較成熟,且效率很高,但是對于諸如影像等變長的二進制數(shù)據(jù)來說很難建立的高效的索引機制。通常將對此類數(shù)據(jù)的索引通過網(wǎng)格分割,改成對格網(wǎng)編號的索引,從而大大提升索引的效率,從而提升數(shù)據(jù)調(diào)

5、度的效率。分割方法是按照一定的規(guī)則將大的數(shù)據(jù)分割為規(guī)則如正方形區(qū)域并且彼此之間沒有重疊的圖像塊,并且給每個塊一個唯一編號如網(wǎng)格行列號,從而通過對格網(wǎng)編號索引實現(xiàn)數(shù)據(jù)的檢索。索引算法如下：若X0,Y0為格網(wǎng)的起始坐標原點,設(shè)窗口顯示的范圍為X1,Y1,X2,Y2,如圖2所示。圖 SEQ 圖 * ARABIC 2 格網(wǎng)索引圖起始格網(wǎng)的行號為：取整X1-X0/x,其中x為格網(wǎng)的寬度值；終止網(wǎng)格的行號為：取整X2-X0/x+1；起始格網(wǎng)的列號為：取整Y1-Y0/y,其中y為格網(wǎng)的寬度值； 終止格網(wǎng)的列號為：取整Y2-Y0/y+1；由此通過格網(wǎng)的起止編號來檢索X1,Y1,X2,Y2對應包含的數(shù)據(jù)塊編號即

6、可。金字塔建立金字塔是指在同一的空間參照下,根據(jù)用戶需求以不同分辨率進行存儲和實現(xiàn),形成分辨率油由低到高,數(shù)據(jù)量由小到大的金字塔結(jié)構(gòu)。這樣在數(shù)據(jù)的最底層存儲最高分辨率的數(shù)據(jù),然后隨著金字塔層數(shù)的增加,數(shù)據(jù)的分辨率依次降低,數(shù)據(jù)量依次減少,在金字塔的頂層,則僅僅存儲用戶所需要的最小分辨率的數(shù)據(jù)。在進行顯示時,根據(jù)當前用戶的瀏覽范圍及顯示設(shè)備的分辨率和范圍,使用能夠滿足用戶視覺要求的金字塔層次中的最高層數(shù)據(jù)作為顯示數(shù)據(jù),這種方式在一定程度上會增加數(shù)據(jù)存儲開銷,但能加快實時顯示速度?；诮鹱炙耐咂指钆c數(shù)據(jù)調(diào)度數(shù)據(jù)金字塔建立之后要分別對其各層數(shù)據(jù)進行格網(wǎng)分割,分割時要根據(jù)瓦片所處的層級及所在區(qū)域的

7、不同對瓦片進行唯一編號,這便是瓦片數(shù)據(jù)的生成?；诮鹱炙耐咂蟹滞ǔ２捎盟牟鏄湫问?即以金字塔最頂層數(shù)據(jù)為基準,依次向下做22n瓦片數(shù)量等大小分割,n為金字塔層級,這也就是前面所闡述的金字塔層級之間分辨率通常保持4倍關(guān)系的原因,如圖所示。在GIS對瓦片數(shù)據(jù)的調(diào)度過程中,對頂層數(shù)據(jù)為基礎(chǔ),隨著距離的拉近,當需要調(diào)度金字塔下一層數(shù)據(jù)時,系統(tǒng)自動對當前視域范圍的瓦片按照四叉樹規(guī)則,調(diào)度其下一層該瓦片數(shù)據(jù)對應分割后的四個子瓦片,因此新加載的瓦片所代表的地理區(qū)域總和與其父節(jié)點瓦片相同,從而達到加載更加清晰數(shù)據(jù)以滿足顯示效果的目的。如圖3中,根據(jù)當前加載的瓦片數(shù)據(jù)的編號可以按照四叉樹分裂規(guī)則直接計算出其

8、上一層或下一層需要加載的瓦片數(shù)據(jù)編號,如當前視域范圍內(nèi)加載的瓦片的空間編號為5-5-15-25即第三個Face的第五級橫坐標為15,縱坐標為25的瓦片,隨著距離的拉近需要更加清晰的數(shù)據(jù)來填充當前的地理范圍,則對該瓦片進行四叉樹分割后的四個瓦片的編號分別為3-6-30-50、3-6-30-51、3-6-31-50、3-6-31-51,從而可以根據(jù)瓦片的編號直接請求響應的瓦片數(shù)據(jù)即可。圖 SEQ 圖 * ARABIC 3 瓦片數(shù)據(jù)分割圖海量瓦片數(shù)據(jù)優(yōu)化管理方案瓦片數(shù)據(jù)的緊縮處理由于瓦片的數(shù)據(jù)通常以離散文件的形式存在,因此對于瓦片數(shù)據(jù)進行必要的緊縮處理可以大大提高瓦片數(shù)據(jù)的可維護性,因此這或許也是越

9、來越多的GIS平臺均或多或少的對瓦片數(shù)據(jù)進行一定的緊縮處理的主要原因所在。而數(shù)據(jù)的緊縮方式對于緊縮后數(shù)據(jù)管理與維護的便捷性有著重要的影響,因此引擎的設(shè)計首先要考慮的就是緊縮數(shù)據(jù)的結(jié)構(gòu)設(shè)計問題。對于緊縮數(shù)據(jù)的總體結(jié)構(gòu),本文對緊縮數(shù)據(jù)采用數(shù)據(jù)文件與索引文件相分離的形式,機數(shù)據(jù)文件中僅僅包含緊縮后的瓦片數(shù)據(jù),而對于數(shù)據(jù)的檢索信息則單獨以檢索文件的形式存在,其總體結(jié)構(gòu)如圖4所示。圖 SEQ 圖 * ARABIC 4 引擎數(shù)據(jù)緊縮的整體結(jié)構(gòu)離散瓦片數(shù)據(jù)緊密的緊縮到數(shù)據(jù)文件中以形成文件體的數(shù)據(jù)文件,由于瓦片數(shù)據(jù)量龐大,而一個數(shù)據(jù)文件的大小也不可嫩無限增大,因此將文件限制在一定大小之內(nèi),從而可以保證數(shù)據(jù)轉(zhuǎn)移

10、和數(shù)據(jù)可維護性,而且可以避免因部分數(shù)據(jù)毀壞而造成數(shù)據(jù)服務(wù)的整體癱瘓。多個數(shù)據(jù)文件構(gòu)成一個數(shù)據(jù)文件集,文件集中每個數(shù)據(jù)文件都有一個唯一的ID編號以便于檢索時的快速定位。數(shù)據(jù)文件完全有瓦片數(shù)據(jù)按照一定的規(guī)則組合而成,其中不包含瓦片數(shù)據(jù)的相關(guān)檢索信息,對于堆積到數(shù)據(jù)文件中瓦片數(shù)據(jù)的檢索是通過瓦片數(shù)據(jù)緊縮過程中同步建立的檢索文件實現(xiàn)的。檢索文件在瓦片數(shù)據(jù)緊縮時記錄了每個瓦片數(shù)據(jù)的基本屬性信息及所屬數(shù)據(jù)文件的相關(guān)檢索信息,從而可以通過對檢索文件的解讀實現(xiàn)瓦片在數(shù)據(jù)文件中的檢索,檢索文件也可以根據(jù)需要建立多個從而實現(xiàn)檢索文件集的建立。由于數(shù)據(jù)文件僅僅用來保存瓦片數(shù)據(jù),而檢索文件是實現(xiàn)對數(shù)據(jù)文件解讀的唯一方

11、式,因此緊縮后數(shù)據(jù)的安全性相較于緊縮前也會有較大提升。另外由于檢索文件對于數(shù)據(jù)文件解析的重要性,因此保證檢索數(shù)據(jù)的完整性與有效性是緊縮后數(shù)據(jù)能否正常對外提供數(shù)據(jù)服務(wù)的一個重要部分,設(shè)計中我們在瓦片數(shù)據(jù)緊縮時對索引文件的建立采用多文件相互備份和同步驗證的方式保證索引文件的正確與有效。通過采用數(shù)據(jù)文件與索引文件相分離的方式可以較大程度的減小瓦片緊縮過程中的數(shù)據(jù)結(jié)構(gòu)的設(shè)計復雜度。對于數(shù)據(jù)文件來說其存儲過程不需要增加冗余的瓦片文件信息,從而可以通過相對簡單統(tǒng)一的結(jié)構(gòu)以實現(xiàn)瓦片數(shù)據(jù)的緊縮存儲,并且在數(shù)據(jù)檢索過程中,通過檢索信息檢索到的數(shù)據(jù)也是純粹的瓦片數(shù)據(jù)而不需要做額外的數(shù)據(jù)過濾工作。而檢索文件是在瓦片

12、數(shù)據(jù)緊縮過程中或數(shù)據(jù)維護更新中生成或更新的,它實現(xiàn)了對所有瓦片在數(shù)據(jù)文件中的檢索信息以及瓦片數(shù)據(jù)自身必要信息的管理與維護。檢索文件的結(jié)構(gòu)設(shè)計與維護在一定意義下可以獨立于數(shù)據(jù)文件,即當瓦片數(shù)據(jù)緊縮的前提下,通過修改或重建符合新功能需求的檢索文件實現(xiàn),從而可以較大程度的提高數(shù)據(jù)維護與數(shù)據(jù)服務(wù)的靈活性。數(shù)據(jù)調(diào)度的快速索引模型關(guān)于索引的建立,可以根據(jù)常見的快速查找算法實現(xiàn),簡單的可以理解為根據(jù)算法要求對檢索文件解析出來的數(shù)據(jù)按照一定的數(shù)據(jù)結(jié)構(gòu)進行組織,從而使重新組織后的數(shù)據(jù)可以滿足快速查找算法的要求。對于算法的選擇,可以通過對檢索算法的比較來確定,檢索算法的效率可以通過平均檢索長度ASL來衡量,所以平

13、均檢索長度,是指為確定檢索對象位置所執(zhí)行關(guān)鍵碼比較次數(shù)的期望值,比如對于含有n個對象的表,檢索成功的平均檢索長度為公式1；ASL=i Ci其中：Pi表示第i個對象的概率,且i=1。Ci是檢索到第i個對象所需要的關(guān)鍵碼比較次數(shù)。檢索方法的不同,Ci可以不同。依據(jù)這個方法,接下來將對本課題用到折半檢索和四叉樹檢索算法進行分析。折半檢索折半檢索又稱為二分法檢索,它是對有序數(shù)據(jù)的一種有效檢索方法,其前提是要求被檢索數(shù)據(jù)為有序數(shù)據(jù),也就是說此類數(shù)據(jù)必須可以按照一定的規(guī)則進行排序,排序后可以得到一個有序序列。在檢索時首先取該有序序列中間位置的記錄與待查數(shù)據(jù)進行比較,如果待查的數(shù)據(jù)較該記錄值大大的含義不僅僅

14、是數(shù)字比較上的大小,而是可以按照任何意義的規(guī)則進行比較,則待查的值必在該記錄所在表中的后半部分；在這后半部分中再取中間位置記錄進行比較,這樣又可舍去這部分中的一半。依次反復,直到找到待查數(shù)據(jù)為成功或查不到為檢索失敗。對于折半檢索的檢索效率,從上述檢索過程看,以有序序列的中點為比較對象,并以中點將序列分割為兩個字序列,對定位到的子序列繼續(xù)進行這種操作。所以,對序列中每個數(shù)據(jù)元素的查找過程,可以用二叉樹來描述,稱這個描述查找過程的二叉樹為定樹。如以有序表1、3、7、10、11、19、23、30、33、35、38、46、55為例,其按折半查找構(gòu)造的判定樹如圖5所示。圖 SEQ 圖 * ARABIC

15、5 折半查詢算法判定樹示意圖可以看到,查詢序列中任一元素的過程,即是判定樹中從根到元素結(jié)點路徑上個結(jié)點關(guān)鍵碼的比較次數(shù),即該元素結(jié)點在樹中的層次數(shù)。對于n個結(jié)點的判定樹,樹高為k,根據(jù)二叉樹的性質(zhì)有n2k-1,即log2n+1=k,所以k=log2n+1。因此折半查找在查找成功時,所進行的關(guān)鍵碼比較次數(shù)最多為log2n+1次。接下來討論折半查找的平均查找長度。為便于討論,以樹高為k的滿二叉樹n=2k-1為例。假設(shè)表中每個元素的查找是等概率的,即pi=1/n則樹的第i層有2i-1個結(jié)點,因此,折半查找的平均查找長度為：ASL=i Ci=1/n120+221+.+k2k-1=log2-1log2-

16、1所以,折半檢索的時間效率為Olog2 n。雖然折半檢索的平均查找效率高,但折半檢索只是用于順序存儲結(jié)構(gòu),因此其主要適合哪種一經(jīng)建立就很少改動、而又經(jīng)常需要查找的線性表。而對于本文探討的瓦片數(shù)據(jù)緊縮也屬于多讀少寫的數(shù)據(jù)類型,因此可以再數(shù)據(jù)緊縮后為檢索文件建立靜態(tài)索引信息或索引文件,并伴隨著數(shù)據(jù)文件的維護更新而同步更新即可。四叉樹檢索四叉樹在空間離散數(shù)據(jù)點的存儲表達和索引中有著廣泛的應用,如點四叉樹、區(qū)域四叉樹和CIF四叉樹等,對于瓦片數(shù)據(jù)的四叉樹索引我們采用線性四叉樹編碼的形式,即通過建立金字塔結(jié)構(gòu)中的一個基本數(shù)據(jù)單元,即類似于樹結(jié)構(gòu)的葉子節(jié)點,而由于瓦片數(shù)據(jù)在金字塔結(jié)構(gòu)中編號FileID的唯

17、一性,因此可以建立一個由瓦片數(shù)據(jù)編號映射而成的線性四叉樹結(jié)構(gòu),進而通過對線性四叉樹FileID的檢索以實現(xiàn)對瓦片數(shù)據(jù)的檢索。這個過程首先要建立瓦片數(shù)據(jù)編號到線性四叉樹的映射關(guān)系,通常金字塔每一級都會遵從四叉樹方式切分,由此金字塔的層級可以與線性四叉樹的層級進行一一映射,即對于一個n層的金字塔建立一個D=n的線性四叉樹,然后對于金字塔頂層瓦片將其編號直接與線性四叉樹的根節(jié)點對應,再次對于頂層之外的每層瓦片數(shù)據(jù)編號與對應層級的線性四叉樹節(jié)點進行一一映射。如圖6所示。其中a為瓦片在金字塔結(jié)構(gòu)的編碼結(jié)構(gòu),編碼第一部分為多金字塔結(jié)構(gòu)中的區(qū)域編碼,即采用多金字塔結(jié)構(gòu)的Face序號,第二部分為瓦片數(shù)據(jù)的層級

18、編號,即對應線性四叉樹結(jié)構(gòu)的深度層級,第三部分為瓦片數(shù)據(jù)的行號,最后一部分為列號,節(jié)點在線性四叉樹結(jié)構(gòu)中映射如b中所示。經(jīng)過這種映射之后線性四叉樹中每一層的節(jié)點分別對應金字塔相應層中瓦片數(shù)據(jù)節(jié)點編號,同時將檢索文件中對應的瓦片的檢索信息存入該四叉樹節(jié)點中,對于不存在的瓦片對應的四叉樹節(jié)點,僅保留該瓦片編號而相應的數(shù)據(jù)檢索信息留空,由此可以將金字塔中對瓦片數(shù)據(jù)的檢索轉(zhuǎn)化為對線性四叉樹節(jié)點的檢索。如此建立的線性四叉樹的檢索效率ASL,由于可采用的檢索方式不同其檢索效率也存在一定差異。四叉樹節(jié)點的順序檢索過程就是對樹中節(jié)點的檢索,通過建立一個從根節(jié)點到被檢索節(jié)點的一個遍歷路徑來實現(xiàn)節(jié)點的檢索。如四叉樹的深度為n,檢索L層第i個瓦片所需要時間為從根節(jié)點到該節(jié)點最短路徑的遍歷時間,以上述映射線性四叉樹為例,假設(shè)要檢索節(jié)點3-3-5-7的索引則首先根據(jù)四叉樹節(jié)點編碼特征建立一個從根節(jié)點到該節(jié)點的遍歷通道,這個過程可以跟進要檢索的節(jié)點向根節(jié)點反溯的方式,即3-3-5-7父節(jié)點為3-2-2-3節(jié)點,依次向上追溯到根節(jié)點為3-1-1-1,3-0-0-0,即從根節(jié)點到檢索節(jié)點的遍歷路徑為3-0-0-0到3-1-1-1再到3-2-2-3最后到3-3-5-7節(jié)點,從而需要四次節(jié)點訪