OpenAI 兴趣点题目的完整解答：容量估算、geohash 编码与邻域搜索、四叉树、精确对比、精确 K 近邻查询、边界与极点情况、索引与细节分离、分片、缓存以及新鲜更新。

作者：The Forward Deployed 编辑团队已审阅

本文属于 OpenAI 系统设计题库。该题目能代表该轮面试的水平。分析与解答为本站原创。

问题描述

用户打开应用，看到附近的地点，可按类别筛选，并按距离或评分排序。该服务存储全球数亿个地点，并在远低于 100 ms 的时间内响应位置查询。商家可以编辑详情；新地点会出现；已关闭的地点会消失。

这道题有多个已知变体：基础位置搜索、精确 K 近邻、索引分片、更新新鲜度，以及对 geohash 或四叉树内部机制的深入追问。下面的解答覆盖了所有这些内容。

澄清问题

  • 有多少地点？ 练习场景：全球 5 亿个。
  • 查询速率？ 峰值每秒 100,000 次，以读为主。
  • 延迟？ p95 低于 100 ms。
  • 查询形态？ 半径范围内查询，例如 2 km，或 K 近邻查询，例如 10 个，可带类别筛选。
  • 更新速率？ 详情编辑频繁；位置移动和新地点出现较少。
  • 新鲜度？ 详情编辑在一分钟内可见；新地点在几分钟内可见。

位置搜索为什么难

普通数据库索引沿一个维度对值排序。而位置有两个维度：纬度和经度。基于纬度的索引能找到环绕全球的一条水平带；基于经度的索引则是一条垂直带。“在此点附近”两者都不是。

所以核心问题是把二维的邻近关系转换成一维索引能够查找的东西。Geohash 和四叉树是两个标准答案。它们在大多数情况下都能把相邻的点映射到相邻的键。而“大多数情况下”正是面试深入之处：恰好跨过单元格边界的点在空间上很近，在索引中却相距很远。

第二个问题是密度。曼哈顿每平方公里有数千家餐厅；撒哈拉沙漠则一家也没有。固定网格在一处太粗，在另一处又太细。

因此核心矛盾是索引的简单性与对密度的自适应性，同时两种方案都必须保证边界正确性。

flowchart LR U([User at lat, lng]):::user --> API[Search API]:::svc API --> GI[Geo index<br/>cell -> place IDs]:::store GI -->|candidates| API API --> DET[(Place details)]:::store API -->|sorted by distance| U classDef user fill:#e6efec,stroke:#315e55,color:#171717; classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;
核心思想。 地理索引将二维的邻近关系映射为一维的键。它几乎正确；设计必须处理好这个“几乎”。

关键概念

Geohash

按经度将世界对半划分并写下一个比特：西为 0，东为 1。然后按纬度对半划分：南为 0，北为 1。如此交替进行。将比特每五个一组，每组编码为一个 base-32 字符。每多一个字符，格子就更精细。同一格子内的点共享前缀，因此前缀范围扫描即可找到某个格子内的所有点。

字符数格子大小（赤道处近似值）
439 km × 19.5 km
54.9 km × 4.9 km
61.2 km × 0.61 km
7153 m × 153 m

四叉树

从覆盖整张地图的一个节点开始。当一个节点包含的地点数量超过设定值（例如 100 个）时，就将其拆分为对应四个象限的四个子节点。密集区域会变得很深、格子很小；空旷区域则保持较浅、格子很大。

Haversine 距离

球面上两点之间的大圆距离。计算成本低，对于附近结果的排序来说足够精确。

索引与详情分离

索引只需要地点 ID、位置和少量过滤字段。营业时间、照片、评论等详情数据更大且变更更频繁。将它们存放在独立的存储中，使各自可以独立扩展。

核心思想。 Geohash：固定格子、前缀键，易于存储和分片。四叉树：自适应格子、内存中的树。两者都需要在边界处进行邻居搜索。

需求

继续阅读之前。 请为两种查询形态写出需求。如果某个属性失效，用户最先注意到的是什么？

1.1 功能需求

  • 查找某点半径范围内的地点，可按类别筛选。
  • 查找距离某点最近的 K 个地点（精确结果）。
  • 展示地点详情：名称、地址、营业时间、评分。
  • 允许商家更新详情；添加和删除地点。

