【Java】需要设计一款基于LBS的交友系统，如何设计地理空间邻近算法？

详细设计重点关注邻近算法，即如何根据用户的地理位置找到一定范围内的其他用户。

您可以通过Liao App获取用户当前的经纬度坐标，并根据经度和纬度计算两个用户之间的距离。距离公式使用以下半正弦公式：

这里，r代表地球半径，\\(\\\\small \\\\varphi\\)代表纬度，\\(\\\\small \\\\lambda\\)代表经度。

但是，如果你有十亿个用户，并且需要计算并排序与当前用户的每次匹配与其他用户的距离，则所需的计算量将至少为数千亿。我们买不起。常见的空间邻近算法有四种，我们一一分析，最终选择最佳方案：

一、问题解析

您可以将用户的经度和纬度直接记录到数据库中。纬度字段记录纬度，经度字段记录经度。用户当前的纬度和经度是X和Y。如果你想求距离D.可以通过以下SQL检索当前用户经纬度之间的其他用户：

从纬度在X-D 和X+D 之间、经度在Y-D 和Y+D 之间的用户中选择*。

这样的SQL 相对容易实现，但是当你有十亿用户并且你的数据分散在数百台服务器上时，运行起来就变得非常低效。此外，虽然我们使用经度和纬度距离进行近似计算，但在高纬度地区，这种近似计算的偏差仍然很大。

同时，“X-D与X+D之间”、“Y-D与Y+D之间”会产生大量的中间计算数据。在这两者之间，首先返回每个经度和纬度区间内的所有用户。然后进行如下图所示的交集和处理。

用户数量较多，附近的好友计算会被频繁访问。同时，分片数据库的配置计算必须在中间代理服务器或应用服务器上完成。计算会产生计算负载，这超出了我们的系统可以处理的范围。因此，这个计划可以放弃。

11.1 需求分析

为了减少上述交集计算中使用的中间数据量，我们将整个地球划分为如下所示的网格。

实际上，划分的网格比图中显示的要密集得多，在赤道附近经纬度每10 公里就有一个网格。

这样，每个用户将始终被分类到一个网格中。在users表中记录用户的网格ID（gridID），并利用该字段进行辅助搜索，将搜索限制在用户所在的网格内。这显着减少了中间数据量。 SQL 是：

对于select*from 用户，纬度在X-D 和X+D 之间，经度在Y-D 和Y+D 之间，gridID 为(gridIDx0, gridIDx1, gridIDx2, gridIDx3, gridIDx4, gridIDx5, gridIDx6, gridIDx7, gridIDx8)马苏。

虽然这条SQL 的计算量比上面的SQL 少很多，但是对于频繁访问的分片数据库来说，使用这样的SQL 来查询附近的好友仍然无法承受距离精度。

然而基于这种网格设计思想，我发现不需要通过数据库就可以实现附近好友的查询。所有网格及其包含的用户都可以记录在内存中。当您运行邻近查询时，您只需要计算一个用户与内存中8 个邻居的网格中的所有用户之间的距离。

将所有用户的经度和纬度读入内存所需的内存量可以估计为\\(\\\\small 1G\\\\times3\\\\times4B=12GB\\)（用户ID，经度，所有纬度均以4）字节编码，用户总数为1G）。这个内存量是完全可以接受的。

事实上，通过适当选择网格的大小，您可以连续访问当前用户位置周围的网格并连续看到附近的其他用户，从近到远，而无需通过SQL 检索它们。那么如何选择网格的大小呢？如何根据用户的位置获取用户所在的网格呢？我们来看看常用的动态如何呢？网格和GeoHash 算法的实践。

11.2 概要设计

事实上，无论你如何选择网格大小，都可能不合适。这是因为，在陆家嘴，一个小网格也能容纳近百万用户，而在可可西里，一个很大的网格只能容纳几个用户。

因此，如果网格中的用户太多，我希望能够将网格分割成几个较小的网格，如果较小的网格中仍然有太多用户，我希望能够将其分割成甚至更小的网格。网格。如下所示。

这是一种四叉树网格结构，最初整个地球只有一个网格，但是随着用户数量的增加并超过阈值（500个用户），四棵子树对应于父节点网格。四个地理子网格。同时，用户根据位置重新分配到四个子树中。类似地，当特定子树中的用户数量增加超过阈值时，子树继续分裂成四个子树，如图所示。

因此，您可以将全局用户分配给这样的4 树网格结构。所有用户都必须位于该4 树的叶节点上，并且每个节点不能包含超过500 个用户。这样的话，陆家嘴网格可能很小，但可可西里网格可能很大，相应的太平洋网格可能长达数千公里。

通过指定当前用户的经纬度来查询附近的用户时，如果根节点是叶子节点，则从根节点开始搜索，直接遍历根节点内的所有用户来计算距离。如果根节点不是叶子节点，则根据指定的经度和纬度确定其在网格中的位置。有四个位置：左上、右上、右下、左下，顺序对应四个子树。根据它们在网格中的位置来访问相应的。如果子树是叶子节点，则在叶子节点内搜索。如果不是叶子节点，继续上面的过程，直到到达叶子节点。

上述过程只能找到当前用户所在网格中的好友。如何找到附近网格中的其他用户呢？实际上，只需将四叉树的所有叶节点排序成一个双向链表即可。链表上每个节点的一些前驱和后继是与该节点在地理上相邻的节点。

