经典案例：基于地理位置的服务 (Proximity Service / LBS - 类似 Yelp 与附近的人)¶

基于地理位置的服务（Location-Based Service，简称 LBS），如大众点评/Yelp 搜索“附近 3 公里的餐厅”、微信“附近的人”、滴滴/Uber“搜索附近的司机”，是系统设计面试中针对空间数据索引、高并发读写与几何算法的超高频考题。

初学者最容易困惑的是：地球是一个三维球体，经纬度是一个二维坐标（经度 Longitude, 纬度 Latitude），而数据库的传统索引（如 B+ 树）本质上是一维有序的。我们如何快速从上亿个地点中秒级检索出“距离我最近的 \(K\) 个地点”？

1. 初学者视角：为什么普通 SQL 查“附近地点”会搞崩数据库？¶

假设我们在 MySQL 中建立了一张地点表 places：

CREATE TABLE places (
    id BIGINT PRIMARY KEY,
    name VARCHAR(100),
    latitude DOUBLE,    -- 纬度 [-90.0, 90.0]
    longitude DOUBLE    -- 经度 [-180.0, 180.0]
);

当用户在坐标 \((lat_0, lon_0)\) 搜索附近 \(R = 3\text{ km}\) 的地点时，很多初学者写出的第一版 SQL 往往是：

SELECT * FROM places 
WHERE latitude BETWEEN lat_0 - delta_lat AND lat_0 + delta_lat
  AND longitude BETWEEN lon_0 - delta_lon AND lon_0 + delta_lon;

graph TD
    subgraph "传统 B+ 树复合索引的失效困境"
    A["建立复合索引 (latitude, longitude)"] --> B["B+ 树首先严格按 latitude 排序"]
    B --> C["只能通过 latitude 筛选出一个大切片 (包含数百万条记录)"]
    C --> D["在大切片内, 每一条记录的 longitude 依然是散乱无序的!"]
    D --> E["数据库被迫逐行扫描大量无效数据, 引发严重磁盘 I/O 导致查询超时!"]
    end

核心矛盾：一维索引无法同时对两个正交维度（经度和纬度）进行高效区间剪枝。
几何距离公式的昂贵开销：两点间的真实球面距离使用大圆距离公式（Haversine Formula），计算包含大量的 sin, cos, sqrt 三角函数。如果在数千万数据上逐行计算距离，单次查询就能让 CPU 跑满数秒！

2. 需求分析与系统范围 (Requirements & Scope)¶

2.1 功能性需求¶

搜索附近地点 (Search Nearby)：给定用户当前经纬度和搜索半径 \(R\)（如 \(5\text{ km}\)），返回该范围内的地点列表；
地点信息增删改 (Add/Update Place)：商家可以新增、修改餐厅或地点的基本信息；
地点详情展示 (Place Details)：查询某个地点的详细信息（名称、评分、地址、营业时间）。

2.2 非功能性需求¶

极低读取延迟 (Low Latency)：搜索“附近”接口必须在 \(100\text{ ms}\) 内返回结果；
高可用性 (High Availability - 99.99%)：核心搜索接口必须保证极端场景下可用；
读远多于写 (Read-Heavy)：用户搜索“附近”的请求量极其庞大，而地点本身的信息很少变动（典型读写比为 \(1000:1\)）。

3. 容量估算 (Back-of-the-Envelope Estimation)¶

全球地点总数：设全球收录了 2 亿个地点（\(2 \times 10^8\) 个）；
日活跃用户 (DAU)：设为 1 亿；
每人每日搜索次数：平均每人每天搜索 5 次；
读取 QPS 估算：

\[ \text{Read QPS} = \frac{10^8 \times 5}{86,400\text{ s}} \approx 6,000\text{ QPS} \]

峰值读取 QPS（按 3 倍计算）约为 18,000 QPS。

存储容量需求：
单条地点元数据大小（id, name, lat, lon, address 等）约 \(500\text{ Bytes}\)；
2 亿个地点的磁盘存储：\(2 \times 10^8 \times 500\text{ B} = 100\text{ GB}\)；
100GB 的数据量非常轻量，完全可以全部常驻在分布式内存缓存中！

4. 核心空间索引算法对比 (Geospatial Indexing)¶

为了在计算机中高效检索二维地理坐标，科学家们提出了多种将二维空间映射为一维可索引结构的精妙算法。

graph TD
    A[二维空间索引主流方案] --> B["方案一: 四叉树 (QuadTree)"]
    A --> C["方案二: GeoHash 网格编码 (最常用)"]
    A --> D["方案三: Google S2 (希尔伯特曲线)"]

    B --> B1["根据地点密度动态递归分裂<br>常驻内存树形结构, 支持快速空间剪枝"]
    C --> C1["经纬度交叉二分 Base32 编码<br>将空间转为字符串, 天然适配 B+ 树与 Redis"]
    D --> D1["空间填充曲线 (Hilbert Curve)<br>比 GeoHash 具备更优的局部保真度"]

4.1 算法一：四叉树 (QuadTree)¶

四叉树是一种树形数据结构，每个非叶子节点恰好有 4 个子节点（分别代表东北、西北、西南、东南 4 个象限）。

+-------------------+-------------------+
|                   |                   |
|      西北 (NW)    |      东北 (NE)    |
|                   |                   |
+-------------------+-------------------+
|                   |                   |
|      西南 (SW)    |      东南 (SE)    |
|                   |                   |
+-------------------+-------------------+

