楊佳穎，毛 健，崔鐵軍，劉朋飛

（天津師范大學(xué)地理與環(huán)境科學(xué)學(xué)院，天津 300387）

現(xiàn)實(shí)世界中有許多數(shù)據(jù)與空間位置相關(guān)，而空間索引是一種依據(jù)空間對(duì)象的位置和形狀或空間對(duì)象間某種空間關(guān)系，按照一定順序排列的數(shù)據(jù)結(jié)構(gòu)，對(duì)海量空間數(shù)據(jù)進(jìn)行篩選，進(jìn)而提高空間操作速度和效率的方法.空間索引方法的選擇直接決定了地理空間數(shù)據(jù)檢索的整體性能.

導(dǎo)航體驗(yàn)的好壞主要取決于導(dǎo)航數(shù)據(jù)的顯示效率，而導(dǎo)航數(shù)據(jù)顯示的核心是道路.道路又分為不同等級(jí)，不同等級(jí)的道路是否顯示取決于當(dāng)前用戶選擇的地圖顯示范圍.當(dāng)?shù)貓D顯示的范圍較大時(shí)，導(dǎo)航顯示較高等級(jí)的道路；當(dāng)?shù)貓D顯示范圍較小時(shí)，則顯示該區(qū)域內(nèi)的詳細(xì)道路.傳統(tǒng)空間索引往往僅依據(jù)當(dāng)前選擇范圍指導(dǎo)系統(tǒng)讀取該當(dāng)前范圍內(nèi)所有等級(jí)的道路數(shù)據(jù)，而并不是所需顯示等級(jí)的道路數(shù)據(jù)，導(dǎo)致導(dǎo)航數(shù)據(jù)讀取時(shí)間過長(zhǎng)，效率降低，因此導(dǎo)航數(shù)據(jù)的讀取時(shí)間是影響導(dǎo)航數(shù)據(jù)顯示效率的關(guān)鍵.道路等級(jí)存在于導(dǎo)航數(shù)據(jù)的屬性中，如果能在傳統(tǒng)空間索引的檢索中加入對(duì)道路等級(jí)屬性的判讀，僅讀取需要顯示的等級(jí)道路勢(shì)必會(huì)提高導(dǎo)航數(shù)據(jù)的顯示效率.導(dǎo)航數(shù)據(jù)的多級(jí)顯示可以通過劃分道路等級(jí)來實(shí)現(xiàn)，而道路等級(jí)信息存在于導(dǎo)航數(shù)據(jù)的屬性中，因此，傳統(tǒng)空間索引與屬性索引相結(jié)合可以在多尺度顯示的前提下提高導(dǎo)航數(shù)據(jù)的索引效率.傳統(tǒng)的屬性索引依靠關(guān)鍵字來進(jìn)行檢索，多用于B+樹索引，它與空間索引是2種不同的索引形式，雖然屬性索引和空間索引的發(fā)展都已經(jīng)相對(duì)成熟，但二者結(jié)合的應(yīng)用還較少[1-2].現(xiàn)有的空間索引方法通常只考慮空間位置，對(duì)于導(dǎo)航數(shù)據(jù)的多級(jí)顯示特點(diǎn)未給予足夠支持[3-4].本研究從傳統(tǒng)空間索引K-D入手，結(jié)合導(dǎo)航數(shù)據(jù)道路等級(jí)屬性，構(gòu)建一種顧及屬性的空間索引機(jī)制，在保證索引效率的同時(shí)，減少當(dāng)數(shù)據(jù)目標(biāo)較大時(shí)系統(tǒng)產(chǎn)生的數(shù)據(jù)冗余.

1 傳統(tǒng)K-D樹空間索引技術(shù)

