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

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

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

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

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

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

6、X2,Y2）對(duì)應(yīng)包含的數(shù)據(jù)塊編號(hào)即可。（2） 金字塔建立金字塔是指在同一的空間參照下，根據(jù)用戶需求以不同分辨率進(jìn)行存儲(chǔ)和實(shí)現(xiàn)，形成分辨率油由低到高，數(shù)據(jù)量由小到大的金字塔結(jié)構(gòu)。這樣在數(shù)據(jù)的最底層存儲(chǔ)最高分辨率的數(shù)據(jù)，然后隨著金字塔層數(shù)的增加，數(shù)據(jù)的分辨率依次降低，數(shù)據(jù)量依次減少，在金字塔的頂層，則僅僅存儲(chǔ)用戶所需要的最小分辨率的數(shù)據(jù)。在進(jìn)行顯示時(shí)，根據(jù)當(dāng)前用戶的瀏覽范圍及顯示設(shè)備的分辨率和范圍，使用能夠滿足用戶視覺(jué)要求的金字塔層次中的最高層數(shù)據(jù)作為顯示數(shù)據(jù)，這種方式在一定程度上會(huì)增加數(shù)據(jù)存儲(chǔ)開(kāi)銷，但能加快實(shí)時(shí)顯示速度。（3） 基于金字塔的瓦片分割與數(shù)據(jù)調(diào)度數(shù)據(jù)金字塔建立之后要分別對(duì)其各層數(shù)據(jù)進(jìn)

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

8、的瓦片數(shù)據(jù)的編號(hào)可以按照四叉樹(shù)分裂規(guī)則直接計(jì)算出其上一層或下一層需要加載的瓦片數(shù)據(jù)編號(hào)，如當(dāng)前視域范圍內(nèi)加載的瓦片的空間編號(hào)為5-5-15-25（即第三個(gè)Face的第五級(jí)橫坐標(biāo)為15，縱坐標(biāo)為25）的瓦片，隨著距離的拉近需要更加清晰的數(shù)據(jù)來(lái)填充當(dāng)前的地理范圍，則對(duì)該瓦片進(jìn)行四叉樹(shù)分割后的四個(gè)瓦片的編號(hào)分別為3-6-30-50、3-6-30-51、3-6-31-50、3-6-31-51，從而可以根據(jù)瓦片的編號(hào)直接請(qǐng)求響應(yīng)的瓦片數(shù)據(jù)即可。圖 3 瓦片數(shù)據(jù)分割圖2、 海量瓦片數(shù)據(jù)優(yōu)化管理方案1. 瓦片數(shù)據(jù)的緊縮處理由于瓦片的數(shù)據(jù)通常以離散文件的形式存在，因此對(duì)于瓦片數(shù)據(jù)進(jìn)行必要的緊縮處理可以大大提高

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

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

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

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

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

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

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

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

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

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