揭开附近的“人”神秘面纱：初识GeoHash算法

开发运维 2023-07-14 大猫手机阅读

一、何为附近的“人”

WX摇一摇附近的妹子、DY直播推荐附近的人、DD推荐附近的出租车、MT推荐附近的美食，我们平时用的APP是如何向我们附近的“人”的呢？为了揭开它们什么的面纱，今天我们就去认识下空间索引：GeoHash算法。

举个实际的场景：当我们点开一个外卖的app就能看到自己附近的餐厅，那我们有没有想过这是怎么实现的呢？come on~

首先我们能想到的就是把所有餐厅的经纬度存下来，然后当用户选择附近餐厅是，我们先获取用户的经纬度，然后到数据库中查出所有的经纬度，依次计算它们和用户间的距离。最后根据用户输入的距离范围过滤出合适的餐厅，并根据距离做一个升序排列。这样貌似能查出附近的餐厅，但是餐厅的数量这么多，直接全查出来内存也要爆掉，即使分批处理计算量也十分大。这样用户等待的时间就会特别长。那有什么办法能减少我们的计算量呢？很简单，我们应该只计算用户关心的那一片数据，而不是计算所有的。例如用户在北京，那完全没必要计算海南，黑龙江，新疆，浙江等其它地区的数据。如果我们能快速定位到北京直至某个区，那么我们的计算量将大大减少。我们发现这其实就是索引的功能，但是MySQL对这种二维的地理位置的索引支持并不友好（mongodb有直接的地理位置索引），它对一维的像字符串这样的支持很好。那如果我们的数据在MySQL中，有没有什么方法能将我们的二维坐标转换为一种可比较的字符串呢？这就是我们今天要介绍的geohash算法。

geohash简单来说就是将一个地理坐标转换为一个可比较的字符串的算法。不过生成的字符串表示的是一个矩形的范围，并不是一个点。比如西二旗地铁附近这一片矩形区域就可以用wx4eyu82这个字符串表示，并且越靠前的编码表示额范围越大，比如中国绝大部分地区可以用w这个字母表示的矩形区域内。像wx4eyu82表示的区域一定在wx4e表示的区域范围内。利用这些特性我们就可以实现附近餐厅的功能了，比如我们希望查看西二旗地铁附近的餐厅就可以这样查询：select * from table where geohash like 'wx4eyu82%'; 这样就可以利用索引，快速查询出相关餐厅的信息了。并且我们还可以用wx4eyu82为key，餐厅信息为value做缓存。

二、地理位置推荐

基于地图的空间搜索使用经度（longitude）和纬度（latitude）作为基本的搜索条件进行地理信息的相关检索和查询。其实现方式一般包括以下一种实现方式：

在数据库表中将经度（longitude）和纬度（latitude）分别以两个不同的列进行存储，通过对经度（longitude）和纬度（latitude）两列建二元索引，提供对经度（longitude）和纬度（latitude）的检索。这种方式简单粗暴，可以满足对小规模的数据进行经纬度的检索。但是，在地图搜索相关的应用中，地理信息相关的记录的数据量会很多，二元索引的速度应该不会很理想，再者，基于地理信息的搜索行为相关的搜索基准点相对比较稀疏，数据库的缓存效果也不会太理想。

Geohash：通过这种编码方式，可以将经度（longitude）和纬度（latitude）值转换为一个基于base32编码的串，一方面可以实现对地理信息的一元索引；另外，地理上相近的点通过这种编码方式编码之后所得的串的前缀相同（当然会有特例，也就是一些边界条件，本文后面讲描述；前缀长度根据表示精度的不同而不同）。这样，要实现"搜索给定点附近的其他点"时，只需要将该参照点按照Geohash进行编码，按照精度要求从所得编码串中选取一定长度的字串作为前缀进行搜索，这样就可以很方便的实现该功能。