Proximity Service 设计解析：用 GeoHash 索引实现「附近餐厅」搜索-平芜编程栈

后端
文档
教程

【免费下载链接】system-design-101

Explain complex systems using visuals and simple terms. Help you prepare for system design interviews.

项目地址：https://gitcode.com/GitHub_Trending/sy/system-design-101

在 Yelp、Google Maps 这类应用中，「帮我找附近的餐厅」是最高频的需求之一。本指南基于 system-design-101 仓库中的 proximity-service.md，拆解这类位置服务（LBS，Location-Based Service）背后的两大核心服务，以及让「附近查询」变快的核心武器——GeoHash 空间索引算法。读完本文，你将掌握从经纬度存储、GeoHash 编码规则到前缀匹配 SQL 查询的完整设计链路，并能理解其局限与替代方案。

一、场景拆解：附近餐厅搜索涉及哪些服务

围绕「给定一个位置和半径，返回附近餐厅列表」这个需求，系统可以拆成两个关键服务：

服务	职责
Business Service（业务服务）	维护餐厅信息：新增 / 删除 / 更新餐厅数据；供用户查看餐厅详情
Location-based Service（LBS，位置服务）	给定半径（radius）与位置（location），返回附近餐厅列表

两个服务各司其职：Business Service 负责数据面的写入与详情查询，LBS 负责地理查询面。LBS 的性能瓶颈不在业务逻辑，而在「如何在海量餐厅数据中快速找到某个区域内的点」——这本质上是一个空间索引问题。

二、核心难题：经纬度到底该怎么存？

一个直觉的做法是：把每家餐厅的经纬度（latitude / longitude）直接存进数据库，查询时计算你与每家餐厅之间的距离，再筛选出半径范围内的结果。

这个方案在数据量小的时候可行，但问题也很明显：

需要遍历所有餐厅记录，逐条计算与查询点的距离；
距离计算本身有三角函数开销，且无法利用数据库索引做剪枝；
餐厅数量达到千万级时，这就是一次近乎全表扫描的查询。

也就是说：单纯存经纬度 + 暴力距离计算，查询效率极差。原文档明确指出这种方式的查询非常低效（"The query will be very inefficient when you need to calculate the distance between you and every restaurant"）。

解决思路是：先把空间按区域切分，让查询只落到少数几个区域，而不是遍历全量数据。GeoHash 就是用来实现这种空间切分与编码的经典算法。

三、GeoHash 算法：把二维坐标编码成一维前缀

GeoHash 的核心思想：把地球这个二维球面递归地切成越来越小的网格，并给每个网格一个字符串编码；编码前缀相同的网格，在地理位置上彼此邻近。这样「找附近的点」就变成了「匹配字符串前缀」。

第一步：用本初子午线和赤道切出四个象限

首先用经度（本初子午线）和纬度（赤道）把地球切成四个象限，并用二进制位标记：

维度	范围	编码
纬度	[-90, 0]	0
纬度	[0, 90]	1
经度	[-180, 0]	0
经度	[0, 180]	1

第二步：递归细分成更小的网格，经纬度位交替编码

对每个网格继续一分为四（再切一次经度与纬度），不断细化。关键编码技巧在于：每个网格的编码由经度位和纬度位交替组成——先放经度位，再放纬度位，如此往复。

例如，一个经过两层划分得到的网格，其编码可以形如01：第一位来自经度，第二位来自纬度。编码每多一位，网格就细化一层，GeoHash 字符串越长，表示的空间范围越小、精度越高，同时相同前缀的两个点空间距离越近。

这样，所有餐厅的经纬度坐标都被映射成一个个网格编码字符串，存入数据库的一张索引表（如geohash_index）中。

四、查询落地：用前缀匹配代替全量距离计算

当用户发起「找附近餐厅」请求时，LBS 先根据用户的经纬度算出其所在网格的 GeoHash 编码（即目标网格的前缀），然后用前缀去数据库中做范围查询。

原文档给出的查询示例：

SELECT * FROM geohash_index WHERE geohash LIKE '01%'

LIKE '01%'意味着：取所有 GeoHash 编码以01开头的餐厅记录——它们都落在同一个大网格内，也就是用户附近的区域。相比逐条计算距离，这种查询可以借助数据库索引（对geohash列建索引，前缀命中）大幅缩小扫描范围。

之后，LBS 再对这批候选结果做一次精确的距离计算与半径过滤，就能返回最终的附近餐厅列表。GeoHash 负责「快速缩小范围」，精确距离计算负责「最终把关」，两者配合是常见的工程实践。

五、GeoHash 的局限与边界问题

GeoHash 并非完美方案，原文档明确指出其核心局限：

网格内数据分布极不均匀：纽约市中心的一个小网格可能挤满几百家餐厅，而海洋里的大网格可能一家也没有。固定网格粒度无法适配密度的剧烈变化，导致查询负载不均。
边界效应：两个地理上非常接近的点，若恰好落在相邻网格的边界两侧，它们的 GeoHash 前缀可能完全不同，前缀查询会漏掉这些本应「在附近」的结果。实践中通常需要查询目标网格及其周围一圈相邻网格，再统一做距离过滤。

这些局限说明：GeoHash 更适合密度相对均匀、精度要求不苛刻的场景；面对密度极端不均或需要精确近邻的场景，需要更复杂的算法。

六、仓库中的替代方案：Quadtree 与 R-Tree

有趣的是，本仓库把 GeoHash 和它的替代方案分别收录为两篇姊妹文档，可以对照学习：

Quadtree（四叉树）：见 quadtree.md。它把世界地图作为根节点，递归四等分，直到每个叶子节点内的商家数量不超过阈值（如 100 家）。查询时从根节点遍历到查询点所在的叶子节点；若该叶子内商家不足，则向相邻叶子扩展补齐。Quadtree 是内存数据结构（非数据库方案），在每台 LBS 服务器启动时构建。针对大规模数据（文档提到约 2 亿商家规模），构建可能耗时数分钟且构建期间服务器无法服务流量，因此上线时建议小规模分批滚动发布，避免大面积服务中断（brownout）。
R-Tree：见 8-data-structures-that-power-your-databases.md。文档将其列为数据库中常用的索引结构之一，适用于多维搜索与最近邻查找，许多地理数据库用它做空间索引。

维度	GeoHash	Quadtree
存储形态	字符串编码，存数据库 + SQL 索引	纯内存树结构，LBS 服务器启动时构建
空间划分	固定网格递归二分（经纬交替）	按商家密度递归四等分，自适应
查询方式	前缀匹配（LIKE）缩小范围	遍历树到叶子，不足时向邻居扩展
主要短板	密度不均、边界漏检	构建耗时长、无法直接持久化

可以看到，GeoHash 的优势是简单、可持久化、可直接用 SQL 索引；Quadtree 的优势是按数据密度自适应划分。真实系统常按数据规模与查询模式组合使用，甚至进一步引入 design-google-maps.md 中描述的地理编码（Geocoding）与路径规划服务来完善整套地图/位置能力。