直接SQL方式
表结构
|
|
准备测试数据
使用下面的PHP脚本建立基础数据 100W条
SQL查询方式(查询10km内的离我(lat: 50, lng : 100)最近的点前25个)
此种方式由球面距离公式计算点距离,为减少计算与排序的数据量,使用距离估算方式由添加了索引的lat,lng列进行距离估算;另外一种方式是根据GEOHASH估算。
|
|
|
|
SQL的EXPLAIN结果显示
id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
---|---|---|---|---|---|---|---|---|---|
1 | SIMPLE | ggc | range | lat,lng | lat,lng | 8 | (NULL) | 3654 | Using where; Using index; Using filesort |
使用Sphinx
Sphinx配置
|
|
建立索引
|
|
启动searchd
|
|
测试
|
|
由查询数的 $res
看到查询时间
|
|
反复调整查询范围 $circle
查询时间都在100~200ms之间,可以得出结论sphinx内部没有对范围查询做优化。
由sphinx官方的文档可以看出,sphinx使用的也是球面距离算法(haversine algorithm)。
由sphinx源码中可以看出,对距离较近的点sphinx采用了另外的算法。
使用Redis的GEO存储方式
截至此时,Redis的GEO功能还是在unstable版本中,下载安装unstable版本后对Redis进行了测试。
建立测试数据
|
|
测试
使用以下代码测试性能
|
|
耗时: 0.016094207763672 也就是大概 16ms
将范围改为 20000000km 再次进行测试
耗时: 0.85910105705261 也就是 859ms
可见Redis内部对查询范围进行了优化,Redis使用的是GEOHASH方式进行的优化。
距离计算算法Redis也是使用球面距离算法进行,可查看Redis源码
|
|
优化
对于以上三种方式,对于距离的计算都有优化的空间,可参考美团技术博客的这篇文章。
使用简化的算法,并对cos进行多项式拟合消除三角函数。
对于Sphinx、Redis可以通过修改源码的方式进行进一步的优化