如何在附近商户中查找离你最近的商家?

前提背景

用户位置按照经纬度获取
用户可选范围内的商家
查询后的结果按顺序返回给用户
商户位置以经纬度存储

常用方法

数据库查询筛选

根据用户当前位置和用户所选择范围, 在数据库中查询后将结果在数据库中排序或者在内存中排序, 返回给用户

代码语言：txt复制

--longitude 表中经度字段
--latitude 表中维度字段
--lat1 指定点维度
--lon1 指定点经度
-- radius_in_km为用户所选择的范围
select business_id ,   6371 * ACOS(
        COS(RADIANS(lat1)) * COS(RADIANS(latitude)) * COS(RADIANS(longitude) - RADIANS(lon1))  
        SIN(RADIANS(lat1)) * SIN(RADIANS(latitude)
    ) AS distance 
    from business
    having
    6371 * ACOS(
        COS(RADIANS(lat1)) * COS(RADIANS(latitude)) * COS(RADIANS(longitude) - RADIANS(lon1))  
        SIN(RADIANS(lat1)) * SIN(RADIANS(latitude)
    ) <= radius_in_km;
    order by distance asc
    limit 0, 20

上述中我们可以给longitude 与latitude 建立联合索引, 方便我们做查询, 另外mysql中还有point类型, 用来表示点的位置, 我们可以利用ST_Distance_Sphere函数来计算店铺点位与用户点位之间的距离, 在做筛选也可

关于数据库查询更优秀的写法大家可以看看这篇文章

附近商家算法-地理空间距离计算优化 - 金泽夕 - 博客园 (cnblogs.com)

利用redis中的geo类型来做范围筛选

可以将用户最大能选范围内的所有商户的经纬度预先存redis中, 之后只需要用户将精度度传递给服务器, 服务器直接在redis中计算之后就可以将商户信息统计返回给用户

代码语言：txt复制

GEORADIUS geo:merchants $user_latitude $user_longitude 5 km WITHDIST WITHCOORD

这里userlatitude和user_longitude是用户的当前位置坐标。此命令将返回所有在5公里范围内的商家及其距离和坐标。我们还可以使用GEOFILTER命令对结果进行更复杂的排序和过滤，例如只返回特定类型的商家，或者按照距离排序。

四叉树解决

这里贴一篇某管上关于四叉树的连接,个人认为通俗易懂,https://www.youtube.com/watch?v=gGgyc9O7dqc , 只在这里做简单简述, 一个数四个节点, 每个节点有个容量为n, 节点存储该范围内的数据, 对应我们的场景就是存储商户信息, 每个节点表示大块区域, 节点的子节点表示他父节点中区域的一部分, 方便更细的划分, 比如中国就是根节点, 湖南,湖北, 北京,上海,,,,都是子节点, 长沙, 常德, ,,,,都是湖南的子节点, 然后每个县又是每个市的子节点, 知道划分成为最小区域位置, 比如我的筛选最小区域是1km * 1km,那么我就将中国分为n个1km*1km的小块存在数中, 四叉树的是将中国分为四块, 每块再划分四块, 知道划分为最小块, 之后我们新增商户或者查询的时候都可以在树中查询

选取上面视频连接的部分片段方便各位理解

查询的时候,我们根据用户位置以及用户筛选的位置, 对四叉树的节点进行遍历, 判断是否相交, 如果相交. 再对相交节点的子节点进行遍历, 与哪些子节点相交. 一直遍历到叶子节点, 之后将叶子节点所有的数据返回即可

另外, 我们可以以县作为根节点, 这样深度更小, 查询更快

业界通用解决方案:Geo Hash

关于geohash网上有更为详细的文章，这里制作简单概述，地图的经纬度范围分别为［-180，180］，［90， -90］，这里我们以经度为例，将经度分为［-180，0］，［0，180］，有一个点经纬度为［-121，34］，用1表示在［-180，0］区间，0表示［0，180］区间，那么这个点表示为1，之后可以看到这个划分太粗糙了，我们继续对该点位于的区间对半分，分别为，［-180，-90］，［-90，0］，同样1表示在左边区间，0表示在右边区间，这里第二位仍然为1，继续划分左区间，划分结果为［-180，-135］，［-135，-90］，1表示在左区间，0表示右区间，这次第三位为0，因此通过110，我们划分三次，就可以知道该经度的范围了，同理纬度也按照同样方式获取，之后将维度放奇数为，径度放偶数位，进行base32编码，5位一编码，就能获取一串字符串，这串字符串就是该点所处的区域，想要更精准我们只需要划分更多次，就行了，经纬度各划分25次后，geohash位数经过编码后为10，这时候误差为0.6米，几乎不影响使用，如果需要更高精度，可以继续划分

另外geohash检索时常见的边缘问题，因为geohash是按矩形块检索的，如果一个矩形块内有a，b两点，b与a的距离为10km，相邻矩形块有c点，c与a的距离为5km，由于a与b前缀编码相同位数更多，将会认为a与b的距离更近，因此为了避免边缘问题，我们在检索时，还要将相邻矩形块也一起遍历，，也就是看似在第三层矩形中找距离最近的点实际上由于边缘问题，我们应该在第二层找最近节点

面试腾讯技术创作特训营S9

0 人点赞