工作机制：¶

从覆盖全球的根节点开始；
当一个方格内包含的地点数量超过上限（例如 100 个）时，系统将该方格均分为 4 个更小的子方格；
人口密集区（如纽约、上海市区）：由于餐厅极多，树会递归分裂得很深，格子非常小；
地广人稀区（如沙漠、海洋）：格子很大，树很浅；
查询流程：从根节点向下递归，如果搜索圆与某个子方格有交集，则进入该子节点；若完全无交集则直接剪枝跳过。

4.2 算法二：GeoHash 空间编码 (工业界最通用)¶

GeoHash 的核心思想是：通过二分法将经度和纬度分别转为二进制位，然后将它们交替穿插组合，最后编码为 Base32 字符串。

编码过程（以经度为例）：¶

经度取值范围是 \([-180.0, 180.0]\)。取中点 \(0.0\)；
若目标经度在 \([0.0, 180.0]\)，记为 1；若在 \([-180.0, 0.0)\)，记为 0；
对落在的子区间继续二分，如果在上半区记 1，下半区记 0，不断重复...
纬度 \([-90.0, 90.0]\) 执行完全相同的二分操作；
交叉合并：将经度和纬度的二进制位奇偶穿插（经度占偶数位，纬度占奇数位）；
Base32 转换：每 5 位二进制转换为一个 Base32 字符（如 wtw3sj）。

GeoHash 的神奇特性：¶

前缀匹配即代表临近空间：
具有相同前缀的两个地点，必定处于同一个网格内！
前缀越长，网格越小，两点距离越近：
- 5 位编码：网格精度约为 \(4.9\text{ km} \times 4.9\text{ km}\)；
- 6 位编码：网格精度约为 \(1.2\text{ km} \times 0.6\text{ km}\)；
- 7 位编码：网格精度约为 \(150\text{ m} \times 150\text{ m}\)。

将二维查询转化为普通的前缀字符串查询：

-- 查询前缀为 'wtw3s' 的所有地点，直接走普通 B+ 树索引！
SELECT * FROM places WHERE geohash LIKE 'wtw3s%';

[!IMPORTANT] 边缘突变效应与 8 邻域搜索：两个物理上仅隔一条街的地点，可能恰好落在两个不同大网格的边界两侧，导致它们的 GeoHash 前缀完全不同。 工业界成熟解法：在搜索时，除了搜索中心点所在的网格，必须同时搜索其周围环绕的 8 个相邻网格（共 9 个网格），彻底消除边界漏洞。

4.3 算法三：Redis GEO 实战¶

Redis 从 3.2 版本开始原生支持 GEO 指令，其底层就是将 GeoHash 编码存储在一个普通的 Sorted Set (ZSET) 中（Score 即为 52 位的 GeoHash 整数值）。

# 1. 添加地点 (经度, 纬度, 名称)
GEOADD restaurants 121.4737 31.2304 "人民广场店"
GEOADD restaurants 121.5050 31.2396 "陆家嘴店"

# 2. 搜索指定坐标周围 5 公里内的地点 (按距离升序排列，带上经纬度和距离)
GEORADIUS restaurants 121.4800 31.2350 5 km WITHDIST WITHCOORD ASC COUNT 10

# 3. 计算两个地点之间的直线距离
GEODIST restaurants "人民广场店" "陆家嘴店" km

5. 高层架构设计 (High-Level Architecture)¶

graph TD
    Client[移动端用户] --> Gateway[API 网关 / 负载均衡]

    subgraph 搜索与查询服务
    Gateway --> SearchService[附近地点搜索服务]
    SearchService --> RedisCluster[(Redis GEO 集群: 存储 地点ID -> GeoHash)]
    end

    subgraph 详情与元数据服务
    Gateway --> PlaceService[地点详情服务]
    PlaceService --> Cache[(Redis 详情缓存)]
    Cache -.->|未命中| DB[(PostgreSQL + PostGIS / MySQL)]
    end

写流程（新增/修改地点）：
商家提交地点信息，写入主数据库；
服务计算其 GeoHash，写入 Redis GEO 集合；
读流程（搜索附近）：
用户发送坐标 \((lat, lon)\) 和半径 \(R\)；
搜索服务直接向 Redis GEO 发送 GEORADIUS 指令，毫秒级获取附近地点 ID 列表；
批量拿着 ID 从 Redis 详情缓存中拉取地点名称、评分、人均消费等字段，组装返回。

6. 面试深挖：静态地点 vs 动态移动对象¶

在系统设计面试中，面试官常会话锋一转：

“上面我们讨论的是静态餐馆。如果是滴滴打车，100 万司机每 3 秒上报一次位置，你的系统该如何改造？”

维度	静态地点（如大众点评餐厅）	动态移动对象（如滴滴司机、外卖骑手）
写频次	极低（每天可能有几百家新店开业）	极其恐怖（100 万司机 \(\times\) 每 3 秒 1 次 = 330,000 写入 QPS）
持久化要求	极高（地点数据必须落盘防丢失）	无需实时落盘（司机的历史瞬时坐标过 5 秒就失去价值）
存储介质	数据库持久化 + 缓存	纯内存化存储（纯在 Redis 或专用 LBS 内存服务中更新）
架构改造策略	采用四叉树或 Redis GEO	按网格分片集群：使用内存分片集群维护 `Driver_ID -> Location`，仅当发生订单时才将轨迹持久化入库。