Mongodb Geo2d索引原理

ongoDB的geo索引是其一大特色,本文从原理层面讲述geo索引中的2d索引的实现。

2d 索引的创建与使用

通过 db.coll.createIndex({"lag":"2d"}, {"bits":int})) 来创建一个2d索引,索引的精度通过bits来指定,bits越大,索引的精度就越高。更大的bits带来的插入的overhead可以忽略不计。

通过

db.runCommand({ 
    geoNear: tableName, 
    maxDistance: 0.0001567855942887398, 
    distanceMultiplier: 6378137.0, 
    num: 30, 
    near: [ 113.8679388183982, 22.58905429302385 ], 
    spherical: true|false})

来查询一个索引,其中spherical:true|false 表示应该如何理解创建的2d索引,false表示将索引理解为平面2d索引,true表示将索引理解为球面经纬度索引。这一点比较有意思,一个2d索引可以表达两种含义,而不同的含义是在查询时被理解的,而不是在索引创建时。

2d索引的理论

Mongodb 使用一种叫做Geohash的技术来构建2d索引,但是Mongodb的Geohash并没有使用国际通用的每一层级32个grid的Geohash描述方式(见wiki geohash)。而是使用平面四叉树的形式。

如下图:

很显然的,一个2bits的精度能把平面分为4个grid,一个4bits的精度能把平面分为16个grid。2d索引的默认精度是长宽各为26,索引把地球分为(2^26)(2^26)块,每一块的边长估算为

2*PI*6371000/(1<<26) = 0.57 米

mongodb的官网上说的60cm的精度就是这么估算出来的:

By default, a 2d index on legacy coordinate pairs uses 26 bits of precision, which is roughly equivalent to 2 feet or 60 centimeters of precision using the default range of -180 to 180.

2d索引在Mongodb中的存储

上面我们讲到Mongodb使用平面四叉树的方式计算Geohash。事实上,平面四叉树仅存在于运算的过程中,在实际存储中并不会被使用到。

插入

对于一个经纬度坐标[x,y],MongoDb计算出该坐标在2d平面内的grid编号,该编号为是一个52bit的int64类型,该类型被用作btree的key,因此实际数据是按照 {GeoHashId->RecordValue}的方式被插入到btree中的。

查询

对于geo2D索引的查询,常用的有geoNeargeoWithin两种。geoNear查找距离某个点最近的N个点的坐标并返回,该需求可以说是构成了LBS服务的基础(陌陌,滴滴,摩拜), geoWithin是查询一个多边形内的所有点并返回。我们着重介绍使用最广泛的geoNear查询。

geoNear的查询过程

geoNear的查询语句如下:

db.runCommand(
   {
     geoNear: "places", //table Name
     near: [ -73.9667, 40.78 ] ,  // central point
     spherical: true,  // treat the index as a spherical index
     query: { category: "public" }  // filters
     maxDistance: 0.0001531 //  distance in about one kilometer
   }
)

geoNear可以理解为一个从起始点开始的不断向外扩散的环形搜索过程。如下图所示:

由于圆自身的性质,外环的任意点到圆心的距离一定大于内环任意点到圆心的距离,所以以圆环进行扩张迭代的好处是:

1)减少需要排序比较的点的个数 2)能够尽早发现满足条件的点从而返回,避免不必要的搜索

点集密度估算

那么,如何确定初始迭代步长呢,mongoDB认为初始迭代步长和点集密度相关。

geoNear 会根据点集的密度来确定迭代的初始步长。估算步骤如下:

1)从最小步长默认为60cm向外以矩形范围搜索,如果范围内有至少一个点,则停止搜索,转3)否则转 2) 2)步长倍增,继续步骤1) 3)以矩形对角线长度的三倍作为初始迭代步长。

圆环覆盖与索引前缀原理

上面我们说过,每一次的搜索都是以圆环为单位进行的,但是真实存入Btree中的是{GeoHashId->RecordValue},计算出与圆环相交的所有边长60cm的格子的GeoHash的值并在Btree中搜素绝对是一个非常愚蠢的做法,因为如果圆环的面积很大,光是枚举所有的GeoHash就有上百万个

