孫 樂 樂，金 寶 軒

(1.云南師范大學(xué)地理學(xué)部，云南 昆明 650500；2.云南省自然資源廳，云南 昆明 650224)

0 引言

隨著信息采集/傳輸技術(shù)的發(fā)展，空間數(shù)據(jù)精度與體量不斷提高，空間數(shù)據(jù)在物聯(lián)網(wǎng)[1]、位置服務(wù)(LBS)等領(lǐng)域廣泛應(yīng)用[2,3]，傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)在異構(gòu)數(shù)據(jù)存儲(chǔ)、擴(kuò)展性、高并發(fā)響應(yīng)等方面的劣勢(shì)不斷凸顯[4,5]，以NoSQL存儲(chǔ)、管理空間數(shù)據(jù)并支撐空間查詢、應(yīng)用成為研究熱點(diǎn)[6-8]。然而，由于存儲(chǔ)模型的差異，NoSQL的空間索引機(jī)制與傳統(tǒng)RDB空間索引不同，設(shè)計(jì)與構(gòu)建高效的NoSQL空間索引是擴(kuò)展NoSQL空間數(shù)據(jù)的關(guān)鍵。

NoSQL數(shù)據(jù)模型主要包括key-value、column-oriented、document、graph等，基于這些模型構(gòu)建的空間索引有MD-HBase[9]、GeoMesa[10]、JUST[3]、GS-Phenix[8]、MongoDB 2d與2dsphere、Neo4j Spatial 等。索引機(jī)制上，SFC(Space-Filling Curve)類索引是應(yīng)用最廣泛的NoSQL空間索引，其以Hilbert、Z-Curve等曲線將多維空間對(duì)象映射、編碼到一維空間，實(shí)現(xiàn)NoSQL索引存儲(chǔ)[3,9,10]，其中，GeoMesa[10]以顯著的查詢性能和豐富的支持功能被廣泛應(yīng)用在京東物流[3]、阿里云(Ganos)、滴滴出行[2]等平臺(tái)，支撐上億量級(jí)的空間大數(shù)據(jù)查詢、分析服務(wù)。但SFC屬于space-specific索引[10]，組織的是空間區(qū)域而非數(shù)據(jù)，適用于點(diǎn)數(shù)據(jù)，對(duì)線、多邊形等復(fù)雜幾何的索引性能有限，且易產(chǎn)生跨區(qū)域?qū)ο蠓峙鋯?wèn)題[3,11]，往往通過(guò)重復(fù)存儲(chǔ)或擴(kuò)張區(qū)域緩解[11]，影響索引性能；另一方面，NoSQL SFC類索引本質(zhì)上是一種Geohash編碼，多被存儲(chǔ)于磁盤，查詢時(shí)需進(jìn)行數(shù)據(jù)表范圍掃描，查詢范圍較大時(shí)，計(jì)算查詢對(duì)應(yīng)的字典序范圍(lexicographic range)成本較高[10]，制約其擴(kuò)展性。

R*樹[12]根據(jù)實(shí)際的空間分布層級(jí)劃分、組織空間區(qū)域，是一種內(nèi)存式、data-specific索引,也是R樹家族中最具查詢性能的索引之一[13，14]。R*樹基本元素為MBR(Minimum Bounding Rectangle)，理論上能索引一切以MBR表示的復(fù)雜幾何(如線、多線、多邊形等)，克服了SFC類索引的上述不足。樹結(jié)構(gòu)型空間索引會(huì)占據(jù)數(shù)據(jù)體量的15%或更高比例[15]，分布式R*樹結(jié)構(gòu)能控制索引體積，避免內(nèi)存溢出，可通過(guò)分區(qū)策略在并行環(huán)境中集成使用，分布式R*樹類索引被廣泛用于提高批處理空間運(yùn)算作業(yè)性能[16]，如SpatialHadoop[17]、GeoSpark[18]等空間處理框架的索引被保存在文件系統(tǒng)中，使用時(shí)通過(guò)并行計(jì)算框架加載、查詢。有研究提出混合模式的NoSQL空間索引方案，以存儲(chǔ)在HDFS或RDB中的外部R樹索引擴(kuò)展NoSQL支持空間操作[18,19]。然而，不同存儲(chǔ)介質(zhì)在安全、備份與并發(fā)訪問(wèn)等策略上的差異[11]會(huì)導(dǎo)致索引查詢、數(shù)據(jù)訪問(wèn)等操作復(fù)雜化，降低效率，同時(shí)會(huì)增加索引、數(shù)據(jù)一致性維護(hù)的成本。因此，要實(shí)現(xiàn)低延遲、高擴(kuò)展性的查詢性能，關(guān)鍵在于設(shè)計(jì)一個(gè)具有優(yōu)良查詢性能的索引機(jī)制以及與其相對(duì)應(yīng)的高性能查詢、應(yīng)用處理機(jī)制。

