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

107 条回复 • 2024-03-14 15:16:30 +08:00

1 2

❮

❯

1

xmumiffy

265 天前

where 条件限制经纬度差距各+-0.1 度,然后再算

2

leaflxh

265 天前

先把店铺按照城市区域分好区

3

dode

265 天前

建一个大一些的基础网格系统，正方形，三角形，六边形，提前划分标记一下这些经纬度

4

akira

265 天前

你先说下你怎么计算距离的呢

5

wenber

265 天前

1

6

HanSonJ

265 天前

2

https://redis.io/docs/data-types/geospatial/

我第一次见坐标用 MySQL 实现的。。。你不得算距离啊

7

liprais

265 天前 via iPhone

mysql 也有 geo 功能，自己看看文档呗

8

toneewang

265 天前

这个需求是不是可以用空间数据类型来存啊

9

toneewang

265 天前

https://www.mysqlzh.com/doc/176/143.html

10

xmumiffy

265 天前

@xmumiffy 经度有错误,还要除余弦

11

V2April

265 天前

@dode 六边形感觉是个有意思的思路，像文明 6 那样数格子就行了

12

rabbbit

265 天前

Redis geo 或者 PostGIS

13

laminux29

265 天前

思路错了。这就好比，你选择用汇编去实现，然后发个新帖子：汇编算法难题。

正确的思路是，选择支持地理范围直接查询的数据库，用它做个冗余数据库，专门做地理查询服务就行了，不要为难 MySQL ，很多场景，Mysql 并不适合。

14

ZoR

265 天前

redis

15

amon

265 天前

2

XY 问题，你还是使用 GEO 存储吧

16

546L5LiK6ZOt

265 天前 via iPhone

之前做过地理位置相关的，经纬度小数点第一位精度是 10 公里左右，数据库按一位小数存经纬度，查询 sql 就变成等值查询了

17

BeiChuanAlex

265 天前

我在想如果用 postgresql 会不会更好写。

18

Vegetable

265 天前

1

@546L5LiK6ZOt 这也太糊弄了，0.9 和 1.1 匹配吗？

19

mikewang

265 天前

根据坐标和 10 公里的条件，确定极限范围：
A <= 经度 <= B
C <= 纬度 <= D
然后在查到的数据中，使用子查询验证是否真正满足 10 公里的条件。
这样可以避免全表计算距离。

20

xiangyuecn

265 天前

mysql 自带空间数据类型 geometry + 空间索引，可以自己研究一下 mysql 文档，查询就直接构造出一个圆面（用合适边数的多边形去近似即可），查出和这个圆面相交坐标点就 ojbk 了，基本上所有数据库通用

21

xiangyuecn

265 天前

指定中心点坐标、半径，生成圆面的代码，可以参考我的 AreaCity-Query-Geometry 代码，30 行

https://github.com/xiangyuecn/AreaCity-Query-Geometry/blob/b626c53a85350c43c64e7886e926c3e9ac877a52/AreaCityQuery.java#L1375-L1402

其中采用 Haversine formula 算法计算经纬度坐标的距离，5 行代码

22

a1b2c3T

265 天前 via iPhone

没记错的话 redis 好像有这个功能，

23

Thymolblue

265 天前 via Android

2

@546L5LiK6ZOt 实际上每经度距离和纬度相关，这样算这个库在北京就用不了了。

24

iseki

265 天前 via Android

以前流行过 geohash ，如果 MySQL 自己的地理信息功能挑不起来大梁，可以尝试附加一个 geohash

25

iseki

265 天前 via Android

另外如果可行，还是推荐使用现成可靠的地理信息设施，比如 PostGIS ，应该比 MySQL 自己的 GIS 功能强得多

26

tracymcladdy

265 天前 via iPhone

不要折腾，全部加载出来，一个工具类的事

27

sola97

265 天前

用过 postgis

28

249239432

265 天前

楼上一群半吊子，这个是计算量的问题，需要消耗 cpu 资源的，不是换个工具换个数据库就能解决

我司需求是 600 万数据查询经纬度大于 50 米，解决方案是用 spark 并行计算，20 个 task ，一个任务配置 2G 内存

后端大概 50 台刀片机服务器集群，跑一次要 16 个小时

29

lshero

265 天前

非要 mysql 吗 geohash 支持那么差劲的
一般用 ES 一步到位或者 Redis 得 geohash 取出 ID 后 mget 获取详情

30

changdy

265 天前

8

@249239432 哈哈笑死我了才 20w 条记录... 还需要购买额外的资源... 还说别人是半吊子..
说句不客气的话..200w 数据 postgis 也是轻轻松松搞定...
楼上那么多人提到了 geo 相关的服务..你这也不反思下自己... 果然你是最独特的...

希望你的下一条回复是 "经过认真分析,确实 geo 工具有可行性"

31

yingqi1

265 天前

2

