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

相关文章

来自专栏Spark学习技巧

复习:聊聊hive随机采样①

数据量大的时候,对数据进行采样,然后再做模型分析。作为数据仓库的必备品hive,我们如何对其进行采样呢?

27930
来自专栏算法修养

文本分类学习 (十)构造机器学习Libsvm 的C# wrapper(调用c/c++动态链接库)

前言: 对于SVM的了解,看前辈写的博客加上读论文对于SVM的皮毛知识总算有点了解,比如线性分类器,和求凸二次规划中用到的高等数学知识。然而SVM最核心的地方应...

10620
来自专栏冰霜之地

高效的多维空间点索引算法 — Geohash 和 Google S2

每天我们晚上加班回家,可能都会用到滴滴或者共享单车。打开 app 会看到如下的界面:

69350
来自专栏Python攻城狮

Python数据科学(六)- 资料清理(Ⅰ)1.Pandas1.资料筛选2.侦测遗失值3.补齐遗失值

成功爬取到我们所需要的数据以后,接下来应该做的是对资料进行清理和转换, 很多人遇到这种情况最自然地反应就是“写个脚本”,当然这也算是一个很好的解决方法,但是,p...

13830
来自专栏吉浦迅科技

DAY19:阅读纹理内存之Texture Gather

39640
来自专栏owent

2018年的新通用伪随机数算法(xoshiro / xoroshiro)的C++(head only)实现

前段时间看到说Lua 5.4用了一种新的通用随机数算法,替换掉本来内部使用的CRT的随机数引擎。我看了一下大致的实现,CPU和空间复杂度任然保持了一个较低的水平...

22720
来自专栏大数据文摘

手把手丨输验证码输到崩溃?教你15分钟黑掉全球最流行的验证码插件

16710
来自专栏安富莱嵌入式技术分享

【安富莱二代示波器教程】第10章 示波器设计—数字信号处理

本章节为大家讲解二代示波器中用到的FFT和FIR。单纯从应用上来说,比较省事,调用API函数即可,从学习的角度来说,需要大家花点精力。

10630
来自专栏专知

【重磅】深度学习顶会 ICLR 2018 匿名提交论文列表(附pdf下载链接)

【导读】ICLR,全称为「International Conference on Learning Representations」(国际学习表征会议),201...

663100
来自专栏新智元

深度学习挑战冯·诺依曼结构

【新智元导读】想挑战冯·诺依曼,就必须从三个要素入手:基本操作,例如加减乘除;逻辑流程控制,例如if-else-then,for,while;设存储器,内存和硬...

406110

扫码关注云+社区

领取腾讯云代金券