基于Hadoop的QR樹索引方法

馮 鈞，任 鋒，唐志賢

（河海大學 計算機與信息學院，江蘇 南京211100）

0 引 言

隨著信息技術的迅猛發(fā)展，各種高新技術應用會周期性地生成海量的空間數據[1]。因而組織和使用這些數據顯得愈發(fā)的重要?？臻g數據通常形式多樣、規(guī)模巨大、計算復雜。這些特性使得如何深度地利用空間數據成為一項具有挑戰(zhàn)性的工作。高效的數據訪問是深度利用海量數據的前提，如何高效地對空間離散數據進行索引以滿足日益增長數據應用的的實時性需求以成為數據庫領域的一個研究熱點[2－4]。

最基本的空間離散數據索引方法是通過將整個空間區(qū)域劃分成不同的部分，再在各個區(qū)域中按照一定的順序查找數據。典型的primary index有B樹、K－D樹、K－D－B樹、四叉樹、R樹及其變體[5，6]等等。在海量空間數據的情況下，往往導致樹的深度過深，上述結構的檢索效率明顯較低。secondary index作為一種混合式索引結構，常見的有QR樹[7]、PMR樹[8]、Hilbert R樹[9]等等，通過兩級級索引的方式能夠有效降低樹的深度，提高檢索效率，但是由于結構復雜，在處理海量數據時會帶來龐大的計算量。面對海量空間數據處理與查詢的復雜性，傳統(tǒng)的集中式處理方式已經變成制約處理和查詢效率的 “瓶頸”。隨著 “云計算”的興起，其所具有擴展性好、容錯性強同時具有強大的數據并行處理能力的特點，為突破上述 “瓶頸”提供了一個很好的思路[10]。Hadoop[11]是由 Apache基金會開發(fā)的開源分布式架構，結合MapReduce能夠對海量空間數據以一種可靠、高效、可伸縮的方式進行處理。

本文提出一種基于Hadoop的QR Tree分布式空間索引，索引存儲在HDFS文件系統(tǒng)中的空間數據；利用四叉樹對索引空間的分層劃分，減少R樹空間重疊和查找失敗路徑，有效的解決數據非均勻分布時的不平衡問題。借助Hadoop平臺強大的MapReduce并行編程框架設計相應的數據處理算法，改善索引建立過程，提高查詢過程的效率。

1 Hadoop QR Tree索引結構設計

邏輯結構

基于Hadoop的QR樹將四叉樹與R樹結合起來。它通過四叉樹將整個空間劃分成至多個子空間 （k為空間維度）。四叉樹的每個節(jié)點對應一個獨立的R樹。R樹通過其最小外包矩形 （MBR）確定所屬四叉樹節(jié)點。空間數據都存儲在R樹中。假設四叉樹節(jié)點的最大容量為Vmax，即各個子空間中數據量最大為Vmax。當某數據空間中數據量超過Vmax時，需要進行分裂。假設圖1（a）中數據量超過子空間最大容量Vmax，本文使用四叉樹將原數據空間劃分為5個子空間。如圖1（b）、圖1（c）所示，原空間中數據根據其空間位置劃歸到各子空間中。若原空間中有數據與多個下層子空間有交集，則將其劃分到上層子空間[12]。

Hadoop QR Tree（HQR Tree）索引支持離散數據查詢和區(qū)域查詢。HQR Tree利用四叉樹將整個索引空間分成多個子空間，并分別為每子空間中的數據建立R樹，不同子空間中空間數據彼此無交集。