K-D樹是Bentley[5]在1975年提出的一種二叉索引樹，它支持k維空間點(diǎn)數(shù)據(jù)，每個(gè)K-D樹的節(jié)點(diǎn)根據(jù)大小將所表示的k維空間分為大于節(jié)點(diǎn)值和小于節(jié)點(diǎn)值兩部分，每個(gè)節(jié)點(diǎn)中都分散存儲(chǔ)了空間點(diǎn)數(shù)據(jù).此外，K-D樹繼承了二叉索引樹簡(jiǎn)單、索引效率高的特點(diǎn).一棵完整的K-D樹的節(jié)點(diǎn)描述包括中間節(jié)點(diǎn)（COUNT，DEPTH，＜CP1，MBR1＞，＜CP2，MBR2＞）和葉子節(jié)點(diǎn)（COUNT，DISLEVEL，＜OI1，MBR1＞，＜OI2，MBR2＞，…，＜OIM，MBRM＞）.其中＜OIi，MBRi＞為數(shù)據(jù)項(xiàng)；OIi為空間對(duì)象標(biāo)識(shí)；MBRi為該空間對(duì)象在k維空間中的最小外接矩形；CPi和MBRi為索引項(xiàng)，CPi為指向子樹根節(jié)點(diǎn)的指針，MBRi表示其子樹索引空間.COUNT≤M表示該節(jié)點(diǎn)中索引項(xiàng)或空間對(duì)象的個(gè)數(shù)，DEPTH表示該節(jié)點(diǎn)在樹中的深度.若m和M分別為索引項(xiàng)或數(shù)據(jù)集的最小和最大個(gè)數(shù)，H為樹的深度，N為空間對(duì)象總個(gè)數(shù)，則H∈[logmN，logMN]，LEVEL≤H.K-D樹的具體實(shí)現(xiàn)形式如圖1所示，其中A點(diǎn)為根節(jié)點(diǎn)，包含了指向左、右兩棵子樹的指針；B、C和G為中間節(jié)點(diǎn)，包含了指向父節(jié)點(diǎn)的指針和指向其左、右兩棵子樹的指針；D、E、F、H和I為葉節(jié)點(diǎn)，包含了指向父節(jié)點(diǎn)的指針以及數(shù)據(jù)的地址等信息.

圖1 K-D樹的形式Fig.1 Form of K-D tree

K-D樹屬于動(dòng)態(tài)索引結(jié)構(gòu)，為非平衡樹[6].同時(shí)，K-D樹在每一層的分枝決策都可以通過該層的分辨器對(duì)相應(yīng)對(duì)象進(jìn)行實(shí)現(xiàn)，并以此類推，在各維中不斷劃分，直至某一節(jié)點(diǎn)中的點(diǎn)數(shù)小于給定的最大點(diǎn)數(shù)，結(jié)束這種劃分.劉宇等[7]對(duì)此問題加以研究，對(duì)本研究具有一定的指導(dǎo)意義.隨著嵌入式導(dǎo)航的快速發(fā)展，國(guó)內(nèi)外學(xué)者在以上幾種空間索引的基礎(chǔ)上，結(jié)合嵌入式導(dǎo)航數(shù)據(jù)的特點(diǎn)，進(jìn)行了一系列研究和改進(jìn).劉春等[8]研究了道路數(shù)據(jù)的空間組織，分析了路網(wǎng)的3個(gè)描述層次，并概括了路網(wǎng)的基本組成要素和用來描述路網(wǎng)的數(shù)據(jù)集，同時(shí)采用K-D樹進(jìn)行空間索引和組織，組成路網(wǎng)的主要要素道路節(jié)點(diǎn).由于K-D樹實(shí)現(xiàn)算法簡(jiǎn)單，且符合導(dǎo)航數(shù)據(jù)通過不同等級(jí)屬性（尤其是道路等級(jí)）的對(duì)比進(jìn)行篩選的特點(diǎn)，可以大幅提高空間索引的效率.

2 顧及屬性的空間索引構(gòu)建

2.1 設(shè)計(jì)思想

根據(jù)導(dǎo)航數(shù)據(jù)中不同等級(jí)道路顯示取決于當(dāng)前地圖顯示范圍的特點(diǎn)，在不改變傳統(tǒng)空間數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的前提下，將道路等級(jí)屬性嵌入到K-D樹索引中，在依據(jù)用戶選擇進(jìn)行檢索時(shí)，使新空間索引不僅進(jìn)行空間范圍的判斷，同時(shí)進(jìn)行簡(jiǎn)單道路等級(jí)的判斷，從而進(jìn)一步減少導(dǎo)航數(shù)據(jù)的讀取量，提高導(dǎo)航數(shù)據(jù)的顯示效率.

2.2 基本算法

K-DA樹的構(gòu)建過程如圖2所示.

圖2 顧及屬性情況下K-DA樹的構(gòu)建過程Fig.2 Construction of the K-DA tree in view of the attributes

（1）首先定義一棵完整的K-D樹，這棵樹具有傳統(tǒng)K-D樹索引的形式，葉節(jié)點(diǎn)中不帶有屬性信息（如圖2中黑色部分所示）.

（2）在樹的葉節(jié)點(diǎn)中添加屬性信息（如圖2中紅色部分所示）.

