徐道柱,焦洋洋,金 澄

(1.信息工程大學 地理空間信息學院，河南 鄭州 450052;2 地理信息工程國家重點實驗室，陜西 西安 710054;3.西安測繪研究所，陜西 西安 710054)

分布式空間數據庫中矢量數據多級空間索引方法研究

徐道柱1,2,3,焦洋洋2,3,金 澄1,2,3

(1.信息工程大學 地理空間信息學院，河南 鄭州 450052;2 地理信息工程國家重點實驗室，陜西 西安 710054;3.西安測繪研究所，陜西 西安 710054)

隨著網格計算、云計算等技術在地理信息領域的應用，海量空間數據的高效組織與管理成為提供各種數據和功能服務的基礎，空間索引是其中的關鍵問題，文中在分布式空間數據庫系統(tǒng)架構基礎上，提出一種適應分布式環(huán)境下的分層+分塊的矢量數據存儲組織模型，設計包括矢量數據面片索引、矢量數據層索引、矢量數據塊索引以及數據塊內索引在內的多級空間索引。實現表明，文中設計的空間索引支持并發(fā)創(chuàng)建和高并發(fā)條件下的數據高效訪問。

分布式；空間數據庫；多級索引；矢量數據；HHCode索引

面對飛速增長的海量空間數據，傳統(tǒng)的數據管理方式已經顯得力不從心。隨著網格計算、云計算等技術在地理信息領域的應用，分布式系統(tǒng)架構與并行處理技術可大大提高地理信息管理、分析和應用的性能，已經成為研究的熱點。

海量空間數據的高效組織與管理是提供各種數據和功能服務的基礎，空間索引是其中的關鍵問題?？臻g索引方法大致可分為線性索引、網格索引和樹形索引三大類[1]，這幾類索引特點不同，適用場合也各不相同。線性索引是將索引項組織為線性結構，結構直觀簡單，但對海量空間數據的管理效率較低。網格索引結構簡單，效率較高，當實體增加導致實體分布不均勻需重構索引[2]。樹形索引是應用較為廣泛的空間索引結構，衍生索引結構比較多，高維索引大都基于樹形索引實現[3-4]。隨著分布式系統(tǒng)研究逐漸成為熱點，分布式、并行索引成為空間索引的研究熱點，文獻[5-6] 研究了ArcSDE在基礎地理信息數據庫存儲和設計的應用；文獻[7-10]研究了MR-tree、R 樹和多級R-tree等空間索引的并行化實現；文獻[11]對四叉樹進行面向列式存儲擴展改進，文獻[12-14]將VoR-Tree、雙層倒排網格索引、空間k近鄰查詢與MapReduce編程模型相結合進行分布式改造。

本文結合分布式環(huán)境下矢量數據的存儲組織模型，設計了一種多級空間索引，并對相關索引進行并行化改造提升索引效率，并針對數據存儲、索引構建、查詢訪問進行相關實驗。

1 分布式空間數據庫系統(tǒng)架構

分布式空間數據庫系統(tǒng)架構是矢量數據存儲組織模型以及空間索引設計的基礎，在進行矢量數據存儲組織模型和空間索引設計時需要充分考慮分布式架構下矢量數據的使用特點，有的放矢，才能充分發(fā)揮分布式架構在存儲量、吞吐量以及并發(fā)性等方面的優(yōu)勢。分布式空間數據庫系統(tǒng)架構由存儲層和矢量數據訪問引擎組成。如圖1所示。

圖1 分布式空間數據庫系統(tǒng)

1)存儲層。存儲層作為分布式空間數據庫的物理存儲中心，由關系型數據庫和分布式數據庫組成，其中關系型數據庫用于存儲矢量數據層的屬性數據、元數據，資源目錄等結構化信息；分布式數據庫由于存儲矢量數據，等半結構化數據文件。

2)矢量數據訪問引擎。矢量數據訪問引擎主要為上層應用提供統(tǒng)一的矢量數據存儲訪問接口。其內部使用數據調度緩存、多級空間索引查詢等手段實現對矢量數據的高效存儲與訪問。

2 矢量數據組織模型及多級空間索引設計

2.1 分布式存儲組織模型

傳統(tǒng)的矢量數據模型，采用將矢量圖層和地理目標進行集中組織存儲，如果一個圖層的地理目標眾多，會帶來數據訪問慢、空間索引維護困難、建立空間索引耗費時間長等一系列問題，很難支持多尺度數據的快速獲取、網絡環(huán)境下的“漸進式”傳輸以及地理信息客戶端的“自適應”動態(tài)可視化等應用。

