⭐ 题目日期：

美团 - 2025/4/25

📝 题解：

Redis 的 GEO 模块底层基于 Sorted Set（有序集合） 和 Geohash 算法实现，其核心思想是将二维的经纬度编码为一维的 Geohash 值，并将其作为 Sorted Set 的 score，从而实现高效的地理位置存储和范围查询。以下是详细实现原理：

---

1. 数据结构：Sorted Set

Redis 的 GEO 数据最终存储在一个 Sorted Set 中，每个地理位置对应 Sorted Set 中的一个元素：

• Member：地理位置的唯一标识（如地名）。
• Score：经纬度经过 Geohash 编码后的 52 位整数。

Sorted Set 的特性：

• 所有元素按 score 排序。
• 支持高效的范围查询（如 ZRANGEBYSCORE），时间复杂度为 O(log N)。

---

2. Geohash 编码

Geohash 是一种将二维经纬度映射为一维字符串的编码算法。Redis 使用 52 位精度的 Geohash，具体步骤如下：

(1) 经纬度标准化

将经纬度映射到区间 [-180, 180] 和 [-90, 90]，例如：

• 经度 -122.4194 → [-180, 180]
• 纬度 37.7749 → [-90, 90]

(2) 二进制交替编码

将经纬度交替转换为二进制位（经度占奇数位，纬度占偶数位），例如：

1. 经度范围 [-180, 180] → 不断二分区间，记录二进制位。
2. 纬度范围 [-90, 90] → 同理。
3. 交替合并经纬度的二进制位，生成一个 52 位的二进制字符串。

(3) 转换为整数

将 52 位二进制字符串转换为一个 64 位有符号整数（实际有效位为 52 位），作为 Sorted Set 的 score。

---

3. GEO 命令的实现

(1) GEOADD

• 输入：经度、纬度、位置名称。
• 步骤：
  1. 对经纬度进行 Geohash 编码，得到 52 位整数 score。
  2. 将 score 和位置名称作为元素添加到 Sorted Set 中。

(2) GEORADIUS / GEOSEARCH

• 输入：中心点经纬度、半径、单位（米/千米等）。
• 步骤：
  1. 计算 Geohash 范围：
     • 根据半径确定所需的 Geohash 精度位数（例如，1 米精度需要约 26 位）。
     • 生成中心点的 Geohash 值，并计算其 8 个相邻区域的 Geohash 范围（避免边界问题）。
  2. 范围查询：
     • 使用 ZRANGEBYSCORE 在 Sorted Set 中快速查找 Geohash 值落在目标范围内的所有元素。
  3. 过滤结果：
     • 对候选结果使用 Haversine 公式 计算与中心点的实际距离，排除超出半径的点。

---

4. 关键优化

(1) 8 邻域搜索

为避免 Geohash 的边界问题（如两个相近点因处于不同 Geohash 块而被遗漏），Redis 会同时搜索中心 Geohash 块及其 8 个相邻块。

(2) Haversine 公式

用于精确计算两个经纬度点之间的距离： [ a = \sin^2\left(\frac{\Delta\phi}{2}\right) + \cos(\phi_1) \cdot \cos(\phi_2) \cdot \sin^2\left(\frac{\Delta\lambda}{2}\right) ] [ c = 2 \cdot \text{atan2}(\sqrt{a}, \sqrt{1-a}) ] [ d = R \cdot c \quad (R \text{为地球半径}) ]

(3) 压缩存储

52 位 Geohash 值被存储为 64 位双精度浮点数，由于 52 位整数可以无损存储，避免了精度损失。

---

5. 性能分析

• 时间复杂度：
  • 添加数据：O(log N)（Sorted Set 插入）。
  • 范围查询：O(log N + M)，M 为候选结果数。
• 空间复杂度：每个地理位置占用约 64 位存储 Geohash 值。

---

6. 限制

• 最大精度误差：约 0.595 米（52 位 Geohash）。
• 不支持多边形查询：仅支持圆形区域查询。

---

7. 示例

假设存储位置 San Francisco（经度 -122.4194，纬度 37.7749）：

1. 将经纬度转换为 52 位 Geohash 值。
2. 将该值作为 score，San Francisco 作为 member 存入 Sorted Set。
3. 查询时，计算中心点的 Geohash 范围，找到附近点并过滤。

---

通过结合 Geohash 的一维编码 和 Sorted Set 的高效范围查询，Redis 的 GEO 模块在保证高性能的同时，实现了复杂的地理位置功能。