39｜Geohash：点外卖时我们是如何查找到附近餐厅的？

Aug 9, 2022

39｜Geohash：点外卖时我们是如何查找到附近餐厅的？-业务开发算法50讲-极客时间



下载APP





关闭

渠道合作

推荐作者

39｜Geohash：点外卖时我们是如何查找到附近餐厅的？

黄清昊 · 业务开发算法50讲

课程介绍



讲述：黄清昊

时长10:17大小9.39M



你好，我是微扰君。
今天我们来聊一聊另一个和索引相关的非常有趣的问题：“地理位置检索”问题。
身处移动互联网时代，我们的衣食住行少不了各种用到地理位置信息的 APP。比如周末想和朋友小聚一下，不知道去哪，我就会在美团点评上检索餐厅或者休闲场所，除了看评价，也经常会按照距离排序或者限定距离范围，找距离近、评价也高的地方，这样通勤成本就可以低很多。
再比如许多基于地理位置推荐用户的社交类 APP，或者摩拜单车这样的 APP 里，也都有类似的地理位置检索的需求。
作为一个软件工程师，不知道你有没有思考过这背后用了什么样的算法呢？今天就让我们来一探究竟。
地理位置检索来明确一下这里要说的地理位置检索问题的讨论范畴。
所谓检索，自然是说从数据中找到一些有指定特征的数据。比如，在数据库中做一个 select 的查询就可以认为是一种检索行为，语句中如果有 where 的子句，就说明我们的查询是有条件的。
地理位置检索，正是从这样一些含有地理位置信息（通常用经纬度表示）的元素中，查询满足特定地理位置条件的元素的行为。比如在存有店铺信息和对应经纬度的数据库中，查询某个经纬度坐标 3km 之内的店铺，或者进一步按照距离远近进行排序。这就是我们今天主要讨论的问题。许多数据存储系统也都支持了相关的查询实现，比如 MongoDB、Redis 等等。
首先，我们要知道的是，在所有的数据库，索引，在地理位置检索中并不是必须的，因为我们总可以通过遍历一遍数据库中所有的元素，来进行数据的过滤或者排序。
但是，在数据量很大的时候，这样的低效查询显然是不尽如人意的。试想，美团这个级别的互联网应用，如果在每个用户按距离查询商铺的时候，都进行全量的过滤，估计再大的数据中心也不可能在几十毫秒内完成大部分查询。
所以建立类似索引的机制是必须的，那我们具体该怎么做呢？
分块思想由于地理位置检索问题历史悠久，又很有现实意义，人们对它的讨论还是比较充分的，解决方案也很多，但其中大部分想法都源于一个非常浅显的直觉——分块思想。
分块思想，在很多时候，都可以帮助我们降低算法的时间复杂度，其实这也是某种用空间换时间思想的应用。通过以块为单位记录一些额外的信息，就能加速查询或者计算的时间。
对于地理位置检索的场景，由于地理位置是二维的，我们无法对距离使用类似于 B+ 树这样的一维索引加速查询（除非，我们针对每个坐标都建一个其他店铺到该坐标距离的索引，这显然是不现实的），但是，直接遍历的时间复杂度又太高，有没有什么办法可以不用全量遍历数据，而是部分遍历数据呢？
当然是可以的。看个具体例子帮助分析。假设，现在有一个数据库存储了全国的店铺，如果我们要查询距离五道口地铁站（坐标 39.9929° N, 116.3379° E）最近的几个剧本杀店。
在查询的时候，即使采用全部遍历一一比较的策略，我们也没有必要真的遍历世界上所有的店铺，只需要选择北京市海淀区的店铺就可以了。这样我们就过滤了大量不可能是查询目标的数据，提高了查询效率，所需要的代价仅仅是为每个数据增加一个“省 - 市 - 区”的标签而已。
这样的标签，实际上可以认为是对地理位置做了一个以“区”为粒度的分块，在检索距离最近的标签时，我们直接查找同一个区内的就行。
如果觉得同一个区内的店铺还是太多了，遍历起来时间成本依旧很高，那我们就可以把分块的粒度划得更细，还可以用更规则的方式。比如把整个地球分成很多个规则的方块，检索临近店铺的时候，只需要找到目标的分块，然后遍历分块内的店铺即可：
图片来源网络
具体每个块要分到多细，就需要看具体的场景了，指导思想就是让每个最小块内的元素不要太多，这样检索的时候效率就会大大增快了。
不过讲到这里，细心的你应该会发现一个问题，很多时候如果只检索和目标坐标同一个块内的元素是不正确的，尤其是目标坐标在某个块边缘的时候，就像这样，我们要查询离 A 地点最近的店铺：
A 所在的分块在图中被红色边界标出来了。对于 A 地点来说，如果我们想找离 A 最近的店铺，只在红色块中查询就是不正确的。因为显然图中的 B 店铺到 A 的距离，比 C 店铺到 A 的距离更近，但 B 却不在 A 所处的分块范围之内。
不过，处理方式其实也很简单，在检索的时候，不只检索和目标坐标处于同一个分块下的元素，也检索和目标分块相邻的 8 个分块内的元素，再根据查询要求进行排序或者选择就可以了。
思想是不是很简单清晰呢～
Geohash有了基本思想，具体如何进行这样的分块和打标，并将其落地到一个数据存储查询的系统，比如数据库中呢？
一种常见的实现就是 Geohash 算法，它将地理位置的二维信息映射到一个可比较且易于存储的字符串中，检索时，基于这个字符串进行比较查询，实质就是分块思想的实现。Redis 中对地理位置检索也是基于 Geohash 实现的。
根据前面所说的，我们会对整个地图按层进行分块，而块信息最简单的表示方式当然就是一个编号了，Geohash 就采用了一种巧妙的编码方式，把二维信息转化成一维编码的时候，也极大保留了地理信息上的连续性。
我们知道，整个地球的经度范围和纬度范围分别是[-180,180]和[-90,90]，一个合法的坐标值当然坐落于这个范围之内。我们先看 Geohash 对纬度信息是如何处理的，同样以五道口地铁站的坐标（39.9929° N, 116.3379° E）为例来考虑这个问题。
先看纬度的分块思路。
Geohash 首先考虑这个坐标处于南半球还是北半球，如果是北半球，就用 1 来标记，反之就用 0 来标记。那显然，39.9929 属于[0,90]的范围，也就是北半球，应该用 1 标记，现在我们的纬度可取范围就缩小到了[0,90]。
然后我们再继续考虑 39.9929 纬度属于[0,45]还是[45,90]，如果属于[45,90]，用 1 标记，反之用 0。这个时候，我们发现 39.9929 属于[0,45]应该用 1 标记。
以此类推，如果我们不断地对纬度进行二分和选择，目标的纬度范围就会越来越接近 39.9929，我们也就可以得到一串二进制数，也就是将纬度均匀等分为 2 的幂次后我们处于哪一段区间的编号，而二分的次数越多，二进制的位数越高，我们定位的精度自然也就越高。
你可以看这段完整的编码过程结果：
[0,90] 1
[0,45] 0
[22.5,45] 1
[33.75,45] 1
[39.375,45] 1
[39.375,42.1875] 0
[39.375,40.7812] 0
[39.375,40.0781] 0
[39.7266,40.0781] 1
[39.9023,40.0781] 1
[39.9902,40.0781] 1
[39.9902,40.0342] 0
[39.9902,40.0122] 0
[39.9902,40.0012] 0
[39.9902,39.9957] 0
[39.9902,39.993] 0
如果我们将地图横切成 65536 份，五道口地铁站的目标纬度，就可以被确定在[39.9902,39.993]的范围内，编号写成二进制是 1011100011100000。
那同样的事情，也可以对经度做一遍，这样我们就相当于对整个地图进行了竖切，得到的编号是 1101001010111010：
[0,180] 1
[90,180] 1
[90,135] 0
[112.5,135] 1
[112.5,123.75] 0
[112.5,118.125] 0
[115.312,118.125] 1
[115.312,116.719] 0
[116.016,116.719] 1
[116.016,116.367] 0
[116.191,116.367] 1
[116.279,116.367] 1
[116.323,116.367] 1
[116.323,116.345] 0
[116.334,116.345] 1
[116.334,116.34] 0
现在，如果我们将两个编号按照某种方式拼接起来，是不是就可以将目标坐标确定在了一个很小的方块范围内了呢？
Geohash 就是这样做的。不过相比于直接把两个二进制拼接在一起，Geohash 非常聪明地采用了经纬度标号交替拼接的方式：“奇数位放纬度，偶数位放经度”，将两个编号信息组合在一起，这样在大部分情况下，两个编码接近的元素在真实地理位置上也会更接近一些。
为了让这个编码更加紧凑，精度范围更精确，Geohash 最终存储编码的时候选择了 base32 的字符串进行存储。
五道口的坐标，如果写成精度为 5 位的 Geohash 编码，也就变成了 wx4ex，是不是看起来非常简短呢？而这样简短的编码，在地图上却已经只是一块很小的区域了。你可以在这个网站（https://csxgame.top/#/）上查看，作者利用百度地图接口提供了一个 Geohash 可视化的工具。
总结我们今天学习了一种常见的地理位置检索的索引方式，Geohash。
作为一种非常经典的分块思想和空间换时间思想的应用，它通过将地理位置分块和巧妙的编码，让我们检索地理位置的时候，只需要在很小的范围内进行排序选择等操作。
编码中体现的分层思想，在计算机的系统中也是随处可见，比如文件系统中的多级索引数据块的建立方式，也和 Geohash 分层编码的方式有着异曲同工之妙，你可以好好体会。
课后作业分块思想也是算法面试中时常考到的知识点。比如力扣的307 区间和检索，我们就可以采用分块的思想解决，避免高阶数据结构如树状数组、线段树的使用，感兴趣的同学不妨去做做这道题：
欢迎你在评论区留言与我一起讨论，我们下节课见～