@249239432 我也是搞大数据的，你这个 spark 的方案是真的有问题。spark 也有空间计算库 GeoSpark...。不需要硬算了。不论什么需求，一个 Job16 个小时真的吓到了。再说了，人家 OP 是要实时查询的方法，很明显用楼上的 redis/mysql geo 数据类型可以解决。

32

Fa11ingWood

265 天前

这个不知道我司用的是 pg pg 有自带的函数 ST_within 这个函数能实现你说的功能

33

249239432

265 天前

你们就不知道好好审题？，一个心眼钻牛角尖用什么工具、框架、软件上？
集群计算速度快还是用你那台数据库或者 postgis 计算快?

@yingqi1 我用程序硬算都能算出来，纠结这东西干什么，不用集群能变快么？

@changdy 我说的是我司方案，你意淫到别人头上去了？

34

249239432

265 天前

@changdy 200w 数据轻松搞定，5 个小时搞定？

35

lqs

265 天前

有个很简单很取巧的做法：

经度和纬度分两个字段，并仅对纬度建立索引。由于纬度等距，相差 0.09 度大约为 10 公里，且中国大城市纬度分布差异较大，这样能利用索引初步筛选，把 20 万筛选到 5000 以内。然后再用距离公式精确计算。

36

dzdh

265 天前

11

1.mysql 8.x 已经支持了，直接 sql 能实现，加上空间索引搜索非常快

2. redis geo 除了 mysql 之外最快的方案

3. 以上两种方案仅限于单纯的范围检索，如果是社交类的场景比如 5 公里范围内的排序外加+女的+18 的+3 天内上线过的+兴趣爱好 in (a,b,c) 的。那就老老实实上 elasticsearch 类的搜索引擎，没有任何其他方法可以最低成本实现。

37

yingqi1

265 天前

1

@249239432 典型的数据结构问题，关集群什么事情。审题: 20 万行数据，产品 ID (int)、经纬度(geohash) 各 8 字节。撑死 10 多 M ，要个鸡毛集群。再说说 spark 不是框架/软件吗？好好学习，请不要再使用“一群半吊子”的词汇了。

38

249239432

265 天前

@yingqi1 这是计算量的问题，跟数据大小有什么关系，说不过就开始专牛角尖了？ spark 我还不知道是什么东西么

2. 求最新最快的半径 10 公里内的所有店铺查询算法, 最好支持 MYSQL.
你这叫审题？我用集群是不是比你用单机快？

39

cI137

265 天前 via iPhone

有人不懂什么叫空间换时间，沙雕集群

40

SimbaPeng

265 天前

2

果然半吊子叫的是最凶的

41

SimbaPeng

265 天前

1

也不知道从哪听了个 spark ，见人都要叭叭两句，笑死我了

42

flyz

265 天前 via Android

@249239432 相当于跑出来存表？每次查询都做表查询么。

43

249239432

265 天前

@flyz 数据从表里面加载，在 spark 计算，结果你要存表或者干什么都行

44

ffw5b7

265 天前 via Android

3

美团技术团队，2014 年的距离优化文档，希望能帮助你
https://tech.meituan.com/2014/09/05/lucene-distance.html

45

encro

265 天前

你们这些人，

都当 mysql 开发团队是 SB ！！！

开发个简单的 geo 还比 pg 性能差一大截？

46

shenjinpeng

265 天前

推荐改用 es 查, 附带搜索一起搞了

PS: 贴一下 MySql 代码

```PHP
// 6371000 地球半径, 距离查询
// 可以当作子查询字段排序,先计算距离再排序
$distance = "ROUND( 6371000 * 2 * ASIN(SQRT( POW(SIN(({$lat} * PI() / 180 - latitude * PI() / 180) / 2),2) + COS({$lat} * PI() / 180) * COS(latitude * PI() / 180) * POW(SIN(({$lng} * PI() / 180 - longitude * PI() / 180) / 2),2))) ) AS distance";

```

```mysql
-- 自己实现的 mysql 函数
CREATE DEFINER=`root`@`%` FUNCTION `calcStoreDistance`(lat double, lng double,latitude double,longitude double) RETURNS int(11)
BEGIN
RETURN ROUND(
12742000 * ASIN(SQRT(
POW(SIN((lat * PI() / 180 - latitude * PI() / 180) / 2),2) +
COS(lat * PI() / 180) *
COS(latitude * PI() / 180) *
POW(SIN((lng * PI() / 180 - longitude * PI() / 180) / 2),2)
)));
END

-- 使用 SELECT *,calcStoreDistance(25.028317,102.678467,store.latitude,store.longitude) as distance FROM `store` order by distance;
```

```mysql
-- 直接用 mysql 自带函数
ROUND(st_distance_sphere(point($lng,$lat),geo)) as distance
```

47

Orlion

265 天前

