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 条评论
登录 后参与评论

相关文章

来自专栏PaddlePaddle

【FAQ】本地训练与预测相关问题汇总

导语 在使用指南的最后一部分,我们汇总了使用PaddlePaddle过程中的常见问题,本部分推文目录如下: 2.22:【FAQ】模型配置相关问题汇总 2.23:...

34610
来自专栏生信技能树

第3篇:用MACS2软件call peaks

Peak calling即利用计算的方法找出ChIP-seq或ATAC-seq中reads富集的基因组区域。

2624
来自专栏AI研习社

Github 项目推荐 | YOLOv3 的最小化 PyTorch 实现

https://github.com/eriklindernoren/PyTorch-YOLOv3

2142
来自专栏企鹅号快讯

Hinton胶囊理论代码开源,上线即受热捧

当前的深度学习理论是由GeoffreyHinton大神在2007年确立起来的,但是如今他却认为,“CNN的特征提取层与次抽样层交叉存取,将相同类型的相邻特征检测...

1926
来自专栏Python爬虫实战

图片转字符画

字符画是一系列字符的组合,我们可以把字符看作是比较大块的像素,一个字符能表现一种颜色(暂且这么理解吧),字符的种类越多,可以表现的颜色也越多,图片也会更有层次感...

1082
来自专栏AI科技评论

开发 | 如何利用微信监管你的TF训练

AI科技评论按:本文作者Coldwings,AI科技评论获其授权发布。 之前回答问题【在机器学习模型的训练期间,大概几十分钟到几小时不等,大家都会在等实验的时候...

3008
来自专栏生信宝典

一文教会你查找基因的启动子、UTR、TSS等区域以及预测转录因子结合位点

本文授权转载自科研小助手(ID:SciRes)斜体小一号字体为生信宝典的备注或校正。

1.1K1
来自专栏AI研习社

如何利用微信监管你的TF训练?

之前回答问题【在机器学习模型的训练期间,大概几十分钟到几小时不等,大家都会在等实验的时候做什么?(http://t.cn/Rl8119m)】的时候,说到可以用微...

3474
来自专栏MixLab科技+设计实验室

自己动手做一个识别手写数字的web应用01

最近在深入地学习keras,发现网上各种教程都是教你怎么训练模型的,很少有问题提到如何把训练好的模型部署为后端服务,为web及app提供服务。 于是,我决定把学...

3788
来自专栏简书专栏

基于jieba、gensim.word2vec、LogisticRegression的文档分类

建议读者安装anaconda,这个集成开发环境自带了很多包。 到2018年8月30日仍为最新版本的anaconda下载链接: https://pan.baid...

1244

扫码关注云+社区