基于NoSQL的分布式R*树索引构建与应用研究

孙 乐 乐，金 宝 轩

(1.云南师范大学地理学部，云南 昆明 650500；2.云南省自然资源厅，云南 昆明 650224)

0 引言

随着信息采集/传输技术的发展，空间数据精度与体量不断提高，空间数据在物联网[1]、位置服务(LBS)等领域广泛应用[2,3]，传统关系型数据库在异构数据存储、扩展性、高并发响应等方面的劣势不断凸显[4,5]，以NoSQL存储、管理空间数据并支撑空间查询、应用成为研究热点[6-8]。然而，由于存储模型的差异，NoSQL的空间索引机制与传统RDB空间索引不同，设计与构建高效的NoSQL空间索引是扩展NoSQL空间数据的关键。

NoSQL数据模型主要包括key-value、column-oriented、document、graph等，基于这些模型构建的空间索引有MD-HBase[9]、GeoMesa[10]、JUST[3]、GS-Phenix[8]、MongoDB 2d与2dsphere、Neo4j Spatial 等。索引机制上，SFC(Space-Filling Curve)类索引是应用最广泛的NoSQL空间索引，其以Hilbert、Z-Curve等曲线将多维空间对象映射、编码到一维空间，实现NoSQL索引存储[3,9,10]，其中，GeoMesa[10]以显著的查询性能和丰富的支持功能被广泛应用在京东物流[3]、阿里云(Ganos)、滴滴出行[2]等平台，支撑上亿量级的空间大数据查询、分析服务。但SFC属于space-specific索引[10]，组织的是空间区域而非数据，适用于点数据，对线、多边形等复杂几何的索引性能有限，且易产生跨区域对象分配问题[3,11]，往往通过重复存储或扩张区域缓解[11]，影响索引性能；另一方面，NoSQL SFC类索引本质上是一种Geohash编码，多被存储于磁盘，查询时需进行数据表范围扫描，查询范围较大时，计算查询对应的字典序范围(lexicographic range)成本较高[10]，制约其扩展性。

R*树[12]根据实际的空间分布层级划分、组织空间区域，是一种内存式、data-specific索引,也是R树家族中最具查询性能的索引之一[13，14]。R*树基本元素为MBR(Minimum Bounding Rectangle)，理论上能索引一切以MBR表示的复杂几何(如线、多线、多边形等)，克服了SFC类索引的上述不足。……