針對(duì)上述問(wèn)題，本文提出一種基于NoSQL的分布式R*樹內(nèi)存式空間索引。首先給出基于Apache Spark的索引并行構(gòu)建算法，以及基于NoSQL SSPT(Server-Side Scripts)計(jì)算框架的查詢/計(jì)算并行處理機(jī)制；然后以HBase為例，通過(guò)構(gòu)建性能、空間查詢性能、應(yīng)用性能三方面實(shí)驗(yàn)比較本文索引的優(yōu)越性；最后以自然資源開發(fā)項(xiàng)目合規(guī)性審查為應(yīng)用場(chǎng)景，驗(yàn)證索引的應(yīng)用表現(xiàn)，以期支撐常見的“查詢+統(tǒng)計(jì)”模式應(yīng)用。

1 理論基礎(chǔ)

1.1 R*樹索引

R*樹通過(guò)引入一系列針對(duì)區(qū)域、邊界形狀、節(jié)點(diǎn)間重疊等方面的措施，優(yōu)化數(shù)據(jù)插入、節(jié)點(diǎn)分裂邏輯，提出強(qiáng)制重插機(jī)制，使樹結(jié)構(gòu)更合理、效率更高[12]。R*樹的內(nèi)存持久化特性使其在檢索時(shí)無(wú)需訪問(wèn)實(shí)際數(shù)據(jù)對(duì)象，直接給出符合空間關(guān)系的對(duì)象列表，使響應(yīng)延遲更低。由于索引元素的形式固定，R*樹的體積與索引對(duì)象數(shù)量成正比，面對(duì)大體量數(shù)據(jù)，構(gòu)建單一集中式R*樹往往導(dǎo)致較大的樹深度與索引體積，索引加載、遍歷的內(nèi)存成本與時(shí)間成本較高。因此，本文采取數(shù)據(jù)劃分策略構(gòu)建分布式R*樹，同時(shí)控制索引體量。

1.2 NoSQL數(shù)據(jù)庫(kù)

NoSQL廣為認(rèn)可的定義是“Not Only SQL”，多為schema-less[4]或schema-free[5]模式，主要特性包括高讀/寫性能、大體量數(shù)據(jù)存儲(chǔ)、結(jié)構(gòu)松散、高擴(kuò)展性與低成本等[5]，與傳統(tǒng)RDB在ACID、事務(wù)、SQL支持等方面存在較大差異。由于存儲(chǔ)容量較大，為彌補(bǔ)客戶端API在結(jié)果解析、統(tǒng)計(jì)計(jì)算方面的性能劣勢(shì)，許多NoSQL數(shù)據(jù)庫(kù)提供了SSPT，如Apache Accumulo的Iterators、Apache HBase的Coprocessor、Aerospike的User-Defined Functions、CouchDB的View等。SSPT通過(guò)在數(shù)據(jù)端執(zhí)行計(jì)算以避免IO成本，并提供以分區(qū)為單位的并行計(jì)算模式，具有低延遲與性能擴(kuò)展優(yōu)勢(shì)。因此，本文基于SSPT設(shè)計(jì)分布式R*樹加載、查詢處理并行機(jī)制，提高索引性能。

1.3 空間索引耗時(shí)模型