結合分布式空間數據庫系統(tǒng)架構下的矢量數據的使用特點，面向矢量數據并行入庫、高效訪問的應用需求，采用關系數據庫和分布式半結構化數據庫相結合的技術思路，提出了一種適應分布式環(huán)境下的分層+分塊的矢量數據存儲組織模型，具體結構如圖2所示。

該矢量數據存儲組織模型從結構上由存儲層、調度層和應用層組成：

1)存儲層。描述了矢量數據的物理存儲環(huán)境，即將矢量數據通過網格剖分生成的所有矢量數據面片以小文件的形式存儲于分布式存儲環(huán)境下的各個數據節(jié)點上，實現了對海量矢量數據的分布式存儲需求；

2)調度層。描述進行矢量數據訪問時，矢量數據從存儲層調度的方式。即根據調度條件(如空間范圍)，首先確定當前調度的矢量數據所在的矢量面片文件并從存儲層讀取，然后根據矢量面片文件中的矢量數據層索引信息，快速獲取需要訪問的矢量數據層，并根據矢量數據層中的空間索引信息，計算符合條件的矢量數據標識和對應的矢量數據塊，最后根據數據塊內索引獲取所有的矢量數據，構成目標集并緩沖到內存，為應用層訪問做好數據準備。通過數據調度緩存、多級空間索引查詢，調度層極大地提高矢量數據的訪問效率；

3)應用層。提供面向用戶的矢量數據的存儲訪問方式。當調度層完成矢量數據的調度后，會將符合調度條件的數據以目標集的形式分批加載到應用層。

通過分布式空間數據庫系統(tǒng)架構下矢量數據的存儲組織模型設計，解決了海量矢量數據并行入庫和高效訪問的應用需求。針對海量矢量數據并行入庫應用需求，將海量矢量數據依據網格部分規(guī)則(如：Google剖分等)將海量矢量數據根據空間范圍劃分若干個矢量數據網格，而一個矢量數據網絡對應一個物理上的矢量數據面片文件，每個矢量數據面片文件中包括某個空間范圍內的所有矢量數據層的矢量數據。通過這種剖分規(guī)則將海量矢量數據化整為零，以矢量面片文件的形式存儲在分布式數據庫的各個數據節(jié)點上，以實現多客戶端并行存儲。通過分布式技術解決了海量矢量數據的存儲以及高并發(fā)訪問的問題，但是其對單用戶的矢量數據訪問效率并未有幫助，甚至會降低訪問效率，為此本文設計了一種多級空間索引機制，以提高矢量數據的單次訪問效率。

圖2 矢量數據存儲組織模型

2.2 多級空間索引

根據矢量數據的分布式存儲組織模型，矢量數據是以矢量數據面片的形式組織存儲的，矢量數據面片是矢量數據物理調度的最小單元，為了提高矢量面片的訪問效率，設計以矢量數據面片對應的矢量網格行列號作為其文件名，當進行空間范圍查詢時，可以快速計算該范圍覆蓋的行列號集，從而快速定位符合條件的矢量面片文件。而在矢量數據面片內部通過矢量數據層索引、矢量數據塊索引以及數據塊內索引等多級索引提高矢量數據的命中率，極大地提高矢量數據的單次訪問效率。其結構如圖3所示。

圖3 矢量數據面片結構

由矢量數據面片結構圖可以看出，矢量數據面片由矢量數據層索引信息和若干矢量數據層組成，其中在每個矢量數據層又由空間索引節(jié)點信息、矢量數據塊信息等構成；

矢量數據層索引信息記錄了該矢量數據面片包含的每個矢量數據層的名稱，以及在矢量數據面片內的存儲位置等信息；

空間索引節(jié)點信息是用于描述創(chuàng)建空間索引時生成的所有空間索引節(jié)點，一個空間索引節(jié)點包括節(jié)點信息(節(jié)點Code、級別等)、包含的矢量目標個數、每個矢量目標的標識、范圍、幾何類型、分級編碼等信息。一個矢量數據桶里包括1～N個空間索引節(jié)點；

矢量數據塊和空間索引節(jié)點一一對應，空間索引節(jié)點中只包含矢量目標的標識、幾何類型等信息，而矢量數據塊將一個空間索引節(jié)點覆蓋的相鄰矢量目標數據以數據塊的形式打包，主要包括矢量目標塊內索引信息、包含的矢量目標個數、每個矢量目標幾何信息、拓撲信息、屬性信息等。