（3）為使屬性判定盡量上移，需要從葉子節(jié)點(diǎn)開始，遞歸構(gòu)建每個(gè)節(jié)點(diǎn)的屬性信息，直至根節(jié)點(diǎn).一般過程為：若同一棵子樹的2個(gè)葉節(jié)點(diǎn)所包含的屬性信息一致，則將該屬性信息移至這2個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)處，如屬性信息不一致，則父節(jié)點(diǎn)屬性為null.如圖2中紅色部分所示，設(shè)H和I兩葉節(jié)點(diǎn)所包含的屬性信息一致，均為att1，則其父節(jié)點(diǎn)G的屬性信息為att1；而D和E兩葉子節(jié)點(diǎn)屬性信息不同，則其父節(jié)點(diǎn)B的屬性為null，以此類推直到根節(jié)點(diǎn)A.

構(gòu)建完成后，K-DA樹的節(jié)點(diǎn)由中間節(jié)點(diǎn)（COUNT，DEPTH，＜CP1，MBR1，ATT1＞，＜CP2，MBR2，ATT2＞）和葉子節(jié)點(diǎn)（COUNT，DISLEVEL，＜OI1，MBR1，ATT1＞，＜OI2，MBR2，ATT2＞，…，＜OIM，MBRM，ATTM＞）組成.其中＜OIi，MBRi＞為數(shù)據(jù)項(xiàng)；OIi為空間對(duì)象標(biāo)識(shí)；MBRi為該空間對(duì)象在k維空間中的最小外接矩形；ATTi為葉節(jié)點(diǎn)中儲(chǔ)存的屬性；＜CPi，MBRi＞為索引項(xiàng)，CPi為指向子樹根節(jié)點(diǎn)的指針，MBRi代表其子樹索引空間；COUNT≤M代表該節(jié)點(diǎn)中索引項(xiàng)或空間對(duì)象的個(gè)數(shù)；DEPTH表示該節(jié)點(diǎn)在樹中的深度.若m和M分別為索引項(xiàng)或數(shù)據(jù)集的最小和最大個(gè)數(shù)，H為樹的深度，N為空間對(duì)象總個(gè)數(shù)，則H∈[logmN，logMN]，LEVEL≤H.

2.2.1 K-DA樹的算法思路

構(gòu)建K-DA樹算法的主要步驟為：

（1）對(duì)每個(gè)對(duì)象構(gòu)建最小外包矩形：根據(jù)外包矩形的構(gòu)建方法，對(duì)每個(gè)對(duì)象（每條道路）建立最小外包矩形，當(dāng)有一個(gè)對(duì)象小于特定值導(dǎo)致最小外包矩形很小時(shí)，對(duì)它及其相鄰的對(duì)象放在一起構(gòu)造最小外接矩形.

（2）構(gòu)建整體的最小外包矩形：根據(jù)已構(gòu)建好的若干對(duì)象的最小外包矩形，通過獲取將要包含的最小外包矩形的min x、max x、min y和max y，逐個(gè)構(gòu)造出包含所有對(duì)象的最小外包矩形.

（3）構(gòu)造子樹：設(shè)定K-DA樹的最大深度maxdepth，判定條件為若當(dāng)前深度小于樹的最大深度，葉節(jié)點(diǎn)的最小對(duì)象數(shù)要大于2，且滿足外包矩形的面積大于最小閾值或?qū)ο罅斜頂?shù)大于5，則通過比較當(dāng)前對(duì)象最小外包矩形中點(diǎn)的x1與所得最小外包矩形中點(diǎn)的x2，將x1小于x2的對(duì)象放入左子樹objBuckets[0]，將x1大于x2的對(duì)象放入右子樹objBuckets[1]，再分別對(duì)左右子樹進(jìn)行類似判斷，繼續(xù)劃分左右子樹直至葉節(jié)點(diǎn)，其中，葉節(jié)點(diǎn)中存儲(chǔ)了地址和屬性信息.

（4）如果不滿足判定條件，則當(dāng)前節(jié)點(diǎn)為葉節(jié)點(diǎn).

（5）當(dāng)節(jié)點(diǎn)被判定為葉節(jié)點(diǎn)后，將屬性嵌入葉節(jié)點(diǎn)中，當(dāng)一棵子樹2個(gè)葉節(jié)點(diǎn)所嵌入的屬性相同時(shí)，則將葉節(jié)點(diǎn)中的屬性嵌入至這2個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)子樹的父節(jié)點(diǎn)中.具體構(gòu)建算法為

2.2.2 索引查詢過程

