基于NoSQL的分布式R*樹索引構(gòu)建與應(yīng)用研究

孫 樂 樂，金 寶 軒

(1.云南師范大學地理學部，云南 昆明 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ù)庫在異構(gòu)數(shù)據(jù)存儲、擴展性、高并發(fā)響應(yīng)等方面的劣勢不斷凸顯[4,5]，以NoSQL存儲、管理空間數(shù)據(jù)并支撐空間查詢、應(yīng)用成為研究熱點[6-8]。然而，由于存儲模型的差異，NoSQL的空間索引機制與傳統(tǒng)RDB空間索引不同，設(shè)計與構(gòu)建高效的NoSQL空間索引是擴展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 等。索引機制上，SFC(Space-Filling Curve)類索引是應(yīng)用最廣泛的NoSQL空間索引，其以Hilbert、Z-Curve等曲線將多維空間對象映射、編碼到一維空間，實現(xiàn)NoSQL索引存儲[3,9,10]，其中，GeoMesa[10]以顯著的查詢性能和豐富的支持功能被廣泛應(yīng)用在京東物流[3]、阿里云(Ganos)、滴滴出行[2]等平臺，支撐上億量級的空間大數(shù)據(jù)查詢、分析服務(wù)。但SFC屬于space-specific索引[10]，組織的是空間區(qū)域而非數(shù)據(jù)，適用于點數(shù)據(jù)，對線、多邊形等復(fù)雜幾何的索引性能有限，且易產(chǎn)生跨區(qū)域?qū)ο蠓峙鋯栴}[3,11]，往往通過重復(fù)存儲或擴張區(qū)域緩解[11]，影響索引性能；另一方面，NoSQL SFC類索引本質(zhì)上是一種Geohash編碼，多被存儲于磁盤，查詢時需進行數(shù)據(jù)表范圍掃描，查詢范圍較大時，計算查詢對應(yīng)的字典序范圍(lexicographic range)成本較高[10]，制約其擴展性。

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

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

1 理論基礎(chǔ)

1.1 R*樹索引

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

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

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

1.3 空間索引耗時模型

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

(1)

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

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

2 分布式R*樹索引機制

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

圖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*樹深度，提高并行加載、查詢的均衡性，采用改進后的STR(Sort Tile Recursive)[20]進行劃分。STR是一種簡單的空間數(shù)據(jù)打包算法，劃分原理見圖2a，其遞歸性地按各坐標軸對空間對象重心進行排序、均等劃分，能同時保證區(qū)塊間條目數(shù)平衡與較小的空間重疊。然而，當數(shù)據(jù)整體MBR的長寬比α較大時，STR劃分后的區(qū)塊數(shù)據(jù)更易呈長條形而非正方形，違反了R*樹的邊界周長最小化原則[12]。同時，STR固定的空間編碼方向會導(dǎo)致類似morton曲線的區(qū)域跳躍問題，使順序編碼的分區(qū)在空間位置上不鄰近，如圖2a中的Part 2到Part 3；還會增大過濾數(shù)據(jù)體量，如圖2a中灰色矩形僅與Part 2、Part 4相交，進行范圍掃描時，需過濾并不相交的Part 3。因此，本研究對STR的切分與編碼策略進行優(yōu)化。假設(shè)要為N個二維空間對象構(gòu)建p(式(2))個容量為C的R*樹，X、Y軸上的切分數(shù)分別為Sx、Sy(式(3))，劃分數(shù)據(jù)時，優(yōu)先按照空間跨度更大的方向劃分，即Sx、Sy較大值對應(yīng)的坐標軸，以S形曲線對各分區(qū)進行編碼。以圖2b為例，先按Y軸劃分，yi切片內(nèi)分區(qū)編號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個編碼為Hcodei的區(qū)塊，每個區(qū)塊包括空間矢量數(shù)據(jù)集Fi。借助并行計算，在每個分區(qū)內(nèi)實例化R*樹對象ri，遍歷分區(qū)元素，插入構(gòu)建R*樹，并獲取R*樹的根節(jié)點mi。將這些數(shù)據(jù)對象轉(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ù)空間范圍，用于過濾分區(qū)。

(5)

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

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

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

算法1 空間查詢處理

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

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

輸入：空間查詢請求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 實驗與結(jié)果分析

3.1 實驗設(shè)計與數(shù)據(jù)

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

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

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

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

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

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

3.3 空間查詢性能分析

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

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

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

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

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

3.3.2 最鄰近查詢性能分析 用D3、D4數(shù)據(jù)集進行最鄰近查詢實驗，以101.419725°E,25.623202°N為中心點，選取不同的距離半徑(表5)，測試本文方法與GeoMesa進行10次查詢的T均值(圖7)。由圖7可知，本文方法的T均值為GeoMesa的52.3%，減少了96.89～8 795.13 ms，執(zhí)行7 700量級、77萬量級最鄰近查詢的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)時間對比Fig.7 Comparison of average response time of nearest neighbor query

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

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

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

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

4 結(jié)語

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