但是换个角度来看,其实以地球为一个整体去看待存储的点,绝对是稀疏的。这个稀疏的性质使得我们可以粗略的以平面四叉树的角度自上而下的找出与圆环相交的四叉树中间节点。

整个平面与圆环必然是相交的,于是将平面一分为四,剔除不相交的部分,对于每个留下来的子平面,继续一分为四,剔除不相交的部分,经过多轮迭代,留下来的子平面的GeoHash都是该子平面中所有grid的索引前缀,如下面四幅图所示:

上面四幅图中,分别为整个平面被四叉树划分0,1,2,3次后与圆环的相交情况,如果继续往下细分,所形成的图形就越来越逼近整个圆环。MongoDB中使用参数internalGeoNearQuery2DMaxCoveringCells来限制最多逼近到多少个子平面与圆环相交,默认为16

我们注意到,上述平面划分过程为四叉树的分裂过程,每一次分裂都使得递归搜索的子平面与父平面有相同的GeoHash前缀(这里需要思考为什么,可能不太明显),因此每一个子平面可以对应于BTree中一段连续的Range(这里又是为什么?),也正因此,该参数越大,会使得需要搜索的子平面越少,但是会使得Btree的Range搜索更趋向于随机化搜索,导致更多的IO。我们知道Btree更适合于做Range搜索,所以对该参数的调整需要慎重。

展望

MongoDB原生的geoNear接口是国内各大LBS应用的主流选择。腾讯云的MongoDB专家经过测试发现,在点集稠密的情况下,MongoDB原生的geoNear接口效率会急剧下降,单机甚至不到1000QPS。腾讯云MongoDB对此进行了持续的优化,在不影响效果的前提下,geoNear的效率有10倍以上的提升,建议大家选择腾讯云MongoDB作为LBS应用的存储方案。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WOLFRAM

Mathematica 之微分特征系统

1296
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(十四)统计信息(下)

在 统计信息(上) 中,我们介绍了统计信息基本概念、TiDB 的统计信息收集/更新机制以及如何用统计信息来估计算子代价,本篇将会结合原理介绍 TiDB 的源码实...

943
来自专栏数据小魔方

R语言学习笔记——柱形图

今天分享R语言中的柱形图,所有图表语法都基于ggplot2包中的ggplot函数完成 。 其实R语言本身就带有各种作图函数,比如plot、bar、pie等,而且...

41013
来自专栏CDA数据分析师

如何使用R语言解决可恶的脏数据

在数据分析过程中最头疼的应该是如何应付脏数据,脏数据的存在将会对后期的建模、挖掘等工作造成严重的错误,所以必须谨慎的处理那些脏数据。 脏数据的存在形式主要有如下...

1925
来自专栏华章科技

入门干货:从《权力的游戏》战斗场景中搞懂数据抽样和过滤

导读: 直观来看,处理大数据的一个方法就是减少要处理的数据量,从而使处理的数据量能够达到当前的处理能力能够处理的程度。可以使用的方法主要包括抽样和过滤。两者的区...

351
来自专栏大数据文摘

改变计算技术的 9 个伟大算法

1863
来自专栏生信宝典

R语言学习 - 非参数法生存分析

生存分析指根据试验或调查得到的数据对生物或人的生存时间进行分析和推断,研究生存时间和结局与众多影响因素间关系及其程度大小的方法,也称生存率分析或存活率分析。常用...

2178
来自专栏大数据

季节性单位根

正如MAT8181课程中所讨论的那样,至少有两种非平稳的时间序列:存在趋势的和存在单位根(这种类型被称为 单整的)。单位根测试不能用来评估一个时间序列是否平稳,...

2465
来自专栏张俊红

python数据科学-单变量数据分析

总第85篇 01|背景: 我们在做机器学习之前,需要自己先对数据进行深入的了解(这些数据是什么类型,总共有多少数据,有没有缺失值,均值是多少之类的),只有自己对...

2955
来自专栏数据结构与算法

模拟退火算法

爬山算法的思想就是一个劲的找最优解,如果接下来的任何状态都比当前状态差,那么就停止

55115

扫码关注云+社区