一般應(yīng)用場(chǎng)景下，空間索引耗時(shí)T計(jì)算公式為：

(1)

式中：p為并行度，值為1時(shí)對(duì)應(yīng)集中式單機(jī)索引，值大于1時(shí)對(duì)應(yīng)分布式索引；i為任務(wù)編號(hào)，取值范圍為[0,p]；Li為索引載入和準(zhǔn)備耗時(shí)；Qi為索引檢索耗時(shí)；Ri為后續(xù)處理(結(jié)果傳輸、加工等)耗時(shí)。

索引體量決定加載、檢索成本。集中式索引結(jié)構(gòu)需單機(jī)集中存儲(chǔ)、加載使用[16]，在有限的內(nèi)存、計(jì)算資源下，當(dāng)索引對(duì)象數(shù)增加，L0、Q0、R0均增大，且存在查詢失敗、資源移出風(fēng)險(xiǎn)，同時(shí)，大數(shù)據(jù)體量會(huì)使索引結(jié)構(gòu)更復(fù)雜[15]。以R樹為例，樹的深度為logmN，m為節(jié)點(diǎn)元素?cái)?shù)，N為數(shù)據(jù)量，N越大樹結(jié)構(gòu)越深，產(chǎn)生的遍歷計(jì)算越多。整體上，單機(jī)索引擴(kuò)展性低，更適用于傳統(tǒng)集中式分析模式。分布式索引多采用分區(qū)策略,將數(shù)據(jù)劃分為中小體量、均勻的區(qū)塊序列[15，17]，各區(qū)塊存儲(chǔ)相鄰的空間對(duì)象集合并構(gòu)建本地索引，執(zhí)行時(shí)僅加載、查詢符合空間關(guān)系的區(qū)塊索引數(shù)據(jù)，若符合空間關(guān)系的區(qū)塊數(shù)大于1，則并行執(zhí)行。因此，在同種索引下，理論上分布式結(jié)構(gòu)索引的Li、Qi、Ri為集中式索引耗時(shí)L0、Q0、R0的1/p，實(shí)際應(yīng)用場(chǎng)景中，集群節(jié)點(diǎn)間性能不一致，或查詢結(jié)果不均勻，使耗時(shí)遵循“木桶效應(yīng)”，即整體耗時(shí)取決于最慢子任務(wù)耗時(shí)。因此，提高區(qū)塊間均衡性對(duì)于減少索引耗時(shí)及提高整體性能同樣重要。

2 分布式R*樹索引機(jī)制

分布式R*樹索引(圖1)包括兩層結(jié)構(gòu)：1)分區(qū)格網(wǎng)索引記錄各分區(qū)所含數(shù)據(jù)的空間范圍、數(shù)量等元數(shù)據(jù)，用于過(guò)濾分區(qū)；2)以分區(qū)為單位構(gòu)建、使用R*樹，用于檢索、過(guò)濾所在分區(qū)數(shù)據(jù)。每個(gè)分區(qū)配有一個(gè)基于Region Server提供的JVM (Java Virtual Machine)與線程池，用于索引實(shí)例化、查詢與應(yīng)用處理。查詢時(shí)，分區(qū)格網(wǎng)索引首先過(guò)濾掉不符合空間關(guān)系的分區(qū)，而后以分區(qū)為單位并行執(zhí)行查詢及應(yīng)用處理，返回結(jié)果，分區(qū)內(nèi)也支持多線程加速，以進(jìn)一步提高效率。

圖1 分布式R*樹索引結(jié)構(gòu)與核心組件Fig.1 Architecture and core components of the proposed distributed R*-tree index

2.1 分布式R*樹構(gòu)建

