系统设计：四叉树与 GeoHash

原文towardsdatascience.com/system-design-quadtrees-geohash-5b896b975262https://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.pngGeoHash 编码级别与矩形尺寸之间的对应关系在地图上找到最近的对象如果我们在地图上有一个对象我们可以通过以下算法使用它找到距离 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 | 维基百科除非另有说明所有图像均为作者所有。