如圖2所示的是一棵二維空間的QR樹，空間區(qū)域內包含多個空間數據 （包括點數據和面數據）。圖2中QR樹的高度為4，有14個R樹。整個空間區(qū)域被劃分成20個子區(qū)域，共有四層:S1，S2，S3……S20。其中S0＝S1∪S2∪S3∪S4，S1＝S5∪S6∪S7∪S8等。同時有20棵R樹R1，R2，R3……R20，每課R樹都對應一個子空間。每個四叉樹節(jié)點包含的子空間均由其上層節(jié)點所包含的空間分裂而來。當上層節(jié)點的中數據量超過節(jié)點最大容量時，需要分裂。以空間S1為例，S1中數量超過最大容量，使用四叉樹將S1劃分成S5，S6，S7，S8這5個子空間?？臻g區(qū)域上，S5，S6，S7，S8彼此無交集，且S1與原空間區(qū)域大小相同，為S5，S6，S7，S8空間區(qū)域之和，同時S5，S6，S7，S8在四叉樹中作為原節(jié)點的新增孩子節(jié)點存在，而S1取代原節(jié)點。原空間中數據根據空間位置插入子空間S5，S6，S7，S8中，若有數據同時與S5，S6，S7，S8中多個有交集，則插入S1中。數據r1落在子空間S5中且不與其他子空間相交，則r1被插入到R5中；而r2與S1，S5，S6，S7，S8相交，根據上述空間分裂規(guī)則，插入子空間S0中，因此數據r11被插入到中。

2 基于MapReduce并行創(chuàng)建索引

索引創(chuàng)建算法

本文利用MapReduce改造索引創(chuàng)建算法?；舅枷?首先用四叉樹將索引空間劃分成個子空間，建立一棵四叉樹，四叉樹的每個節(jié)點都對應一棵R樹，當四叉樹節(jié)點對應子空間數據超過最大容量時將導致節(jié)點分裂。將數據的MBR與各子空間比較，尋找能夠完全將其包含的最小子空間，將數據映射到該子空間。若子空間達到最大容量，則進行分裂。最后，為每個子空間分別建立R樹。數據空間的劃分和各個子空間R樹的建立過程由Map函數實現，完成后返回相應信息，由Reduce函數將各個R樹合并起來并掛載到四叉樹節(jié)點上，最終形成一個全局的QR樹。

圖2 QR樹空間劃分和樹結構

3 分布式并行查詢策略

3.1 離散數據查詢

基本思想:首先將給定的離散數據數據分組，根據每個空間數據的空間位置判斷是否在索引空間中。自上而下查詢HQR－tree，與各四叉樹節(jié)點比較，尋找完全包含數據的最小四叉樹節(jié)點，接著從此節(jié)點對應的R樹中查詢數據。

3.2 區(qū)域查詢

基本思想:根據待查詢區(qū)域空間信息查詢索引空間中存在數據。自上而下查詢 HQR－tree，與各四叉樹節(jié)點比較，尋找出與待查詢區(qū)域相交的四叉樹節(jié)點，接著從這些節(jié)點對應的R樹中查詢完全包含在相交區(qū)域中的數據。

3.3 索引算法性能分析

假設分布式環(huán)境下計算節(jié)點個數為N，每個節(jié)點所能并行運行的Map函數和Reduce函數最多分別為Mn和Rn。則整個系統(tǒng)最大Map函數數為

遍歷四叉樹，耗時為τq，遍歷R樹，耗時為τr；

（1）離散數據

查詢待查詢數據量為O，劃分成若干組，每組最多有S個數據 （S≤O），則有個分組。

1）處理單個分組中每個數據是否在四叉樹中所需時間為tQ，有

2）處理單個分組中每個數據是否在R樹中所需時間為tR，有

當單次四叉樹和R樹查詢時間不變時，處理時間與每組的數據數S和Map函數個數有關，當S越少同時Map函數個數越多時，處理單個組耗時越少，反之耗時變長。

由上述可得，系統(tǒng)需要順序執(zhí)行的Map數Mo為

查詢O個數據是否在四叉樹中耗時

查詢O個數據是否在R樹中耗時

則總處理時間

分析上式 （7）可得，相較于集中式索引響應時間O×（τq＋τr），分布式QR樹通過分布式環(huán)境分散檢索的計算量，在數據個數不變的情況下通過增加計算節(jié)點來減少查詢時間，提高檢索效率。

（2）區(qū)域查詢

與待查詢區(qū)域相交節(jié)點數為Cn，對應Cn棵R樹，劃分成若干組，每組有S個數據 （S≤Cn），則至少有G＝個這樣的分組。

處理單個分組，遍歷R樹，查詢并返回相交區(qū)域中數據耗時為