2.1.1 空間數(shù)據(jù)劃分 為控制R*樹深度，提高并行加載、查詢的均衡性，采用改進(jìn)后的STR(Sort Tile Recursive)[20]進(jìn)行劃分。STR是一種簡(jiǎn)單的空間數(shù)據(jù)打包算法，劃分原理見圖2a，其遞歸性地按各坐標(biāo)軸對(duì)空間對(duì)象重心進(jìn)行排序、均等劃分，能同時(shí)保證區(qū)塊間條目數(shù)平衡與較小的空間重疊。然而，當(dāng)數(shù)據(jù)整體MBR的長(zhǎng)寬比α較大時(shí)，STR劃分后的區(qū)塊數(shù)據(jù)更易呈長(zhǎng)條形而非正方形，違反了R*樹的邊界周長(zhǎng)最小化原則[12]。同時(shí)，STR固定的空間編碼方向會(huì)導(dǎo)致類似morton曲線的區(qū)域跳躍問(wèn)題，使順序編碼的分區(qū)在空間位置上不鄰近，如圖2a中的Part 2到Part 3；還會(huì)增大過(guò)濾數(shù)據(jù)體量，如圖2a中灰色矩形僅與Part 2、Part 4相交，進(jìn)行范圍掃描時(shí)，需過(guò)濾并不相交的Part 3。因此，本研究對(duì)STR的切分與編碼策略進(jìn)行優(yōu)化。假設(shè)要為N個(gè)二維空間對(duì)象構(gòu)建p(式(2))個(gè)容量為C的R*樹，X、Y軸上的切分?jǐn)?shù)分別為Sx、Sy(式(3))，劃分?jǐn)?shù)據(jù)時(shí)，優(yōu)先按照空間跨度更大的方向劃分，即Sx、Sy較大值對(duì)應(yīng)的坐標(biāo)軸，以S形曲線對(duì)各分區(qū)進(jìn)行編碼。以圖2b為例，先按Y軸劃分，yi切片內(nèi)分區(qū)編號(hào)Hcodei(式(4))范圍為(1+(yi-1)Sx,yiSx)，編碼方向根據(jù)yi的奇偶性確定。

圖2 STR數(shù)據(jù)均衡劃分策略Fig.2 Data balancing and partitioning strategy of STR

(2)

(3)

(4)

2.1.2 索引并行構(gòu)建 劃分后得到p個(gè)編碼為Hcodei的區(qū)塊，每個(gè)區(qū)塊包括空間矢量數(shù)據(jù)集Fi。借助并行計(jì)算，在每個(gè)分區(qū)內(nèi)實(shí)例化R*樹對(duì)象ri，遍歷分區(qū)元素，插入構(gòu)建R*樹，并獲取R*樹的根節(jié)點(diǎn)mi。將這些數(shù)據(jù)對(duì)象轉(zhuǎn)換為字節(jié)形式，以便后續(xù)導(dǎo)入NoSQL，得到劃分后的空間數(shù)據(jù)集M(式(5))。從M中抽取出Hcodei、mi(即分區(qū)格網(wǎng)索引),Hcodei記錄各分區(qū)數(shù)據(jù)的rowkey前綴與范圍，mi記錄各分區(qū)數(shù)據(jù)空間范圍，用于過(guò)濾分區(qū)。

(5)