1.2 非功能需求

  • 延迟？ p95 低于 100 ms。
  • 吞吐量 峰值每秒 100,000 次查询。
  • 边界附近的正确性：不能因为附近地点位于相邻格子而漏掉它。
  • 新鲜度：详情编辑在一分钟内生效；索引变更在几分钟内生效。
  • 搜索可用性 99.99%。

1.3 约束与属性

正确的最近结果才是属性。 一个漏掉街对面咖啡馆的搜索会让用户失望。10 万 QPS 下的读取延迟是约束。 它迫使索引放入内存、详情放入缓存。

粗略估算

  • 地点：5 亿 × 每条约 1 KB 详情 = 500 GB 详情数据。分片存储可以承载。
  • 索引条目：5 亿 × (8 字节格子键 + 8 字节地点 ID + 几个字节的类别) ≈ 10 GB。这可以放进单台机器的内存，因此每个搜索副本都能持有完整索引。
  • 查询：峰值每秒 10 万次。如果一个副本每秒从内存服务 5,000 次查询，大约需要 20 个副本，再加上余量并分布到多个区域。
  • 详情获取：每秒 10 万次查询 × 20 条结果 = 每秒 200 万次详情读取；一个高命中率的缓存可以吸收大部分读取，因为热门地点会重复出现。
  • 更新：假设每天有 100 万次详情编辑（约每秒 12 次）和每天 10 万个新增或迁移的地点。写入负载微不足道。
关键思路。 索引足够小，可以复制到各处；详情更大，采用缓存。读取比写入高出几个数量级。

API 设计

继续阅读之前。 搜索响应应该包含完整的地点详情吗？

只包含结果列表展示的内容：名称、类别、评分、距离和缩略图。当用户打开某个地点时，再加载完整详情，例如营业时间和照片。这样可以让搜索响应保持小巧，并让详情缓存聚焦。

GET /v1/places/search?lat=37.7749&lng=-122.4194&radius_m=2000&category=cafe&limit=20
GET /v1/places/nearest?lat=37.7749&lng=-122.4194&k=10&category=cafe
  -> {results: [{place_id, name, category, rating, distance_m, thumb_url}]}

GET   /v1/places/:id
PATCH /v1/places/:id        (owner)   {hours?, phone?, ...}
POST  /v1/places            (owner or admin) {name, lat, lng, category, ...}
DELETE /v1/places/:id

数据模型

places (place_id, name, lat, lng, geohash6, category, rating, rating_count,
        address, hours_json, phone, updated_at, status)
        primary key place_id; sharded by place_id

geo_index (in memory on search replicas, rebuilt from places + change stream)
   geohash -> sorted list of (place_id, lat, lng, category, rating)
   or quadtree nodes with the same leaf payload

change_stream  (place_id, op, new_lat, new_lng, category, ts)   -- feeds replicas

把纬度和经度复制到索引中，搜索副本就能计算精确距离，而无需查询详情。

高层设计

5.1 基于纬度和经度的 SQL 范围查询

SELECT * FROM places WHERE lat BETWEEN :lat - d AND :lat + d AND lng BETWEEN :lng - d AND :lng + d;

使用单独的索引时，数据库会选择一个维度，扫描环绕全球的一条带状区域，再过滤另一个维度。在 5 亿行、每秒 10 万次查询的规模下，这实在太慢了。

5.2 修复 1：按 geohash 建索引

存储每个地点的 geohash 并为其建索引。查询时以某个精度计算用户的 geohash，使单元格大小接近搜索半径，然后扫描该前缀。这样扫描范围只覆盖一个小单元格。

5.3 修复 2：搜索相邻单元格

一个 20 米外的地点可能位于单元格边界另一侧，前缀完全不同。因此要搜索用户所在单元格及其八个相邻单元格，计算精确距离，按半径过滤，再排序。

flowchart TB
  subgraph Grid["Geohash cells around the user"]
    direction LR
    NW[NW neighbor]:::svc --- N[N neighbor]:::svc --- NE[NE neighbor]:::svc
    W[W neighbor]:::svc --- C["user's cell"]:::store --- E[E neighbor]:::svc
    SW[SW neighbor]:::svc --- S[S neighbor]:::svc --- SE[SE neighbor]:::svc
  end
  classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717;
  classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;

5.4 修复 3：内存索引服务

把索引从详情数据库中移出，放到将其保存在内存中的搜索副本里。详情则存放在独立的存储和缓存中。

5.5 修复 4：用于保持新鲜度的变更流

地点变更会发布事件。搜索副本在几秒内应用索引变更；详情编辑会使详情缓存失效。