https://blog.fanscore.cn/a/51/ 看下我这这篇文章吧，不知道对你有没有帮助，大概思路是取出一个坐标点附近九宫格所有坐标点，然后在程序中计算每个点距离该坐标点的距离，过滤掉不符合距离条件的点。

虽然文章中使用的是 redis ，但换成 mysql 应该是通用的吧。

48

opengps

265 天前

这问题刚好我以前做围栏时候用过，办法就是一楼所说。按照纬度 1 度相差 111km 来算，10 公里刚好就是 0.1 度，然后你再根据需要二次筛选即可（甚至不筛选也够用了）

49

QlanQ

265 天前

1

mysql 高版本的已经支持了，20w 数据还是可以应付了，等公司有钱了，快上市了，流量起来了，有时间了你在改一版吧，改成 es ，把前端相关查询都走 es(es 真的很费钱，小公司单台服务器配置差点的，都跑不起来，比如 2G 内存的)

50

summerLast

265 天前

1. 当前经纬度各加减 50 米
2. 35.35 米外 50 米内坐标转换算斜边长度大于 50 米的
1+2

51

echoZero

265 天前

之前做过根据用户位置查找多少米的商户，用 redis 的 GEO 算的

52

Desdemor

265 天前

俺们用的 redis

53

qsnow6

265 天前

GEO 是最佳实践，优化好索引速度很快，上集群纯粹没活硬整，集群间的通信不需要开销吗？

54

wanniwa

265 天前

@ffw5b7 #44 感谢分享，收藏了

55

tool2d

265 天前

我用 google 的 http://s2geometry.io/ ，查询效率很高。

这算法 mongodb 有内置空间索引，mysql 似乎没有。

56

griffen

265 天前

neo4j 比较适用于这类数据吧？

57

fengpan567

265 天前

我建议直接换 mongodb

58

xz410236056

265 天前

@xmumiffy #1 范围是个圆形。。。

59

eachann

265 天前

1. 使用 MySQL 的空间数据类型`POINT`存储位置经纬度是合适的。
2. 使用 MySQL 的空间索引和`ST_Distance_Sphere`函数可以快速查询半径 10 公里内的所有店铺。

解释：
1. MySQL 的空间数据类型`POINT`可以存储地理位置的经纬度信息。与传统的两个分开的字段相比，`POINT`类型可以让 MySQL 利用空间索引（ Spatial Index ），这样可以大大提高地理位置查询的效率。
2. `ST_Distance_Sphere`函数可以计算两个点之间的球面距离，适用于地球表面的距离计算。结合空间索引，这种方法可以快速筛选出指定半径内的店铺。

建议：
- 确保你的 MySQL 版本支持空间数据类型和函数。MySQL 5.7 及以上版本对空间数据的支持较好。
- 在包含经纬度的`POINT`字段上创建空间索引，以提高查询效率。
- 使用如下 SQL 示例进行查询：

```sql
SELECT shop_name, ST_AsText(location)
FROM shops
WHERE ST_Distance_Sphere(location, ST_GeomFromText('POINT(经度纬度)')) <= 10000;
```
- 替换`经度`和`纬度`为你的指定坐标。这个查询会返回距离指定坐标 10 公里内的所有店铺的名称和位置。

60

ElmerZhang

265 天前

我用 postgis 。不过我记得 mysql 5.7 开始就支持 geo 了吧？

61

openmynet

265 天前

tile38

62

sazima

265 天前

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

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

63

MoYi123

265 天前

1

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

64

freewind

265 天前

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

65

jackerbauer

265 天前

感觉 geohash 应该可以的

66

cI137

265 天前 via iPhone

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

67

ZeroDu

265 天前

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

68

rrfeng

265 天前

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

69

lianglianglee

265 天前

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

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

70

dyllen

265 天前

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

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

71

zihuyishi

265 天前

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

72

0576coder

265 天前

geohash

73

yjhatfdu2

265 天前

7

@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 亿倍

只能说废公司是贵物

74

leonhao

265 天前

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

75

xmumiffy

265 天前 via Android

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

76

xmumiffy

265 天前

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

77

lyz1990

265 天前

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

78

niubee1

265 天前

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

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

79

dbpe

264 天前

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

80

dog82

264 天前

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

81

lambdaq

264 天前

20 万条记录。。。直接 where 经度 between a and b AND 纬度 between c AND d 然后拿到数据，代码里 Haversine 一把梭吧。。

啥时候 1000w 以上的数据再用各种 geo 库吧。

82

xz410236056

264 天前

@xmumiffy #75 严格来说，应该是个球面（甚至除以余弦的方式也不严谨，地球又不是个球。应该用 Vincenty ），在空间中找个平面图形，误差会很大。经纬度中每度的距离并不是固定的，尤其是精度，会随着纬度变化而变化。有的地方会是个 22*22 的矩形（赤道）越靠近极点越小，这样就会有很多冗余数据和漏掉很多数据。