2.1.3 存儲(chǔ)模式設(shè)計(jì) 1)存儲(chǔ)模型上，由于列(column)配置可變，HBase表僅需配置geo、prop兩個(gè)列族(column family)即可(表1)。rowkey為Hcodei_Ocodei,j形式，長(zhǎng)度固定，Hcodei長(zhǎng)度為3，Ocodei,j是指存儲(chǔ)對(duì)象在當(dāng)前i分區(qū)的編碼，數(shù)值形式為字符串，長(zhǎng)度為全局ri的最大深度，不足則頭部補(bǔ)0。rowkey根據(jù)存儲(chǔ)內(nèi)容分為元數(shù)據(jù)row(Hcodei、Ocodei,j均為0)、分區(qū)元數(shù)據(jù)row(Ocodei,j為0)、數(shù)據(jù)row(Hcodei、Ocodei,j均大于0)。由于rowkey根據(jù)ASCII字典順序排序，配置數(shù)據(jù)表在Hcodei_0000處切分區(qū)塊，i∈[1，p-1]，保證相同Hcodei前綴的row分配到同一區(qū)塊內(nèi)。如表1的分片方案可配置為[001_0000,002_0000,…，Hcodep-1_0000]，因此，每個(gè)分區(qū)startkey的Ocodei,j數(shù)值固定為0。2)編碼存儲(chǔ)上，元數(shù)據(jù)row存儲(chǔ)分區(qū)格網(wǎng)索引與全局元數(shù)據(jù)，如表1中row 000_0000 以geo:Hcodei_0000列記錄各分區(qū)的空間范圍mi，以prop:size、prop:wkid列存儲(chǔ)數(shù)據(jù)整體條目數(shù)、坐標(biāo)系信息；分區(qū)元數(shù)據(jù)row存儲(chǔ)各分區(qū)的索引ri、空間范圍mi，保證索引本地化，如表1中row 001_0000以geo:rtree列存儲(chǔ)ri，以prop:extent列存儲(chǔ)當(dāng)前分區(qū)數(shù)據(jù)的空間范圍mi；數(shù)據(jù)row存儲(chǔ)空間數(shù)據(jù)集Fi，F(xiàn)i中每個(gè)元素存儲(chǔ)為一個(gè)row，為提高相鄰rowkey的空間鄰近性，本研究將空間對(duì)象從R*樹根節(jié)點(diǎn)到葉節(jié)點(diǎn)的編碼拼接為一維序列，構(gòu)成rowkey中Ocodei,j編碼部分，對(duì)應(yīng)其在ri中的索引路徑，如圖3中9號(hào)元素的Ocodei,j為021。

表1 HBase分布式R*樹與空間數(shù)據(jù)存儲(chǔ)模型示例Table 1 Instances of distributed R*-tree and spatial data storage model of HBase

圖3 對(duì)象的R*樹路徑映射為一維rowkey空間編碼示意Fig.3 Mapping spatial object′s route path in R*-tree to one-dimensional spatial encoded rowkey

2.2 查詢并行處理

空間查詢可描述為從原始空間數(shù)據(jù)集中獲取符合給定空間關(guān)系要素的過(guò)程。分布式R*樹、數(shù)據(jù)編碼存儲(chǔ)模式已實(shí)現(xiàn)索引和數(shù)據(jù)的本地化，因此，可結(jié)合HBase的SSPT機(jī)制EndPoint Coprocessor開發(fā)并行運(yùn)行于服務(wù)端的查詢處理服務(wù)接口，處理空間查詢。本文空間查詢處理(算法1)首先通過(guò)全局分區(qū)格網(wǎng)索引獲取符合空間關(guān)系的Hcodei集合：S={Hcodei,…,Hcodet}(i∈[1,p])，然后將查詢請(qǐng)求q廣播到S對(duì)應(yīng)的區(qū)塊內(nèi)并進(jìn)行R*樹查詢，獲取索引對(duì)象的ID集合D，若D容量較大，則采用多線程進(jìn)行后續(xù)運(yùn)算，線程數(shù)為round(D.size()/l)，l為給定的單線程處理數(shù)閾值。由于D是查詢R*樹的結(jié)果，若要獲取經(jīng)過(guò)實(shí)際數(shù)據(jù)幾何空間關(guān)系檢驗(yàn)的結(jié)果，還需執(zhí)行算法2，遍歷D獲取實(shí)際數(shù)據(jù)，執(zhí)行幾何空間關(guān)系檢驗(yàn)，對(duì)過(guò)濾后的結(jié)果進(jìn)行加工、輸出。

算法1 空間查詢處理

輸入：空間查詢請(qǐng)求q

輸出：查詢結(jié)果R

S=queryRegionRowkeyList(q);

foreachregion inSdo

load R*-tree instance

D=queryRegionR*-tree(q);

if(D.size()>l){

threadPool = init(D.size(),l);

threadPool.run(geoCheckandProcess(D,q,R));

}else{

geoCheckandProcess (D,q,R);

}

算法2 查詢處理函數(shù)geoCheckandProcess

輸入：空間查詢請(qǐng)求q，ID集合D

輸出：查詢結(jié)果R

foreachID in Ddo

