GeoHash 与空间索引
GeoHash 与空间索引
GeoHash 是一种将二维地理坐标编码为一维字符串的空间索引方法，广泛用于 LBS（基于位置的服务），如"查找附近 1km 的商家"。
为什么需要 GeoHash
搜索"我附近的餐厅"时，最朴素的做法是遍历所有商家的经纬度，算距离后排序——O(n) 复杂度，数据量大时完全不可行。
空间索引的思路是将二维平面划分成格子，每个格子有一个编码。查询时先定位到格子，再检查相邻格子即可，大大缩小搜索范围。
GeoHash 的工作原理
编码过程
GeoHash 将经纬度交替二分编码为二进制，再转成 Base32 字符串：
纬度范围 [-90, 90]，经度范围 [-180, 180]
每二分一次，增加一位精度
例如：天安门 (116.397, 39.909)
→ 二进制：11100 11101 00100 01111 00000 01101...
→ Base32：wx4g0bm...Base32 字符集（去掉 a/i/l/o 防止混淆）：
0123456789bcdefghjkmnpqrstuvwxyz编码特性
GeoHash 编码长度决定了精度：
| 编码长度 | 网格大小 | 精度说明 |
|---|---|---|
| 1 | 5000km × 5000km | 洲级 |
| 5 | 4.9km × 4.9km | 城市街区级 |
| 6 | 1.2km × 0.6km | ~附近 1km 搜索 |
| 7 | 153m × 153m | 精确到街道 |
| 8 | 38m × 19m | 精确到建筑物 |
核心特性：相邻区域具有共同前缀。
wx4g0e ← 我的位置
wx4g0s ← 东边相邻
wx4g0d ← 西边相邻
wx4g0f ← 北边相邻查询附近商家时，用 wx4g0 前缀过滤即可命中附近大片区域。
边界问题
GeoHash 并不是完美的——两个物理上很近的点，编码可能完全不同（分属不同树枝）。
wx4g0z ←→ wx4g1b
这俩编码几乎没有共同前缀，但物理距离可能只有几十米这就是 GeoHash 的"边界跳变"问题。解决方案是同时检查当前格子周围的 8 个邻居格子。
进阶：四叉树（Quadtree）
对于更复杂的空间查询需求（如"最近 K 个商家"、"碰撞检测"），GeoHash 的定长编码不太够用，四叉树是更灵活的方案。
四叉树的基本思路
递归地将空间分成 4 个象限，直到每个区域满足条件（如不超过 N 个元素）：
┌───────┬───────┐
│ NW │ NE │
│ · │ · · │
├───────┼───────┤
│ SW │ SE │
│ · │ │
└───────┴───────┘查询时从根节点向下递归，只搜索与查询范围相交的象限。
GeoHash vs 四叉树
| 维度 | GeoHash | 四叉树 |
|---|---|---|
| 数据结构 | 固定编码（字符串） | 动态树结构 |
| 查询效率 | 前缀匹配 O(k) | 树遍历 O(log n) |
| 内存 | 固定编码，轻量 | 需要维护树节点 |
| 动态更新 | 编码固定，无需调整 | 插入/删除需要重平衡 |
| 适合场景 | 简单附近搜索 | 复杂空间查询（KNN、碰撞） |
实际应用
Redis Geo
Redis 内置 GeoHash 支持：
# 添加坐标
GEOADD cities 116.397 39.909 beijing
# 查询附近
GEORADIUS cities 116.397 39.909 50 kmMongoDB
db.places.createIndex({ location: "2dsphere" });
db.places.find({
location: {
$near: {
$geometry: { type: "Point", coordinates: [116.397, 39.909] },
$maxDistance: 1000
}
}
});PostGIS / MySQL
MySQL 8.0+ 和 PostGIS 都支持空间索引（R-tree），比 GeoHash 更通用。如果需要复杂的空间计算（多边形包含、路径规划），优先考虑这些方案。
总结
GeoHash 的优点在于简单、跨语言、适合常见 LBS 场景。它的 Base32 字符串编码天然支持数据库前缀查询，配合 Redis 非常方便。对于需要 K-最近邻、碰撞检测等复杂空间查询的场景，四叉树（Quadtree）或 R-tree 是更好的选择。