由上述可得，系統(tǒng)需要順序執(zhí)行的Map數Ma為

則總處理時間

分析上式，當增加計算節(jié)點的數量N和每個節(jié)點上的Map函數數量Mn時，能夠有效減少區(qū)域查詢的總處理時間T。而在集中式環(huán)境下相同條件的區(qū)域查詢總處理時間為τq＋τr×Cn。相比較可得，在分布式環(huán)境下算法查詢效率更高。

根據上述對離散數據檢索和區(qū)域檢索的性能分析 （見式 （7），式 （10）），響應時間T與系統(tǒng)計算節(jié)點數成正比，當計算節(jié)點個數增加時，能夠有效的減少響應時間T。HQR－Tree相對于集中式算法能夠有效的減少系統(tǒng)響應時間，提高檢索效率。

4 索引更新策略

索引空間區(qū)域插入或刪除數據時，可能帶來索引節(jié)點的分類或合并。其中節(jié)點的分裂和合并包括上層四叉樹節(jié)點的更新和各四叉樹節(jié)點對應R樹的更新。

圖3 HQR－Tree更新

如圖3（a）所示，當空間S中插入新的空間數據r10時，四叉樹節(jié)點S分裂成S0，S1，S2，S3，S4。相應的空間S所對應的R樹將分裂成五個不同的子R樹:R0，R1，R2，R3，R4，如圖3（b）所示。反之，若刪除空間數據r10，則四叉樹節(jié)點S0，S1，S2，S3，S4合并成一個節(jié)點S；同時各四叉樹節(jié)點對應的R樹R0，R1，R2，R3，R4也合并成一棵R樹。

（1）數據插入

（2）數據刪除

5 實驗及分析

5.1 實驗環(huán)境設置

本實驗比較集中式環(huán)境下和分布式環(huán)境下處理大規(guī)模數據。

集中式環(huán)境:操作系統(tǒng):Windows 7；CPU:英特爾酷睿i5－2300CPU ＠ 2.80GHz（單 核）；內 存:1GB ，DDR3，單通道 ；硬盤:希捷ST31000524AS，7200轉 ，1000GB。

分布式環(huán)境:一臺主節(jié)點，三臺從節(jié)點，Ip分別為10.196.80.90／91／92／93。

操作系統(tǒng)均為Oracle Linux Server release 6.3，hadoop版本:1.0.4。其中主節(jié)點內存為1G，從節(jié)點為1G、1.5G、2G不等。CPU主節(jié)點為英特爾單核2.60GHz、從節(jié) 點 為 英 特 爾 雙 核 3.20GHz、 雙 核 1.60GHz、 單核2.66GHz。

實驗程序實現:Myeclipse10.6，JDK1.6。

5.2 索引創(chuàng)建

實驗采用隨機生成的10萬、20萬、50萬、100萬、200萬、500萬、800萬、1000萬8組空間數據作為實驗數據，分別測試在集中式環(huán)境下和分布式環(huán)境下建立索引所耗費的時間，用以分析比較并行計算和集中式計算的效率。其中四叉樹節(jié)點容量為512KB。

如圖4所示為集中式和分布式環(huán)境下創(chuàng)建QR樹的對比關系。其中橫坐標為實驗數據量，縱坐標位創(chuàng)建索引所需的時間。在分析8組隨機空間數據可得，在數據量較小時，集中式創(chuàng)建索引較有優(yōu)勢。這是因為，使用分布式計算時，需要花費時間進行數據的分割和計算節(jié)點的通信，而單機環(huán)境下不存在此問題。但是，當數據量開始變大時，如上實驗，當本實驗環(huán)境下，在數據量超過500萬時，分布式環(huán)境在為空間數據建立索引時已經開始比集中是創(chuàng)建索引具有優(yōu)勢。此時，隨著數據量的增大，計算節(jié)點的通信開銷及數據分割的開銷對建索引效率的影響將越來越低。

圖4 隨機數據在集中式環(huán)境和分布式環(huán)境下建立索引耗時圖 （單位:ms）

5.3 隨機數據查詢