if(isIntersecting(getGeo(ID),q.geo())){

r=formatResult(getData(ID));

appendResults(R,r)

}

returnR;

2.3 應(yīng)用并行處理

應(yīng)用并行處理與查詢并行處理機(jī)制相似，理論上無(wú)需區(qū)塊間通信的計(jì)算都可通過(guò)SSPT實(shí)現(xiàn)。HBase官方指出，Coprocessor能執(zhí)行不復(fù)雜的映射、統(tǒng)計(jì)、聚合等計(jì)算，因此，可通過(guò)擴(kuò)展服務(wù)接口實(shí)現(xiàn)基于數(shù)據(jù)端的應(yīng)用并行處理。以自然資源開發(fā)項(xiàng)目合規(guī)性審查為例，只需在原有EndPoint類中新定義一個(gè)服務(wù)接口，處理邏輯與算法1整體一致，不同之處在于將算法2替換為合規(guī)性處理函數(shù)(算法3)。算法3可計(jì)算輸入圖斑與審查圖層幾何的相交情況，以及相交部分的橢球、平面面積并輸出。

算法3 合規(guī)性處理函數(shù)spCompProcess

輸入：空間查詢請(qǐng)求q，ID集合D

輸出：查詢結(jié)果R

foreachID inDdo

if(isIntersecting(getGeo(ID),q.geo())){

geo=getIntersection(q.geo(),getGeo(ID));

compute geodesic/planar area;

transform CRS and get the other area;

r=formatResult(getData(ID).prop,geo,area_geodesic,area_planar);

appendResults(R,r)

}

returnR;

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)與數(shù)據(jù)

利用具有代表性的NoSQL/SQL空間查詢和GeoMesa、ArcGIS分析工具，選取自然資源管理部門真實(shí)數(shù)據(jù)(表2)，通過(guò)構(gòu)建性能、空間查詢性能與應(yīng)用性能三方面實(shí)驗(yàn)，對(duì)比驗(yàn)證本文索引的性能。

表2 實(shí)驗(yàn)數(shù)據(jù)集信息Table 2 Information of experimental datasets

實(shí)驗(yàn)的單機(jī)配置為Intel Xeon E3-1230 v5處理器，16 G內(nèi)存，Windows 10專業(yè)版操作系統(tǒng)；HBase集群包括3個(gè)HMaster、4個(gè)RegionServer，RegionServer有24個(gè)Vcores、80 G內(nèi)存，HBase版本為cdh5.13.3-1.2.0，GeoMesa版本為1.3.5；ArcSDE數(shù)據(jù)庫(kù)服務(wù)器為Oracle 12c，128 G內(nèi)存。集群內(nèi)節(jié)點(diǎn)間通過(guò)萬(wàn)兆交換機(jī)連接，客戶端與集群環(huán)境間的網(wǎng)絡(luò)傳輸速率為100 Mbps。

3.2 構(gòu)建性能分析

在D4數(shù)據(jù)集中隨機(jī)抽取1萬(wàn)～500萬(wàn)條數(shù)據(jù)構(gòu)建索引，記錄本文方法與GeoMesa的執(zhí)行耗時(shí)(圖4)。由圖4可知，本文索引構(gòu)建的平均耗時(shí)僅為GeoMesa的30.0%，當(dāng)數(shù)據(jù)集較小時(shí)(1萬(wàn)、10萬(wàn))，GeoMesa構(gòu)建耗時(shí)表現(xiàn)略優(yōu)，但當(dāng)數(shù)據(jù)量達(dá)50萬(wàn)后，本文方法更具優(yōu)勢(shì)，如500萬(wàn)量級(jí)下耗時(shí)僅為GeoMesa的18.6%。這說(shuō)明GeoMesa采用基于協(xié)處理器的索引構(gòu)建方法[10]，擴(kuò)展性低于本文的批處理并行構(gòu)建模式，同時(shí)，本文的數(shù)據(jù)劃分策略優(yōu)化了分布式R*樹間體積的均衡性，緩解了數(shù)據(jù)傾斜問(wèn)題，進(jìn)一步提高了R*樹的并行構(gòu)建效率。本文索引機(jī)制下，執(zhí)行500萬(wàn)條多邊形空間數(shù)據(jù)索引構(gòu)建、NoSQL導(dǎo)入的總耗時(shí)在2 min內(nèi)，能滿足一般應(yīng)用場(chǎng)景的需求。

