mysql - MySql 性能查找 1 公里内的所有用户

Question

我有 mysql 表，需要找到彼此相距 1 公里以内的所有用户表：

Geo
----------
id(int)
location(geometry)  with spatial index
username(string)

可以解决：

1. 由用户迭代 i ... n
2. 对于每个选择特定多边形内的所有用户，使用索引
3. 互相发信息

所以复杂性将是〜O（n）或更多（取决于索引），还有其他性能更好的解决方案吗？

Answer 1

由于您的数据是 2D 的，并且您知道您的半径，您可以为您的数据建立一个网格索引。然后每个小区将只向每个相邻小区发送消息。

计算单元分配是 O(n)。所以这应该把这个任务降低到n * O(m * m)，m你的最大单元占用时间是什么时候。

请注意，这里很难保证任何事情。如果您的所有对象都在 1 公里的半径范围内，那么没有索引会对您有太大帮助。每个人都必须发送给其他人，因为这将是二次的。

Answer 2

Mysql 使用R-Tree来创建空间索引，因此只要您的索引适合内存，您就应该拥有比 O(n) 更好的性能。