5.6 组合后的设计

sequenceDiagram
  autonumber
  actor U as User
  participant A as Search API
  participant I as Search replica (in-memory index)
  participant C as Details cache
  participant D as Places DB
  U->>A: nearest k=10 near (lat, lng), cafe
  A->>I: query
  I->>I: user cell + 8 neighbors at precision p
  I->>I: exact distance, filter category, sort
  alt fewer than 10 within guaranteed radius
    I->>I: lower precision (bigger cells), repeat
  end
  I-->>A: 10 place IDs + distances
  A->>C: batch get summaries
  C-->>A: hits
  A->>D: misses
  A-->>U: results
关键思路。 在内存索引上进行 geohash 前缀扫描，始终包含相邻单元格，最后计算精确距离，并用变更流保持数据新鲜。

深入探讨

6.1 Geohash 详解

继续阅读之前。 手动把一个点编码到前几个比特，然后解释为什么附近的点通常共享前缀，以及什么时候不共享。

以旧金山为例，大约北纬 37.77°，西经 122.42°。先看经度：−122.42 位于东半区 [0, 180] 还是西半区 [−180, 0]？西半区：比特 0。再把 [−180, 0] 对半分：−122.42 位于 [−180, −90]：比特 0。然后是纬度：37.77 位于 [0, 90]：比特 1。依此类推，交替进行。每五个比特组成一个 base-32 字符；旧金山以

9q8y

.

两个点共享的前缀长度，恰好等于它们在迄今为止每一次分割中都落在同一侧的长度。距离很近的两个点通常如此。但分割线是固定的直线。位于分割线两侧、相距仅一米的两个点，从那一位开始以及之后的每一位都不同，因此它们的前缀很早就分道扬镳。最坏的情况是本初子午线或赤道：相距几米的点的 geohash 第一个字符就不同。这就是为什么每次 geohash 搜索都要包含相邻的格子。

精度选择：选择格子至少与搜索半径一样大的精度，使 3 × 3 的格子块能覆盖整个圆。对于 2 公里半径，精度 5（格子约 4.9 公里）可行；精度 6 的格子（约 1.2 公里 × 0.6 公里）就太小了。

边界情况：由于经线向两极汇聚，格子宽度向极点方向收缩，因此固定精度在高纬度覆盖的面积更小。相邻格子的计算必须能跨越 180° 经线回绕。这两点都要提到。

6.2 详解四叉树

在继续阅读之前。 为整个世界构建一棵叶子容量为 100 的四叉树。它在曼哈顿上空会达到多深？你如何存储它？

从整个世界作为根节点开始。任何包含超过 100 个地点的节点都分裂成四份。在海洋上空，根节点的象限保持为单个叶子。在曼哈顿上空，它不断分裂，直到每个叶子大约只覆盖一两个街区。深度随密度自适应，这正是其意义所在。

搜索：下探到包含用户的叶子，收集其中的地点。如果搜索圆跨越到相邻的叶子，也要访问它们：将每个附近节点的包围框与圆进行比较，只下探到与圆相交的框。

存储：5 亿个地点、每个叶子最多 100 个，意味着至少 500 万个叶子和几百万个内部节点。整棵树连同地点 ID 和坐标，几十 GB 内存即可容纳。启动时从地点表构建，并应用来自数据流的变更。持久化快照，以便副本快速重启。四叉树也可以存入数据库，以节点路径作为键，例如

0231

，这使它看起来非常像 geohash。

6.3 Geohash 还是四叉树

Geohash Quadtree
格子大小按精度固定随密度自适应
存储一个带普通索引的字符串列通常是内存中的树
更新修改一行的键插入可能分裂节点；删除可能合并节点
分片简单：每个分片负责一段前缀范围更难：树是单一结构；按顶层子树分片
密集区域每个格子地点多；需要更多过滤叶子保持均衡
稀疏区域空格子多；需扩大搜索一个大叶子
实现简单，到处都有现成库代码更多

好的回答会指出权衡并做出选择：为了简单和易于分片，在数据库中使用 geohash；或者在密度差异极大且精确的 K 近邻查询很重要时，在内存中使用四叉树。两者都说得通。有些系统使用结合了这两种思想的分层单元格系统。

区分回答好坏的关键：地理索引

弱：提到索引但讲不清机制

只说“用地理索引”或“用 PostGIS”，却无法解释其工作原理。