隨機數據查詢實驗采用500萬個數據的索引作為實驗數據，分別在集中是環(huán)境下和分布式環(huán)境下進行查詢。查詢次數為 （單位:次）:10，100，1000，1萬，10萬，20萬，50萬，100萬。

圖5 隨機數據在集中式環(huán)境和分布式環(huán)境下查詢耗時圖 （單位:ms）

圖5 所示為隨機數據在集中是環(huán)境和分布式環(huán)境下查詢的耗時，其中縱坐標為查詢時間，橫坐標為查詢次數。與建索引時類似，當查詢次數較少時，單機查詢耗時要小于分布式環(huán)境下耗時，但當次數增加到1000次及以上時，分布式環(huán)境下的隨機數據查詢耗時開始優(yōu)于集中是環(huán)境。

6 結束語

HQR－Tree是一種基于Hadoop的分布式QR樹索引方法，用于處理海量空間數據。QR樹作為兩層索引結構結合了四叉樹和R樹的優(yōu)點，但由于其結構復雜，創(chuàng)建與維護代價大。通過研究發(fā)現，在分布式環(huán)境下建立QR樹，將計算量分散到各個計算節(jié)點中分別處理，可以有效降低算法響應時間，對處理海量空間數據具有良好的表現，大大提高數據處理效率。本文基于Hadoop平臺，結合MapReduce的思想，設計優(yōu)化了分布式環(huán)境下QR樹索引算法的建立和查詢過程 （包括點查詢和區(qū)域查詢）。理論分析與實驗結果表明，HQR－Tree的分布式算法在時間復雜度優(yōu)于QR－Tree。本文的進一步研究將針對HDFS文件系統(tǒng)的特點及動態(tài)數據的問題進行設計相應的解決方案進一步優(yōu)化HQR樹性能。

[1]Lee M W，Hwang S.Robust distributed indexing for localityskewed workloads[C]／／Proceedings of the 21st ACM International Conference on Information and Knowledge Management.ACM，2012:1342－1351.

[2]Wang J，Wu S，Gao H，et al.Indexing multi－dimensional data in a cloud system[C]／／Proceedings of the International Conference on Management of Data.ACM，2010:591－602.

[3]Wu S，Jiang D，Ooi B C，et al.Efficient b－tree based indexing for cloud data processing[J].Proceedings of the VLDB Endowment，2010，3 （1－2）:1207－1218.

[4]Zhu M，Shen D，Kou Y，et al.An adaptive distributed index for similarity queries in metric spaces[G].LNCS7418:Web－Age Information Management.Berlin:Springer Berlin Heidelberg，2012:222－227.

[5]Wang J，Wu S，Gao H，et al.Indexing multi－dimensional data in a cloud system[C]／／Proceedings of the International Conference on Management of Data.ACM，2010:591－602.

[6]Wu S，Jiang D，Ooi B C，et al.Efficient b－tree based indexing for cloud data processing[J].Proceedings of the VLDB Endowment，2010，3 （1－2）:1207－1218.

[7]Huang B，Wu Q.A spatial indexing approach for high performance location based services[J].Journal of Navigation，2007，60 （1）:83－94.

[8]Pelanis M，Saltenis S，Jensen C S.Indexing the past，present，and anticipated future positions of moving objects[J].ACM Transactions on Database Systems，2006，31 （1）:255－298.

[9]Zimek A，Schubert E，Kriegel H P.A survey on unsupervised outlier detection in high－dimensional numerical data[J].Statistical Analysis and Data Mining，2012，5 （5）:363－387.

[10]Tanin E，Harwood A，Samet H.Using a distributed quadtree index in peer－to－peer networks[J].The VLDB Journal，2007，16 （2）:165－178.

[11]Apache.Welcome to ApacheTMHadoop ！[EB／OL].[S].[2012－03－19].http:／／hadoop.apache.org／.

[12]GUO Wei.Spatial database indexing techniques[M].Shanghai:Shanghai Jiaotong University Press，2006:129－143 （in Chinese）.[郭薇.空間數據庫索引技術[M].上海:上海交通大學出社，2006:129－143.]