圖4 索引構(gòu)建執(zhí)行耗時(shí)對(duì)比Fig.4 Comparison of execution time for constructing index

3.3 空間查詢性能分析

3.3.1 范圍查詢性能分析 范圍查詢包括MBR查詢與多邊形幾何查詢：前者以MBR為輸入，僅以MBR間的空間關(guān)系過(guò)濾數(shù)據(jù)；后者以不規(guī)則多邊形為輸入，進(jìn)行幾何間空間關(guān)系檢查。實(shí)驗(yàn)以D3、D4為目標(biāo)數(shù)據(jù)，查詢輸入MBR、多邊形幾何信息見表3、表4，查詢僅返回ID序列，以不同輸入信息下兩種方法的平均查詢響應(yīng)時(shí)間T作為性能評(píng)價(jià)指標(biāo)。

表3 查詢輸入的MBR信息Table 3 Information of input MBRs

表4 查詢輸入的多邊形信息Table 4 Information of input polygons

(1)MBR查詢。如圖5所示，本文索引的MBR查詢性能顯著優(yōu)于GeoMesa，平均T值為后者的26.5%，說(shuō)明SFC類索引固定的空間劃分、組織模式，面對(duì)復(fù)雜多邊形時(shí)，負(fù)擔(dān)的遍歷、檢索成本更高。本文索引充分利用R*樹的查詢優(yōu)勢(shì)，更多考慮空間對(duì)象的分布特征，檢索時(shí)能快速定位目標(biāo)要素，查詢效率更高；其次，R*樹的內(nèi)存化特性使其在執(zhí)行MBR查詢時(shí)無(wú)需掃描數(shù)據(jù)row，進(jìn)一步控制了時(shí)間成本。性能擴(kuò)展方面，隨著查詢范圍擴(kuò)大，兩種方法的T值均有所增大，這是由于更多查詢結(jié)果增加了客戶端與服務(wù)器端的傳輸耗時(shí)，以M5查詢D4為例，返回結(jié)果的數(shù)據(jù)量約為23.32 MB，百兆網(wǎng)絡(luò)下傳回客戶端耗時(shí)接近2 s。由圖5可知，數(shù)據(jù)表范圍掃描的檢索方式使GeoMesa面對(duì)更大查詢范圍時(shí)，T值增幅更大；XZ-Ordering的區(qū)域擴(kuò)展策略產(chǎn)生了重疊、相交區(qū)域，增加了遍歷計(jì)算量。本文方法充分利用STR能兼顧數(shù)目均衡性與空間分布特征的優(yōu)勢(shì)，很好地控制了R*樹的深度與體積，減少了索引加載、查詢耗時(shí)，同時(shí)，R*樹間重疊面積較小，有效控制了查詢分區(qū)的數(shù)量。

圖5 MBR查詢平均響應(yīng)時(shí)間對(duì)比Fig.5 Comparison of average response time of MBR query

(2)多邊形幾何查詢。由于SFC類索引執(zhí)行兩種查詢時(shí)操作內(nèi)容相似，由圖6可知，相比MBR查詢，GeoMesa多邊形幾何查詢的T值增幅較小。本文方法則增加了數(shù)據(jù)獲取與幾何關(guān)系判斷計(jì)算，多邊形幾何查詢的T值增加了1.69～2 753.30 ms；同時(shí)，得益于R*樹索引的查詢性能優(yōu)勢(shì)，本文方法執(zhí)行81萬(wàn)量級(jí)查詢的T值仍控制在5 s內(nèi)，平均T值是GeoMesa的53.4%，性能優(yōu)勢(shì)依然突出。

圖6 多邊形幾何查詢平均響應(yīng)時(shí)間對(duì)比Fig.6 Comparison of average response time of polygon query