好：解释 geohash 及其邻近单元格

对位置进行 geohash 编码，根据半径选择精度，然后搜索 3 × 3 的邻域。

强：进行比较并处理边界情况

也解释四叉树，从密度、更新和分片方面进行比较，并处理边界、极点和 180° 经线。

6.4 精确 K 近邻

在继续阅读之前。 用户想要最近的 10 家咖啡馆。你搜索 3 × 3 的单元格，找到 12 家。这 12 家中最接近的 10 家一定就是真正最近的 10 家吗？

不一定。3 × 3 的区块是一个正方形，而真正第 10 近的咖啡馆可能刚好在区块之外，同时你的 12 家中有一家位于区块的远角。这个保证只在用户到所搜索区块最近边的距离范围内成立。

正确的循环：

  • 以某个精度搜索用户所在单元格及其邻近单元格。
  • 按精确距离对候选结果排序。
  • 设 r 为用户到所搜索区块最近边界的距离。任何距离在 r 以内的候选结果都保证是正确的。
  • 如果至少有 K 个候选结果在 r 以内，返回其中最近的 K 个。
  • 否则，降低一位精度（单元格变为原来的四到八倍大）并重复。

使用四叉树时，同样的保证来自最佳优先搜索：维护一个按节点到用户的最小可能距离排序的优先队列，当第 K 个候选结果比下一个节点的最小距离更近时停止。

6.5 分片与缓存

索引可以放进内存，因此最简单的扩展方式是复制：每个搜索副本持有整个索引，由负载均衡器分发查询。将副本部署在靠近用户的多个区域。

如果索引大到一台机器放不下，就按 geohash 前缀分片。一个查询会触及拥有其单元格的分片，通常是一个，偶尔在分片边界处是两个。热点区域（如大城市）会进行更细的分片拆分并配置更多副本。

按单元格和类别缓存热门查询，并设置较短的生存时间（如 60 秒）：同一街区的许多用户会在早上 8 点搜索咖啡。按地点 ID 缓存地点摘要。当地点发生变化时使对应的摘要失效。

6.6 更新的新鲜度

大多数更新改变的是详情而非位置。营业时间变更会更新 places 表，然后使详情缓存条目失效。无需更改索引。

新地点、关闭的地点或搬迁的地点会改变索引。写入会进入 places 表，该表发出变更事件。每个搜索副本消费该数据流，并在几秒内将变更应用到其内存索引。没有人需要新餐厅在毫秒内可搜索；一分钟内就足够了。

定期从 places 表全量重建索引，例如每晚一次，作为防止遗漏事件的兜底措施。

6.7 半径搜索，逐步解析

继续阅读之前。 写出“用户 1 公里范围内的咖啡馆”的步骤，包括你如何选择精度，以及如何处理角落里的结果。
  • 选择精度。 3 × 3 的块必须覆盖圆形，因此每个单元格的高度和宽度至少要等于半径。在 1 公里时，精度 6 的单元格为 1.2 公里 × 0.6 公里：一个方向太短。使用精度 5（4.9 公里），或使用 5 × 5 的块搜索精度 6。第二种在密集城市中读取的点更少。
  • 计算单元格。 对用户的点进行编码，然后计算其相邻单元格，处理 180° 经线处的环绕。
  • 扫描每个单元格的前缀（在内存索引中），按类别过滤。
  • 使用半正矢公式计算精确距离。
  • 丢弃半径之外的点。 块是方形的；搜索区域是圆形。块角落中的点可能远超半径之外，必须移除。
  • 排序并限制。 按距离，或按混合了距离和评分的分数。

练习：在曼哈顿中心，一个精度 5 的单元格可能容纳 20,000 个地点，因此 3 × 3 的块需要检查 180,000 个点；而精度 6 单元格的 5 × 5 块覆盖的面积小得多，可能只容纳几千个点。根据密度而不仅仅是半径来选择精度，可以在城市中保持扫描规模较小。

6.8 使用数据库的四叉树变体

如果面试官问如何在数据库中存储四叉树：给每个节点一个由其象限选择构建的路径键，例如

0

,

02

,

021

,

0213

。将叶子节点作为以路径为键的行存储，并包含其地点。对路径前缀的范围扫描会返回整个子树。这几乎就是一个自适应深度的 geohash，这是一个值得提出的要点：两种思想殊途同归。