地理位置检索在移动互联网时代扮演着重要角色，而本文介绍了解决这一问题的算法——分块思想。地理位置检索需要从含有地理位置信息的数据中查询满足特定地理位置条件的元素，如按距离排序或限定距离范围。在大数据量情况下，全量遍历数据的低效查询显然不可取，因此建立类似索引的机制是必须的。分块思想通过以块为单位记录额外信息，加速查询或计算的时间，降低算法的时间复杂度。具体地，通过对地球分成规则的方块，检索临近店铺时只需遍历目标分块内的店铺，从而提高查询效率。文章还介绍了Geohash算法，它将地理位置的二维信息映射到一个可比较且易于存储的字符串中，实质上是分块思想的实现。Geohash通过将地理位置分块和巧妙的编码，让我们检索地理位置的时候，只需要在很小的范围内进行排序选择等操作。这种分层思想在计算机系统中也是随处可见，比如文件系统中的多级索引数据块的建立方式。总的来说，本文介绍了地理位置检索的重要性以及分块思想和Geohash算法在解决这一问题上的应用，为读者提供了对地理位置检索问题的有效解决方案。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

2022-08-09

赞 3

提建议

38｜倒排索引：搜索引擎是如何做全文检索的？

40｜垃圾回收：现代语言是如何自动管理回收内存的？

 写留言

全部留言(2)

最新
精选

拓山
2023-08-10 来自浙江
[然后我们再继续考虑 39.9929 纬度属于[0,45]还是[45,90]，如果属于[45,90]，用 1 标记，反之用 0。这个时候，我们发现 39.9929 属于[0,45]应该用 1 标记] 这句话写的有问题，头半句是说 [0,45] 要用0标记，怎么到了第二句又变成了[0,45]用1标记？
1
Kevin
2023-04-24 来自广东
恍然大悟，巧妙的算法