2.2.1 矢量數據層索引

矢量數據層索引信息記錄了該矢量數據面片包含的每個矢量數據層在矢量數據面片內部的存儲偏移量，當需要訪問該矢量面片中某個矢量數據層時，可以通過該索引信息快速定位矢量數據層在矢量數據面片內的存儲位置，實現了矢量數據層隨機訪問的能力。

2.2.2 矢量數據空間索引

矢量數據空間索引是在HHCode(Helical Hyper-spatial Code)的索引機制的基礎上進行了改造，即將HHCODE空間索引數據塊化。每個HHCODE空間索引對應一定空間范圍內的目標集合，并將跨HHCODE空間索引的目標進行升級，提升至上一級HHCODE空間索引節(jié)點，構建空間索引節(jié)點樹，實現矢量數據按塊查詢調度，以滿足對矢量數據的高效空間查詢需求。

HHCode(Helical Hyper-spatial Code)是目前國際上空間數據索引采用的主要技術之一。 它是由CHS(Canadian Hydrographic Service)于1990年開發(fā)的將多維數據轉換為一個整數值的一種編碼技術。

一維HHCode是對一維矢量數據進行二分形成的二進制編碼，m維HHCode是對m維矢量進行二分形成的二進制編碼。以二維地圖為例，HHCode編碼方法如下：

首先，對二維地圖所在的地圖范圍進行逐級四分，每次劃分用2個1比特標識所選區(qū)域，分別標識北/南、西/東方向。這樣，經過n級劃分就得到2個n比特串，從高位到低位依次代表從小到大的級別。然后，將這兩個位串按位交叉存儲成一個2n比特的值，所得的二進制編碼即為區(qū)域的n級HHcode編碼值。設1標識北和東，0標識南和西，2維空間的2級與3級HHCode的編碼如圖4所示。

圖4 二維空間的HHCode編碼

基于HHCode編碼技術的空間索引本文用HHCODE索引表示。地理目標的HHCODE索引由它所在區(qū)域的HHCode編碼表示，索引值為HHCode編碼值，索引級別為HHCode編碼的級別，一個完整的HHCODE索引表示為<值，級>()。例如，對于圖5中的點P，經過4級遞歸劃分后，其北/南方向上的二進制位串位為0011，東/西方向上的二進制位串位為1001，將兩個位串交叉存儲后得到點P的HHCODE索引的值為01001011，HHCODE索引的級為4，點P的完整的HHCODE索引為<01001011，4>。

圖5 地理目標的HHCODE索引

對于線目標和面目標，由于它們都具有大小，所以可能需要不同劃分級別上的多個HHCODE索引才能完整的覆蓋整個目標。例如，在圖5中，面B的索引為<101100,3>，面A的完整的索引如下：

<100010,3>、<100011,3>、<100111010,4>、<100111011,4>、<101000,3>、<101001,3>、<101011,3>、<10101001,4>、<101100,3>、<101110,3>、<10110100,4>、<10110110,4>、<10111000,4>。

一個HHCODE索引對應整個空間范圍中的一個空間區(qū)域，通過HHCODE索引可以檢索到這個空間區(qū)域，稱這個空間區(qū)域為相應的HHCODE的索引區(qū)域。盡管HHCODE僅以一對整數值定位空間區(qū)域，但它卻包含了豐富的空間關系信息，具體表現：

1)HHCODE索引能夠體現空間數據之間的相等關系。如果的索引區(qū)域與的索引區(qū)域相同，則level 1 = level 2，且code 1 = code 2；

2)HHCODE索引能夠體現空間數據之間的包含關系。如果的索引區(qū)域包含的索引區(qū)域，則level 1 ≤ level 2，且code 2由高到低第1位到第2level 1位與code 1相等；

3)HHCODE索引能夠體現空間數據之間的相交關系。如果的索引區(qū)域與的索引區(qū)域相交，兩個索引的索引區(qū)域相等或具有包含關系。

由于HHCODE本身包含豐富的空間關系信息，因此，利用HHCODE索引可以快速判斷符合某一個范圍的所有HHCODE索引區(qū)域，而每個HHCODE索引區(qū)域都對應一個以HHCODE索引的level和code唯一標識的空間索引節(jié)點，空間索引節(jié)點里記錄了對應的HHCODE索引范圍內所有矢量目標的標識、范圍、主屬性等信息，當進行空間條件查詢時，根據空間范圍條件可以快速計算出其覆蓋所有HHCODE索引范圍，進而獲取到對應的所有空間索引節(jié)點和矢量數據塊，然后從這些空間索引節(jié)點中提取符合條件的矢量目標標識，根據矢量目標標識和矢量數據塊內索引快速從矢量數據塊中提取矢量目標數據，通過這種方式極大地提高矢量數據的訪問效率。

