《系统设计面试》（卷 2）¶
阅读信息
- 链接：https://github.com/Admol/SystemDesign
- 评分：⭐️⭐️⭐️⭐️⭐️
- 时间：6/30/2026 → 6/30/2026
- 读后感：继续系统的硬核之旅，结合 AI 能深入了解不同领域的解决方案，让自己具有更加广阔的视野。集百家之长，吸收其设计思想，用优雅的方式解决问题。
临近服务¶
API 设计¶
用户端点
GET /v1/search/nearby
请求参数
| 字段 | 描述 | 类型 |
|---|---|---|
| latitude | 给定位置的纬度 | decimal |
| longitude | 给定位置的经度 | decimal |
| radius | 可选。默认为 5000 米 (约 3 英里) | int |
数据模型¶
LBS 服务的特点：
- 读请求很大（搜索附近商家，查询商家详情等），但写请求极低
- QPS 很高，尤其在密集区域的高峰时段
- 无状态服务，易于水平扩展
空间索引¶
常用的空间索引包括：
- Hash: 均匀网格、GeoHash、Google S2、Uber H3、笛卡尔层等
- Tree: 四叉树、R 树等
GeoHash¶
GeoHash 根据本初子午线和赤道将地球划分成\(4\times8\)的网格，每个网格又能被细分为\(4\times8\)的网格，层层递进，总共有 12 层（精度因子），如表格所示。精度因子决定了网格的大小，只需要调整 geohash 长度即可实现精度的调整。通常 4~6 位长度的 geohash 就足以满足需求。
GeoHash 精度 
GeoHash 半径精度
GeoHash 通常使用 base32 表示，如 1001 10110 01001 10000 11011 11010 -> 9q9hvu。GeoHash 保证两个 GeoHash 之间共享前缀越长，它们就越接近，但两个相邻的位置可能完全没有共享前缀，比如本初子午线两侧的位置。
关于 GeoHash 的视频讲解：https://b23.tv/BV1x44y1L7HJ
GeoHash 简单、易于实现，在许多简单的场景下效果不错，但缺点也很明显：
- Z 阶曲线边界突变问题：虽然可以通过同时查询目标点所在的网格以及周边相邻的 8 个网格来缓解，但增加了复杂度。
- 墨卡托投影畸变：GeoHash 采用墨卡托投影将地图划分为矩形，导致纬度越高，畸变越严重，这种不均匀性导致高纬度计算开销很大。Uber H3 采用的六边形网格更加均匀。
四叉树¶
四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四叉树常应用于二维空间资料的分析与分类。通常用于通过递归地将二维空间划分为四个象限 (网格) 来对其进行分区，直到网格的内容满足某些标准。
四叉树是空间驱动的，按固定空间边界递归等分（而非根据数据密度自适应），因此分布式存储中很少直接将四叉树节点路径用作分片键：
- 如果某些区域（如市中心）POI 非常密集，四叉树在这些区域就会分得很深；而郊区则分得很浅。
- 这种结构不均匀性使得它很难直接用作分布式数据库的分片键，容易导致数据倾斜。
- 相比之下，GeoHash / S2 / H3 可以将坐标直接转化为一个固定的字符串或 64 位整数，更容易进行分布式哈希和水平扩展。
四叉树非常适合做碰撞检测、视口裁剪（Window Query）和游戏 AOI（Area of Interest）管理
R 树¶
二维矩形上的 R 树 
用 ELKI 做出的三维 R* 树视觉效果图（每个立方体是一个目录页）
R 树的“R”代表“Rectangle（矩形）”，其核心思想是聚合距离相近的节点并在树结构的上一层将其表示为这些节点的最小外接矩形，这个最小外接矩形就成为上一层的一个节点。R 树非常适合解决附近查询问题，比如附近的医院、餐馆等。
与 B 树类似，R 树也是平衡树（所有叶子节点都在同一深度），R 树还有 R*树和 R+ 树等变体。
在 PostgreSQL (PostGIS)、MySQL Spatial、SQLite (SpatiaLite) 和 Oracle Spatial 等主流空间数据库中，默认的空间索引基本上都是 R 树（或其变体，如 PostGIS 的 GiST 索引）。原因如下：
- 完美契合现实中 POI 数据的不均匀分布
- 数据特征：城市的商店和银行分布是极其不均匀的（市中心 CBD 极度密集，郊区和乡村极度稀疏）。
- R 树是“数据驱动”（Data-driven）的：它的外接矩形（MBR）是根据实际数据点动态收缩和扩张的。在市中心，R 树会形成许多紧凑的小矩形；在郊区，则形成巨大的稀疏矩形。这保证了树的深度是平衡的（类似 B-Tree），在任何位置进行“附近搜索”都能保持稳定的 \(O(logN)\) 检索性能。
- 四叉树是“空间驱动”（Space-driven）的，不管有没有数据，它都会机械地将空间一分为四。在市中心，为了区分密集的商店，四叉树会分裂得很深，导致树结构严重失衡；而在郊区，又会产生大量没有任何数据的空节点，造成内存和检索路径的浪费。
- 最近邻查询（KNN）和窗口查询效率极高
- 搜索“附近 10 个银行”（KNN 检索）是 LBS 的核心需求。在 R 树中，配合分支限界算法，可以非常高效地剪枝，快速排除那些不可能包含最近邻点的树枝。
- 工业界的学术和工程测试表明，对于此类邻近查询，R 树的平均查询速度和稳定性显著优于四叉树
尽管在数据库层面 R 树占据统治地位，但在以下场景中，四叉树依然是开发者的首选：
- 前端地图渲染与点聚合
- 当用户缩放地图时，前端需要展示“当前屏幕视口内的商店”，或者在地图放大时将重叠的图标展开。
- 四叉树结构简单、易于在内存中构建。在前端（如浏览器或移动端 App）中，可在内存中快速构建一棵四叉树，能极快地完成视口裁剪（Window Query）和图标聚合渲染（注意：Mapbox 的 Supercluster 点聚合库底层使用的是 kd-tree，而非四叉树）。
- 高频更新的内存缓存
- R 树的痛点在于更新开销大：因为 R 树需要时刻保持平衡（类似 B 树的合并与分裂），当有大量位置频繁变动的数据（如外卖骑手、打车软件中的车辆）需要实时更新时，R 树的维护成本很高。
- 四叉树的边界是静态固定的：插入或删除点时，不需要像 R 树那样重新调整父级矩形的大小，因此它的写入和更新速度显著快于 R 树。对于完全常驻内存的高频读写缓存，四叉树（或其变体）是一个更轻量、低延迟的选择。
Google S2¶
Google S2 使用希尔伯特曲线（Hilbert Curve）将球体映射到一维索引，比 GeoHash 的 Z 阶曲线具有更好的空间邻近性（较好地解决了突变问题）。希尔伯特曲线有一个非常重要的特性：在希尔伯特曲线上彼此接近的两个点在一维空间中也是接近的。在一维空间上的搜索比在二维空间上的搜索效率要高得多。S2 被 Google Maps、Tinder、Foursquare 使用，非常适合地理围栏。
Uber H3¶
Uber H3是一个开源地理空间索引系统，它将地球划分为一系列离散的六边形网格，每个网格都有一个唯一的标识符（Index）。在网约车、外卖配送等需要频繁计算“配送半径”、“区域供需关系”、“动态调价”的场景中，H3 几乎成为了行业标准。
对比¶
| 技术方案 | 主要应用场景 | 优势 | 劣势 |
|---|---|---|---|
| GeoHash | 基础 LBS 应用、Redis 快速附近人检索、简单文本索引。 | 简单、数据库兼容性极好。 | 存在边界突变，高纬度网格变形严重。 |
| Google S2 | 全球化复杂 LBS、大规模空间几何计算（多边形求交集等）、地理围栏。 | 空间邻近性极佳，支持多层级无缝切换。 | 实现较复杂，上手成本稍高。 |
| Uber H3 | 骑行/网约车调度、外卖配送范围、热力图分析、动态定价。 | 六边形网格无方向偏差（邻居等距），最适合做空间数据聚合和分析。 | 六边形无法完美嵌套（大六边形不能完美切分为若干个小六边形），层级转换时存在微小误差。 |
| 四叉树 (Quadtree) | 地图瓦片渲染、游戏 AOI（Area of Interest）、内存高频空间碰撞/检索。 | 结构简单，适合内存计算；空间边界固定，写入更新速度快。 | 空间驱动非数据驱动，数据分布不均时树极度失衡；难以直接用于分布式分片。 |
| R 树 (R-Tree) | 数据库空间索引（PostGIS、MySQL Spatial）、POI 范围查询与 KNN 检索。 | 数据驱动，自适应数据分布；KNN 查询效率极高，是主流空间数据库的首选索引。 | 插入/删除开销大，树重平衡成本高，不适合高频写入场景。 |