3.3.2 最鄰近查詢性能分析 用D3、D4數(shù)據(jù)集進(jìn)行最鄰近查詢實(shí)驗(yàn)，以101.419725°E,25.623202°N為中心點(diǎn)，選取不同的距離半徑(表5)，測(cè)試本文方法與GeoMesa進(jìn)行10次查詢的T均值(圖7)。由圖7可知，本文方法的T均值為GeoMesa的52.3%，減少了96.89～8 795.13 ms，執(zhí)行7 700量級(jí)、77萬(wàn)量級(jí)最鄰近查詢的T值分別為0.25 s、4.44 s，能保證大范圍最鄰近查詢的低延遲響應(yīng)，可較好地支撐應(yīng)用。

表5 最鄰近查詢輸入的半徑信息Table 5 Information of input query radii for nearest neighbor query

圖7 最鄰近查詢平均響應(yīng)時(shí)間對(duì)比Fig.7 Comparison of average response time of nearest neighbor query

3.4 應(yīng)用性能分析

合規(guī)性分析是指在土地、礦產(chǎn)建設(shè)開發(fā)等審批階段分析自然資源開發(fā)、建設(shè)項(xiàng)目在空間上的規(guī)劃合理性，避免破壞耕地、自然保護(hù)區(qū)等限制及禁止開發(fā)規(guī)劃區(qū)域，通常包括空間查詢、疊加運(yùn)算、結(jié)果加工等步驟。本研究以自然資源開發(fā)項(xiàng)目合規(guī)性分析為應(yīng)用場(chǎng)景，通過(guò)查詢、疊加計(jì)算獲取審查項(xiàng)目(表6)與各類審查數(shù)據(jù)的壓占關(guān)系，進(jìn)行結(jié)果加工及壓占面積、數(shù)量指標(biāo)計(jì)算，生成審查結(jié)論，并將本文方法與ArcGIS、GeoMesa進(jìn)行對(duì)比。如圖8所示，基于NoSQL較好的擴(kuò)展性及SSPT并行計(jì)算的優(yōu)勢(shì)，本文方法和GeoMesa的效率顯著高于基于Oracle的ArcGIS，平均耗時(shí)分別為ArcGIS的10.6%與14.53%。本文方法綜合應(yīng)用表現(xiàn)最優(yōu)，最大耗時(shí)不超36.2 s，低于GeoMesa的47.97 s，平均耗時(shí)為GeoMesa的72.7%，證明了分布式R*樹與應(yīng)用并行處理的優(yōu)越性，能支撐常見的“查詢+統(tǒng)計(jì)”類應(yīng)用。

表6 合規(guī)性審查輸入的圖斑信息Table 6 Information of input review polygons for the compliance review

圖8 各方法審查執(zhí)行耗時(shí)對(duì)比Fig.8 Comparison of execution time for compliance review using various methods

4 結(jié)語(yǔ)

空間索引是支撐空間查詢、分析應(yīng)用的基礎(chǔ)。本文提出一種基于NoSQL的分布式R*樹索引機(jī)制，該索引基于NoSQL的分區(qū)機(jī)制與優(yōu)化后的STR均衡策略，實(shí)現(xiàn)分布式索引結(jié)構(gòu)，以控制樹的深度、體積，憑借R*樹更優(yōu)良的空間組織結(jié)構(gòu)與內(nèi)存化特性，以及基于NoSQL的SSPT機(jī)制設(shè)計(jì)的查詢、應(yīng)用并行處理機(jī)制，實(shí)現(xiàn)查詢、應(yīng)用計(jì)算的高響應(yīng)與高性能擴(kuò)展。實(shí)驗(yàn)證明：本文索引在構(gòu)建性能、空間查詢性能、應(yīng)用性能方面優(yōu)越性顯著，能為基于NoSQL的大體量空間數(shù)據(jù)管理、分析應(yīng)用提供一種優(yōu)良解決方案。但本文索引的更新成本偏高，后續(xù)將研究提升索引更新性能與數(shù)據(jù)可視化。