2.2.3 矢量數據塊內索引

矢量數據塊內索引記錄了該塊內每個矢量目標在矢量數據塊內的存儲位置，其由矢量目標標識和矢量目標在塊內的偏移量構成，通過需要獲取的矢量目標標識，獲取該矢量目標在矢量數據塊內的偏移量，達到矢量目標快速加載、隨機訪問的目的。

3 實驗與分析

3.1 實驗環(huán)境和實驗數據

本文在實驗環(huán)境中對提出的矢量數據存儲組織模型和多級空間索引進行了實驗驗證，實驗硬件環(huán)境包括43臺存儲服務器用于部署分布式文件系統(tǒng)和分布式數據庫，6臺存儲服務器用于部署關系數據庫，25臺客戶端機器用于部署待入庫數據和并行入庫、并發(fā)訪問程序；實驗軟件環(huán)境包括改進后的分布式文件系統(tǒng)HDFS、分布式數據庫HBase、達夢關系數據庫(DM7 MPP版本)和并行入庫、并發(fā)訪問實驗軟件。實驗數據包括多比例尺、多源矢量數據300 GB。

3.2 實驗案例和結果分析

3.2.1 數據入庫和多級索引建立

將試驗數據分攤部署在并行客戶端機器上，啟動并行入庫程序，表1為分布式矢量數據入庫和傳統(tǒng)數據庫管理系統(tǒng)入庫效率對比實驗結果。

表1 分布式矢量數據入庫和傳統(tǒng)數據庫管理系統(tǒng)入庫效率比較

實驗結果分析：

1)通過分布式矢量數據入庫、多級索引創(chuàng)建實驗結果可以看出，隨著數據量的增長，在客戶端數量不變的情況下，入庫時間呈線性增長趨勢，單臺客戶端入庫速度保持穩(wěn)定。

2)通過傳統(tǒng)數據庫管理系統(tǒng)入庫、索引創(chuàng)建實驗結果可以看出，隨著數據量的增長，在客戶端數量不變的情況下，入庫時間呈線性增長趨勢,單臺客戶端入庫速度略有下降。

3)通過對兩者實驗結果相比較可以看出，通過分布式矢量數據入庫，雖然矢量數據平均入庫效率沒有提升，反而下降，但總體矢量數據裝載時間大大縮短，且可管理數據量大大提升。

3.2.2 數據并發(fā)訪問效率

在25臺客戶端部署并發(fā)訪問程序，每臺客戶端上分別模擬若干個并發(fā)訪問用戶，并為每個測試執(zhí)行者分配參數文件序號，執(zhí)行并發(fā)訪問5 min，記錄每個并發(fā)訪問用戶5 min內向系統(tǒng)發(fā)送請求的個數、系統(tǒng)成功處理請求的個數、系統(tǒng)處理請求成功率，以及成功處理請求的最小、最大、平均響應速度。表2為矢量數據并發(fā)訪問測試記錄表。

實驗結果分析：

1)通過分布式矢量數據訪問實驗結果可以看出，隨著并發(fā)訪問量的增加，5 min訪問時間內系統(tǒng)處理請求成功率沒有發(fā)生明顯變化，矢量數據并發(fā)訪問成功率都達到99%以上；但是矢量數據并發(fā)訪問單位時間內獲取的要素個數卻呈逐步下降的趨勢，這與矢量數據的屬性數據需要使用關系數據庫進行管理有關，當訪問量增加時，關系數據庫的響應效率將有所下降。

表2 矢量數據并發(fā)訪問測試記錄表

2)通過基于傳統(tǒng)數據庫的矢量數據訪問實驗結果可以看出，隨著并發(fā)訪問量的增加，5 min訪問時間內系統(tǒng)處理請求成功率呈現下降趨勢，而且在矢量數據并發(fā)訪問單位時間內獲取的要素個數呈現逐步下降趨勢，說明傳統(tǒng)數據庫在并發(fā)訪問量增大的情況下，其處理能力在逐漸下降。

4 結束語