（1）構(gòu)建用戶所要求的窗口，從K-DA樹的根節(jié)點(diǎn)開始由上至下進(jìn)行遞歸查詢.如有節(jié)點(diǎn)的對(duì)象不為空（即節(jié)點(diǎn)中包含道路對(duì)象），則將其判定為葉節(jié)點(diǎn).此時(shí)開始依次判斷葉節(jié)點(diǎn)中道路對(duì)象的最小外接矩形是否與用戶要求的窗口有相交部分.如果有相交部分，則將該葉節(jié)點(diǎn)中的屬性（道路等級(jí)）與用戶要求的屬性（道路等級(jí)）進(jìn)行對(duì)比.如屬性（道路屬性）匹配，則將葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)輸出；如屬性（道路等級(jí)）不匹配，則不輸出葉節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù).如果葉節(jié)點(diǎn)中道路對(duì)象的最小外接矩形與用戶要求的窗口沒有相交部分，則不輸出對(duì)應(yīng)的數(shù)據(jù).以上過程將“先讀取后判斷”轉(zhuǎn)化為“先判斷再讀取”，避免了冗余數(shù)據(jù)的讀取.

（2）當(dāng)某節(jié)點(diǎn)中的對(duì)象為空時(shí)（即節(jié)點(diǎn)中不包含道路對(duì)象），其不是葉節(jié)點(diǎn)，而是中間節(jié)點(diǎn)，也稱非葉節(jié)點(diǎn).在非葉節(jié)點(diǎn)的情況下，判斷非葉節(jié)點(diǎn)的最小外接矩形與用戶要求的窗口是否有相交部分.如果有相交部分，則繼續(xù)判斷非葉節(jié)點(diǎn)中的屬性（道路等級(jí)）和用戶要求的屬性（道路等級(jí)）是否匹配.如果屬性（道路等級(jí)）匹配，則繼續(xù)向下查詢子節(jié)點(diǎn)時(shí)不需要再對(duì)比屬性；如果非葉節(jié)點(diǎn)中的屬性為空，證明該節(jié)點(diǎn)2個(gè)子節(jié)點(diǎn)的屬性不一樣，則繼續(xù)向下查詢子節(jié)點(diǎn).如果非葉節(jié)點(diǎn)的最小外接矩形與用戶要求的窗口沒有相交部分，則停止查詢，依次類推.

以上過程的具體實(shí)現(xiàn)算法為

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)方法

（1）硬件條件：實(shí)驗(yàn)所用嵌入式設(shè)備處理器為四核，運(yùn)算速度為1.2 GHz；運(yùn)行內(nèi)存為2 GB；手機(jī)儲(chǔ)存為16 GB.

（2）軟件條件：java編程軟件為eclipse，需Android 4.4.4平臺(tái).

（3）數(shù)據(jù)來源：天津地區(qū)的導(dǎo)航數(shù)據(jù)，其中道路總數(shù)99 369條，共分8個(gè)等級(jí).

（4）測(cè)試方案：為了測(cè)評(píng)K-DA樹的性能，在Android平臺(tái)分別編寫K-D與K-DA樹索引方法的java代碼.按照查詢的空間對(duì)象個(gè)數(shù)，共分8組數(shù)據(jù)，并對(duì)比相同查詢范圍內(nèi)，傳統(tǒng)索引與顧及屬性新索引的耗時(shí).每組數(shù)據(jù)測(cè)試10次，取其平均值作為最終結(jié)果.每次實(shí)驗(yàn)均需重啟程序，避免內(nèi)存空間對(duì)測(cè)試結(jié)果的影響.

3.2 測(cè)試結(jié)果與分析

分別取 133、1 334、2 752、4 330、7 167、11 215、14 804和20 424條道路的8組數(shù)據(jù)進(jìn)行測(cè)試，得到傳統(tǒng)索引的耗時(shí)分別為 28、121、225、381、1 069、1 585、2 100和3 372 ms，新索引方法的耗時(shí)分別為10、41、105、167、350、560、692 和 1 248 ms，結(jié)果圖 3 所示.

圖3 傳統(tǒng)索引和新索引耗費(fèi)的時(shí)間對(duì)比Fig.3 Comparison of the time spent between traditional and new indexes

由圖3可以看出，隨著查詢空間對(duì)象個(gè)數(shù)的增加，2種空間索引的檢索耗時(shí)都在增加.這是因?yàn)殡S著查詢空間對(duì)象數(shù)量的增多，索引數(shù)據(jù)節(jié)點(diǎn)的訪問次數(shù)、數(shù)據(jù)的讀取次數(shù)以及屬性的判定次數(shù)均隨之增多，導(dǎo)致耗時(shí)增加.但與傳統(tǒng)空間索引相比，K-DA在每組查詢中的耗時(shí)分別約為傳統(tǒng)索引花費(fèi)時(shí)間的50%、40%和30%，且隨著查詢數(shù)量的增加，節(jié)約的時(shí)間更多.其原因主要為