动态网格又称为四叉树网格，更常用于空间邻近算法，也能满足.但编程实现有点繁琐，如果网格大小设计不当，树高就会太高，每次搜索需要走的路径也会太长，导致性能不佳。相对贫穷。我们来看看GeoHash算法，它在性能和灵活性上都有所提高。

11.3 详细设计

GeoHash实际上是除了动态网格算法之外的另一种变形网格算法，也是Redis中Geo函数使用的算法。 GeoHash 是一种对网格进行编码并根据该编码存储哈希的算法。

经度和纬度数字的精度不同，意味着经度和纬度的误差范围不同。例如，如果将经度和纬度保留到小数点后一位，误差幅度可达11 公里（赤道附近）。这意味着11 公里* 11 公里的经度和纬度网格，精确到小数点后一位。

然后创建一个哈希表key，value=\’\’style=\’box-sizing:respect;\’对，以小数点后一位精度的经纬度为key，以网格中的用户集合为value。通过找到这个KV对以及周围8个网格中的KV对，并计算这些值内的所有用户与当前用户的距离，就可以找到11公里以内的所有用户。

事实上，redis的GeoHash并不是直接使用经度和纬度作为key，而是使用基于Z序曲线的编码方法将二维经度和纬度转换为一维二进制，并进行base32编码执行。具体流程如下：

首先，求经度和纬度各自当前区间的平均值（对于纬度，起始区间为[-90, 90]；对于经度，起始区间为[-180, 180]），然后计算当前间隔。该区间分为两个区间。接下来，将用户的经度和纬度与区间的平均值进行比较。用户的经度和纬度必须位于两个区间之一内。如果大于平均值则为1。如果低于平均水平：在这种情况下，它将需要0。继续对当前区间进行平均，并将当前区间分成另外两个区间。重复此过程，得到经度和纬度方向的两个二进制数。二进制数越长，间隔越小，精度越高。

下图展示了经度和纬度42.60411、-5.59041的二进制编码过程。最终得到纬度的12 位编码和经度的13 位编码。

获得两个二进制数后，将它们组合成一个二进制数。连接规则从第一个数字开始，其中奇数位是经度，偶数位是纬度。上例连接后的结果是01101 11111 11000 00100 00010，总共25 个二进制数字。

我们将25个二进制数字分为5组，每组有5个二进制数字，使用Base32编码对应的十进制数字如下：

编码计算过程如下：

最后，检索字符串“ezs42”作为哈希表的键。 25位二进制GeoHash码的误差范围约为2.4公里，对应于\\(\\\\小2.4km\\\\times2.4km\\)网格。网格中的用户作为值放入哈希表中。

一般来说，可以选择GeoHash的编码长度，实现不同大小的网格，以满足邻近约会的应用场景。但是，由于Redis需要解决更常见的地理定位计算场景，因此Redis中的GeoHashes存储在跳表中，而不是哈希表中。

Redis使用52位二进制GeoHash编码，误差范围为0.6米。 Redis 将编码的二进制数扩展为一维，遵循Z 顺序曲线的布局。换句话说，用Z形曲线连接二维经纬度点。 Z 顺序曲线布局的示例是：

事实上，所谓的Z序曲线布局本质上是基于GeoHash的二值排序。这些编码的二进制数据存储在跳跃表中。搜索用户时，您可以快速找到用户，并沿着跳转列表来回搜索，找到您附近的用户。

11.3.1 SQL邻近算法

Liao的邻近算法最终选择了GeoHash算法，该算法使用哈希表存储。经度用13 位编码，纬度用12 位编码。所以最终的GeoHash编码为5个字符，每个网格为\\(\\\\small 4.9 km\\\\time4.9km\\ \\约25km^{2}\\)，整个地球为\\(\\\\small 2^{ 25} \\大约3300 万个\\）网格化并删除了大多数地点的海洋和沙漠极地区域。那里没有人居住，需要存储的哈希键数量不到500万个，存储在哈希表中。哈希表的键是GeoHash编码，值是包含具有相同GeoHash编码的所有用户ID的列表。

在搜索附近的好友时，Liao首先计算用户当前位置的GeoHash值（5个字符），然后从哈希表中读取该哈希值对应的所有用户，即同一网格中的用户。将满足匹配条件的对象返回给用户。如果网格中的匹配对象数量不足，我们计算周围8个网格的GeoHash值，并通过加载这些哈希对应的用户列表来继续匹配。

11.3.2 地理网格邻近算法

我们计划开发一个针对所有互联网内容的搜索引擎，产品名称为“Bingoo”。

Bingo 的主要技术挑战是：

如何有效管理用户输入搜索词时爬虫检索到的大量数据，以及如何将包含搜索词的网页内容排序到搜索结果列表的顶部。网页正是用户所期望的。

11.3.3 动态网格算法

根据我多年从初学者到架构师的学习经验，我整理了一份50万字的面试分析文档、简历模板、学习路线图和必读的Java学习书籍。有需要的朋友请留言或点击。请在评论区“寻求帮助”。

#以上需要设计一个基于[Java] LBS的交友系统。如何设计地理空间邻近算法？相关内容来源网络仅供参考。相关信息请参见官方公告。