免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 4737 | 回复: 1

[MongoDB] 图解 MongoDB 地理位置索引的实现原理 [复制链接]

论坛徽章:
0
发表于 2012-02-21 21:35 |显示全部楼层
图解 MongoDB 地理位置索引的实现原理







地理位置索引支持是MongoDB的一大亮点,这也是全球最流行的LBS服务foursquare 选择MongoDB的原因之一。我们知道,通常的数据库索引结构是B+ Tree,如何将地理位置转化为可建立B+Tree的形式,下文将为你描述。

首先假设我们将需要索引的整个地图分成16×16的方格,如下图(左下角为坐标0,0 右上角为坐标16,16):



单纯的[x,y]的数据是无法建立索引的,所以MongoDB在建立索引的时候,会根据相应字段的坐标计算一个可以用来做索引的hash值,这个值叫做geohash,下面我们以地图上坐标为[4,6]的点(图中红叉位置)为例。

我们第一步将整个地图分成等大小的四块,如下图:



划分成四块后我们可以定义这四块的值,如下(左下为00,左上为01,右下为10,右上为11):

01 11
00 10

这样[4,6]点的geohash值目前为 00

然后再将四个小块每一块进行切割,如下:



这时[4,6]点位于右上区域,右上的值为11,这样[4,6]点的geohash值变为:0011

继续往下做两次切分:





最终得到[4,6]点的geohash值为:00110100

这样我们用这个值来做索引,则地图上点相近的点就可以转化成有相同前缀的geohash值了。

我们可以看到,这个geohash值的精确度是与划分地图的次数成正比的,上例对地图划分了四次。而MongoDB默认是进行26次划分,这个值在建立索引时是可控的。具体建立二维地理位置索引的命令如下:

db.map.ensureIndex({point : "2d"}, {min : 0, max : 16, bits : 4})其中的bits参数就是划分几次,默认为26次。

相关链接:Mongo in Flatland

论坛徽章:
0
发表于 2012-02-24 17:39 |显示全部楼层
谢谢分享
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP