系统设计：四叉树与 GeoHash
原文：
towardsdatascience.com/system-design-quadtrees-geohash-5b896b975262
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5979ffdcbfe489e84bc8f684cde2911e.png
简介
Google Maps 和 Uber 只是众多处理地理数据的最流行应用的一些例子。存储世界上数百万地点的信息迫使它们高效地存储和操作地理位置，包括距离计算和最近邻搜索。
所有现代地理应用都使用由经度和纬度表示的对象的二维位置。虽然将地理数据以坐标对的形式存储可能看起来很天真，但这种方法存在一些陷阱。
在这篇文章中，我们将讨论朴素方法的潜在问题，并讨论另一种用于加速大型系统中数据操作的现代格式。
注意。在这篇文章中，我们将把世界表示为一个大的平坦二维矩形，而不是三维椭圆体。经度和纬度将分别用 X 和 Y 坐标表示。这种简化将使解释过程更容易，而不会遗漏主要细节。
问题
让我们想象一个数据库，它存储了所有应用对象的二维坐标。一个用户登录到应用中，想要找到最近的餐厅。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/e87b88719f0a9732c3c6901f564723d9.png
表示用户（节点 u）和位于邻近区域的其他对象的地图。目标是找到所有位于用户距离 d 以内的最近节点。
如果坐标简单地存储在数据库中，那么回答这类查询的唯一方法就是线性遍历所有可能的对象并过滤出最近的那些。显然，这不是一个可扩展的方法，在真实应用中搜索会非常慢。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/60695b88768d780fdb8cad6cf96a9d09.png
线性搜索包括计算到所有节点的距离并过滤最近的节点
SQL 数据库允许创建一个索引——一种建立在表的一定列上的数据结构，通过该列的键加速搜索过程。
另一种方法包括在坐标列之一上创建索引。当用户执行查询时，数据库可以在 O(1)时间内检索到表中对应于用户当前位置的行的位置。
多亏了构建的索引，数据库也可以快速找到具有最近坐标值的行。然后，可以取出一组这样的行，然后过滤出那些从用户位置到总欧几里得距离小于一定搜索半径的行。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/7103072815c8229a11eaeb1edb0559fe.png
在包含节点 Y 坐标的列上建立索引。因此，快速找到一组 Y 坐标与给定节点最近的节点变得非常迅速。然而，搜索过程没有考虑任何关于 X 坐标的信息，这就是为什么搜索结果必须随后进行过滤。
虽然所描述的方法比之前的方法更好，但需要时间来过滤最近距离的行。此外，也可能存在最初选定的最近坐标的行实际上并不是离用户位置最近的行的情况。
单个表不能同时有两个索引。这就是为什么为了解决这个问题，两个坐标应该被表示为一个单一的组合值，同时保留距离信息。这一目标正好通过下一节讨论的四叉树实现。
四叉树
四叉树是一种用于将二维空间递归分割成四个象限的树形数据结构。根据树的结构，每个父节点可以有 0 到 4 个子节点。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/1644023c821849d58bdcf4097ec8d1c6.png
四叉树格式中的地图表示。使用的层级越多，精度越高。
如上图所示，当前级别的每个正方形在下一级被分成四个相等的子正方形。因此，编码第i级的单个正方形需要i2位。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/3818dd7a8442695644a6bdfde48a476c.png
四叉树可视化
如果以这种方式将地理地图分割，那么我们可以用自定义的位数来编码其所有子部分。在四叉树中使用更多的层级，精度就越好。
属性
四叉树特别适用于地理应用，具有以下优点：
由于其结构，四叉树允许快速树遍历。
用来编码地图上两个点对的两字符串的共同前缀越大，它们就越接近。然而，在边缘情况中，这并不成立：一对点可以非常接近，但共同前缀很小。尽管边缘情况会发生，但并不常见：它们只发生在两个小象限位于另一个大象限的边界两侧时。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/56369a1e7625e7ed8350757bfc2b882b.png
边缘情况示例：边界不同侧的较小象限在其前缀中只有 1 个共同字符
- 如果一个象限由字符串 s₁s₂…sᵢ表示，那么它包含的所有子象限都由字符串 x 表示，例如 s₁s₂…sᵢ < x < s₁s₂…sⱼ，其中 sⱼ是 sᵢ在字典顺序中的下一个字符。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5c28756136db09acae24353f424152a5.png
在四叉树中按字典顺序排列有助于快速识别包含在较大区域内的所有子区域
优点
四叉树的主要优点是地图上的每个位置都由一个唯一的字符串标识符表示，该标识符可以作为一个单独的列存储在数据库中，这使得在四叉树字符串上构建索引成为可能。因此，给定任何表示地图上区域的字符串，它变得非常快：
上移到更高的级别或下移到更低的级别；
访问该区域的全部子区域；
找到同一级别上所有 8 个相邻区域（除了边缘情况）。
GeoHash
在大多数实际的地理应用中，使用的是 GeoHash 格式，这是对四叉树格式的轻微修改：
地理区域由矩形而不是正方形划分；
区域被划分为超过四个部分；
地图上的每个对象都由一个字符串编码，该字符串采用“base 32”格式，由数字 0-9 和除“a”、“i”、“l”和“o”之外的小写字母组成。
尽管有这些轻微的修改，GeoHash 仍然保留了上面描述的四叉树的重要优点。
下表显示了每个 GeoHash 级别与矩形尺寸之间的对应关系。在大多数情况下，级别 9 和 10 已经足够在地图上给出非常精确的近似值。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/7033af1e4d0342bace899d6a3926b0cd.png
GeoHash 编码级别与矩形尺寸之间的对应关系
在地图上找到最近的对象
如果我们在地图上有一个对象，我们可以通过以下算法使用它找到距离 d 内的最近对象：
- 将对象转换为 GeoHash 字符串 s。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2f67b455ea7d950a4a9761a783a44656.png
在这个例子中，我们希望找到所有位于蓝色节点 d = 500 m 范围内的对象
- 找到第一个最小的 GeoHash 级别 i，其大小大于所需的距离 d。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d683151fea10ff4e47f0d252c80714f2.png
级别 6 是第一个其宽度和高度都大于搜索半径 d 的级别
- 取字符串 s 的前 i 个字符（以表示包含初始对象在级别 k 的矩形）。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d3309ef51016abf538ccbab9d1b4bf1a.png
找到字符串 s[0 … i – 1]周围的 8 个相邻区域。
找到初始区域和相邻区域中的所有对象，并过滤掉那些与初始对象距离小于 d 的对象。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b211d5a197deb369f6f292891218b197.png
在搜索过程中，必须考虑矩形 97sy3k 及其 8 个相邻矩形内的所有对象。然后对所有候选对象进行线性过滤，以找到满足距离条件的对象。
结论
快速导航是使用数百万用户和地点数据的地理应用的关键方面。实现这一目标的关键方法包括创建一个单一的索引标识符，它可以隐式地表示纬度和经度。
通过继承四叉树最重要的属性，GeoHash 服务器作为一个此类方法的绝佳例子，在实践中确实实现了出色的性能。它的唯一弱点是当两个对象位于将它们分开的大边界两侧时，会出现边缘情况。尽管它们可能会对搜索效率产生负面影响，但在实践中边缘情况并不常见，这意味着 GeoHash 仍然是地理应用的顶级选择。
如果你对机器学习熟悉，并想了解更多关于在嵌入中进行可扩展的相似性搜索的优化方法，我建议你阅读我关于此主题的其他一系列文章：
相似性搜索
资源
四叉树 | 维基百科
Geohash | 维基百科
除非另有说明，所有图像均为作者所有。