*** MYSQL 算法难题: 查询距离指定坐标 10 公里范围内的所有店铺 ***

tile38

直接按距离查就行， 之前做过和 gis 相关的。

https://dev.mysql.com/blog-archive/geography-in-mysql-8-0/

@249239432 r-tree ,kd-tree 这些数据结构都不行, 还得是我最爱的集群 for 循环最高效

50w 数据直接用 mysql 查不用一秒就出来了

感觉 geohash 应该可以的

@249239432 你们公司方便告诉一下是哪个公司吗，可以降本增效了

大多数据库都有 geo 相关支持的。简单点 redis 就可以

600 万数据查询经纬度大于 50 米，跑一次查询 16 小时，笑死
可能是个好消息，这种公司还能活着说明市场还没差到那么惨？

如果版本低，可以先从 MySQL 中取正方形的数据，10 公里可以取固定的经纬度差，然后再用代码计算哪些需要剔除。

10 公里范围内，只要不是南北极，不用算球的弧度，相差不会太大，可能有十几厘米的误差

我之前用 decimal 类型存经纬度数据，精确到四位还是几位忘了，两个字段，查距离就比较经纬度数据了，能查个大概。

比较格子的四个点，在点里面的数据全取出来。

东南西北各扩展 10 公里然后把正方形里的店铺全筛出来，然后再用代码算一下距离把不满足条件的过滤掉。

geohash

@249239432 你这也太离谱了，我给你看看 postgis 的测试结果，笔记本上运行（ m1max ）。
创建一个测试表，并用使用 WGS84 坐标系，创建 1000w 条测试数据，平均分布在经度 120-130 ，纬度 60-70
postgres=# create table geo(id serial primary key,point geography);
CREATE TABLE
Time: 8.159 ms
postgres=# insert into geo(point) select st_point(120+10*random(),60+10*random(),4326) from generate_series(1,10000000);
INSERT 0 10000000
Time: 22743.621 ms (00:22.744)
postgres=# select count(*) from geo;
count
----------
10000000
(1 row)

Time: 184.563 ms
直接查找 500m 内的点
postgres=# select id,st_astext(point) from geo where point<->st_point(121,61,4326) <500;
id | st_astext
---------+----------------------------------------------
462445 | POINT(120.99758165008446 60.99813696562379)
1438617 | POINT(121.00541966217078 61.00254115685877)
6427771 | POINT(121.0057518866478 60.99946005998968)
7239910 | POINT(121.00062919717045 61.00302782747821)
480378 | POINT(121.00686930870204 60.99929456226042)
6463221 | POINT(121.00448273536959 60.99901955735362)
7497972 | POINT(121.00128087999187 61.000266168985476)
9546292 | POINT(121.00044691737057 61.00368666618427)
9594039 | POINT(121.00070061094034 60.996584053665245)
(9 rows)

Time: 897.110 ms
创建 GIST 索引后使用 ST_DWithin 函数可以使用索引加速
postgres=# select id,st_astext(point) from geo where ST_DWithin(point,st_point(121,61,4326),500) ;
id | st_astext
---------+----------------------------------------------
7497972 | POINT(121.00128087999187 61.000266168985476)
9594039 | POINT(121.00070061094034 60.996584053665245)
6463221 | POINT(121.00448273536959 60.99901955735362)
9546292 | POINT(121.00044691737057 61.00368666618427)
1438617 | POINT(121.00541966217078 61.00254115685877)
7239910 | POINT(121.00062919717045 61.00302782747821)
462445 | POINT(120.99758165008446 60.99813696562379)
480378 | POINT(121.00686930870204 60.99929456226042)
6427771 | POINT(121.0057518866478 60.99946005998968)
(9 rows)

Time: 10.359 ms
只要 10 毫秒，比你们快至少 3 亿倍

只能说废公司是贵物

这帖子太刷新下限了，没想到数据库水平如此之低，天天卷八股了

@xz410236056 先限定范围在圆的外接正方形内，只对这个正方形继续搜索

@lianglianglee 经度差要除纬度的余弦,不然北京就和赤道就差了 25%.
纬度 60 度时,每 1 度经度的长度是赤道的一半.
反正被搜索点的纬度是确定的,除以余弦还是常数子,不影响效率.

哈哈，为啥这种不涉及价值观和意识形态的纯技术问题也能吵起来

圆形半径比较难算，如果是计算一个上下左右 5 公里范围的矩形就简单了。如果你不用索引的内置函数的话，可以计算出这个矩形的经度范围和纬度范围，然后根据这个范围过滤就行了，前提是经度纬度要分开用浮点字段存。这个方法适合没有用 GIS 索引的情况下。
如果你用了空间索引的话：

SELECT *
FROM locations
WHERE ST_Contains(
GeomFromText('Circle(Longitude Latitude radius)'),
position
);

@lyz1990 因为楼里某位大佬举例的场景和使用的解决方案。。太离谱了

XX 年前知道 oracle spatial 是解决空间计算的扩展
看楼上的回复，mysql geo 应该类似