像默默，微信的附近的人的功能是是怎么实现的。

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3824 天前的主题，其中的信息可能已经有所发展或是发生改变。

数据表可能是这样的

user_id | latitude | longtitude

但是不可能遍历整个数据表吧。

求大概的算法和实现方式

12 条回复 • 2014-07-06 21:50:56 +08:00

akfish

2014-07-06 17:20:06 +08:00

当然不可能遍历，地理位置网格分块，存块ID，然后四叉搜索。

你的经纬度换算成网格ID，同网格的人撸出来，临近网格的人撸出来，搞定。

lsylsy2

2014-07-06 17:20:27 +08:00

灯塔算法

fangzhzh

2014-07-06 17:29:36 +08:00 via Android

范围扩大一倍人数指数级增长

TangMonk

2014-07-06 17:33:34 +08:00

@akfish 谢谢，请问怎么把地理位置分块，怎么把经纬度转化成网格 ID 呢。

TangMonk

2014-07-06 17:33:55 +08:00

貌似有个 geohash，研究下

akfish

2014-07-06 18:00:11 +08:00

@TangMonk 方法很多，本质上就是hash

udonmai

2014-07-06 18:37:11 +08:00

KD Tree
R Tree

TangMonk

2014-07-06 19:55:46 +08:00

TangMonk

2014-07-06 20:57:47 +08:00

nice！ mongodb 支持 spatial search, 童鞋们可以看下：

http://docs.mongodb.org/manual/core/geospatial-indexes/

won

2014-07-06 21:17:25 +08:00 via iPhone

购买geo

wanjun

2014-07-06 21:18:01 +08:00

就看你的用户量了，如果最多只有几亿的话，mysql就可以了，存储x,y坐标，加索引，
然后mongodb自身实现了计算距离，排序。
geohash并不好用，https://github.com/kungfoo/geohash-java

leiz

2014-07-06 21:50:56 +08:00

postgis