空間索引是海量空間數據的高效組織與管理的關鍵問題，本文在分布式空間數據庫系統(tǒng)架構基礎上，結合矢量數據的使用特點和應用需求，采用關系數據庫和分布式半結構化數據庫相結合的技術思路，提出了一種適應分布式環(huán)境下的分層+分塊的矢量數據存儲組織模型，在此基礎上設計了包括矢量數據面片索引、矢量數據層索引、矢量數據塊索引以及數據塊內索引在內的多級空間索引，并針對數據存儲、索引構建、查詢訪問進行了相關實驗。實現表明，本文設計的空間索引支持并發(fā)創(chuàng)建和高并發(fā)條件下的數據高效訪問。在多級索引中矢量數據分片、矢量數據空間索引數據塊化改造等方面還需進一步深入研究、優(yōu)化參數，以期進一步提高數據管理效率。

[1] 何珍文,鄭祖芳,劉剛,等.動態(tài)廣義表空間索引方法[J]. 地理與地理信息科學,2011,27(5):9-15.

[2] 周勇. 改進的層次網格空間索引技術研究與實現[D]. 福州：福州大學,2004.

[3] 蓋森,張心悅,喻峰,等.多尺度位置鍵空間索引方法[J]. 測繪科學,2015,40(8):147-151.

[4] 龔俊,朱慶,張葉廷,等.顧及多細節(jié)層次的三維R 樹索引擴展方法[J].測繪學報,2011,40(2):249-255.

[5] 孫朝犇,馬學民,路軒軒,等. ArcSDE在基礎地理信息數據庫更新中的應用[J].測繪與空間地理信息,2016,39(1):79-81.

[6] 李德元,姚文龍,楊二龍,等. 基于ArcSDE文件地理數據庫存儲和設計的應用研究[J].測繪與空間地理信息,2016,39(1):82-84.

[7] 付仲良,劉思遠.MR-tree空間索引的Voronoi圖改進及其并行空間查詢方法[J]. 武漢大學學報(信息科學版),2012,37(12):1490-1494.

[8] 趙園春,李成名,趙春宇.基于R 樹的分布式并行空間索引機制研究[J]. 地理與地理信息科學,2007,23(6):38-81.

[9] 付仲,劉思遠,田宗舜,等.基于多級R-tree的分布式空間索引及其查詢驗證方法研究[J]. 測繪通報,2012 (12):42-46.

[10] 鄭祖芳.分布式并行時空索引技術研究[D]. 武漢：中國地質大學,2014

[11] 涂振發(fā).云計算環(huán)境下海量空間數據高效存儲關鍵技術研究[D]. 武漢：武漢大學,2012.

[12] 楊文奇,劉 杰,陳飛輪.基于MapReduce 的并行VoR-Tree 索引[J].地理空間信息,2013,11(6):109-111.

[13] 趙敏超,杜震洪,張豐,等.基于MapReduce和雙層倒排網格索引的KNN算法[J].浙江大學學報(理學版),2014,41(6):703-708.

[14] 陳飛輪.基于MapReduce的VoR_Tree索引并行構建技術研究[D].江西贛州：江西理工大學,2012.

[責任編輯：李銘娜]

Research on multilevel spatial index method of vector data in the distributed spatial database

XU Daozhu1,2,3,JIAO Yangyang2,3，JIN Cheng1,2,3

(1.School of Surveying and Mapping, Information Engineering University, Zhengzhou 450052, China;2.State Key Laboratory of Geo-information Engineering, Xi’an 710054, China;3.Xi’an Station of Surveying and Mapping, Xi’an 710054, China)

Distributed computing and cloud computing technology have been applied to the field of geographic information, offering a variety of data and function services based on the efficient organization and management of massive spatial data. Spatial index is the key problem. Based on distributed spatial database system architecture, the paper proposes a layered and blocked vector data storage organization model which adapts to the distributed environment, along with a multilevel spatial index that included patch index, layer index, block index and inside block index of the vector data. The experiments illustrate that the model designed in the paper supports the concurrent create spatial index and efficient data access under the condition of high concurrency.

distributed; spatial database; multilevel index; vector data；HHCode index

著錄：徐道柱,焦洋洋,金澄.分布式空間數據庫中矢量數據多級空間索引方法研究[J].測繪工程，2017，26(10)：1-6.

10.19349/j.cnki.issn1006-7949.2017.10.001

2016-07-18

國家自然科學基金資助項目(41201469)

徐道柱(1982-),男,助理研究員,博士研究生.

TP391

A

1006-7949(2017)10-0001-06