拆分叶子节点会在一个事务中用四个新键重写其行。如果拆分以原子方式替换行，那么与拆分竞争的读取要么看到旧叶子，要么看到新子节点，绝不会同时看到两者。

区分答案优劣之处：精确的查询

弱止步于单元格查找

返回单元格中的所有内容，却忘记了半径之外的角落。

良好按精确距离过滤

扫描块，计算半正矢距离，过滤并排序。

优秀按密度调优

根据局部密度选择精度和块大小，解释角落过滤，并将存储的四叉树与自适应 geohash 联系起来。

变体

7.1 超越距离的排序

真实的结果会综合距离、评分、人气以及该地点当前是否营业。先按位置检索候选，再进行打分。在索引中预先计算每个地点的“当前是否营业”，以便快速过滤。

7.2 移动对象

司机或外卖骑手每隔几秒就会移动。更新占主导，而非读取。将他们的位置保存在按单元格组织的内存存储中，当对象跨越边界时，将其在单元格之间移动。

7.3 按文本和地点搜索

“我附近的披萨”将文本搜索与位置相结合。使用带地理过滤的搜索引擎，或者在候选集较小时先按位置检索，再按文本过滤。

7.4 当查询量增长十倍时

在每秒一百万次查询的规模下，将索引复制到更多区域以及每个区域的更多副本；索引本身不会随查询量增长。详情缓存成为更重的层级。为热门单元格和类别缓存完整的结果列表，并设置较短的有效期，因为同一街区的许多用户会在同一时间搜索相同的内容。

可迁移的模式

位置搜索的本质是一种让相邻对象彼此邻近的空间键，再加上对它们并不真正相邻时的校正。同样的模式适用于任何多维邻近性问题：时间和数值范围、带量化单元格的嵌入向量，以及 IP 范围。映射到一维键，搜索邻近区域，并在返回前验证精确距离。

回顾：30 秒答案

  • 索引小，详情分离。 每个副本内存中约 10 GB 的索引；500 GB 的详情缓存。
  • Geohash 前缀扫描加邻近单元格。 精度由半径决定；每次都要扫描 3 × 3 的单元格块。
  • 密度变化时使用四叉树。 自适应叶子节点，用最佳优先搜索求精确的 K 近邻。
  • 精确 K 近邻需要保证半径。 不断扩展，直到 K 个结果都落在半径内。
  • 用变更流保证新鲜度。 详情通过缓存失效机制更新；位置通过索引更新在数秒内同步。

测验

+为什么在纬度和经度上分别建两个独立索引无法快速回答“附近”查询？

每个索引只能缩小一个维度，因此数据库会扫描一条环绕全球的带状区域，然后再过滤另一个维度。与实际搜索的小范围相比，工作量巨大。

+为什么 geohash 搜索必须包含八个相邻单元格？

两个距离很近的点可能落在单元格边界的两侧，从而拥有不同的前缀。只搜索用户所在的单元格会漏掉它们。

+对于 2 km 半径，如何选择 geohash 精度？

选择单元格尺寸至少与半径相当的精度，这样 3 × 3 的单元格块就能覆盖搜索圆。精度 5 的单元格约 4.9 km 宽，适用于 2 km。

+为什么 3 × 3 单元格块中的 10 个最近候选不一定是真正的 10 个最近？

真正更近的地点可能恰好位于所搜索区块之外。结果仅在从用户到区块最近边缘的距离范围内有保证；如果区块内不足 K 个，则扩大搜索范围。

+什么时候你会选择四叉树而不是 geohash？

当地点密度差异极大且你希望叶子节点保持均衡时，或者需要通过最佳优先搜索进行精确的 K 近邻查询时。Geohash 在存储和分片上更简单。

+为什么 3 × 3 区块的结果必须按精确距离过滤？

区块是正方形，而搜索区域是圆形。位于区块角落的点可能比半径更远，必须被剔除。

+四叉树如何存储在数据库中？

为每个节点分配一个由其象限选择组成的路径键，例如 0213，并按该键存储叶子节点。前缀扫描即可返回一个子树，这使它表现得像一个深度自适应的 geohash。

资料来源与延伸阅读

  • Geohash 介绍了编码方式、精度表和边界情况。
  • Quadtree 描述了点四叉树及其搜索方法。
  • S2 Geometry 文档介绍了一种用于生产环境位置服务的球面分层单元格系统。
  • 同样以读为主、缓存优先的思路在更简单的形式下出现在 URL shortener 中。

NextDistributed Crossword Solver