（1）節(jié)省讀取時(shí)間.傳統(tǒng)空間索引沒有顧及屬性，在索引時(shí)將所有數(shù)據(jù)全部讀取，并根據(jù)用戶所給定的索引條件，從全部讀取出的數(shù)據(jù)中篩選出符合條件的信息，再進(jìn)行顯示；而顧及屬性的新索引已經(jīng)將屬性信息添加至K-D樹的葉節(jié)點(diǎn)中，所以在索引時(shí)，根據(jù)用戶給定的索引條件，可以直接篩選出符合要求的葉節(jié)點(diǎn)中的屬性對(duì)應(yīng)的數(shù)據(jù)，不用讀出全部數(shù)據(jù)，因此在此環(huán)節(jié)節(jié)省大量時(shí)間.

（2）節(jié)省檢索時(shí)間.傳統(tǒng)的空間索引在檢索時(shí)，需要檢索所有數(shù)據(jù)，搜索范圍很大.而新的K-DA檢索過程中，由于在K-D樹的葉節(jié)點(diǎn)添加了屬性，縮小了需要搜索的范圍，所以節(jié)約了檢索時(shí)間，提高了檢索的效率.

4 結(jié)論

本研究將導(dǎo)航數(shù)據(jù)道路等級(jí)屬性與空間索引相結(jié)合，研究顧及屬性的K-D樹空間索引方法，提出的K-DA空間索引機(jī)制在傳統(tǒng)K-D空間索引的基礎(chǔ)上，擴(kuò)展了屬性項(xiàng)，使其在保留傳統(tǒng)空間篩選功能的同時(shí)，增加了屬性判斷，減少了數(shù)據(jù)的冗余讀取，讀取速度在每組查詢中的耗時(shí)分別約為傳統(tǒng)索引耗時(shí)的50%、40%和30%，且隨著數(shù)據(jù)量的增加，K-DA樹索引時(shí)間與傳統(tǒng)索引時(shí)間比例更小，索引效率更高.新索引機(jī)制不僅可以用于導(dǎo)航數(shù)據(jù)，還可以用于傳統(tǒng)空間數(shù)據(jù)的索引，且算法不會(huì)對(duì)傳統(tǒng)空間索引的本質(zhì)產(chǎn)生影響，方法靈活，具有一定的普適性.

參考文獻(xiàn)：

[1] 牛紅光.基于R樹和Petri網(wǎng)的多尺度表達(dá)模型研究[D].鄭州：信息工程大學(xué)，2006.NIU H G.Research on Multi Scale Expression Model Based on R Tree and Petri Net[D].Zhengzhou：Information Engineering University，2006（in Chinese）.

[2]付偉.基于R樹的空間索引技術(shù)的研究與應(yīng)用[D].成都：四川大學(xué)，2006.FU W.Research and Application of Spatial Indexing Technology Based on RTree[D].Chengdu：Sichuan University，2006（in Chinese）.

[3] 余登峰.基于R樹的空間數(shù)據(jù)索引技術(shù)研究與實(shí)現(xiàn)[D].武漢：中國(guó)地質(zhì)大學(xué)，2006.YU D F.Research and Implementation of Spatial Data Indexing Technology Based on R Tree[D].Wuhan：China University of Geosciences，2006（in Chinese）.

[4]周帆.基于R-樹的空間數(shù)據(jù)索引技術(shù)的研究與實(shí)現(xiàn)[D].哈爾濱：哈爾濱理工大學(xué)，2009.ZHOU F.Research and Implementation of Spatial Data Indexing Technology Based on R-tree[D].Haerbin：Harbin Polytechnic University，2009（in Chinese）.

[5] BENTLY J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517.

[6]閻德超，趙學(xué)勝.GIS空間索引方法述評(píng)[J].地理與地理信息科學(xué)，2004，20（4）：23-26.YAN D C，ZHAO X S.A review of GIS spatial indexing methods[J].Geography and Geographic Information Science，2004，20（4）：23-26（in Chinese）.

[7] 劉宇，熊有倫.基于有界K-D樹的最近點(diǎn)搜索方法[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，36（7）：73-76.LIU Y，XIONG Y L.The nearest point search method based on bounded K-D tree[J].Journal of Huazhong University of Science and Technology（Natural Science Edition），2008，36（7）：73-76（in Chinese）.

[8]劉春，史文中，劉大杰.導(dǎo)航電子地圖中道路數(shù)據(jù)的空間索引和組織[J].工程勘察，2003（1）：38-41.LIU C，SHI W Z，LIU D J.Spatial index and organization of road data in navigation electronic map[J].Engineering Investigation，2003（1）：38-41（in Chinese）.