Reliability & Operations
Geohashing and Quadtrees
Geohash 与 Quadtree 基础
Geohashing
Geohashing 是一种 geocoding 方法，用于把经纬度编码成短的字母数字字符串。由 Gustavo Niemeyer 在 2008 年提出。
例如，San Francisco 的坐标 37.7564, -122.4016 可以编码成 geohash 9q8yy9mf。
Geohashing 如何工作？
Geohash 是一种层级化的空间索引，使用 Base-32 编码。第一个字符确定 32 个初始网格之一，该网格再细分成 32 个子网格，如此递归细分，直到达到所需精度。精度越高，cell 越小。
Geohash 保证：前缀越长，空间距离越近。例如 9q8yy9mf 与 9q8yy9vx 共享前缀 9q8yy9，因此地理位置更接近。
Geohash 还能提供一定匿名性：通过调整长度，只暴露用户所在区域，而非精确位置。
不同长度 geohash 的 cell 大小：
| Geohash length | Cell width | Cell height |
|---|---|---|
| 1 | 5000 km | 5000 km |
| 2 | 1250 km | 1250 km |
| 3 | 156 km | 156 km |
| 4 | 39.1 km | 19.5 km |
| 5 | 4.89 km | 4.89 km |
| 6 | 1.22 km | 0.61 km |
| 7 | 153 m | 153 m |
| 8 | 38.2 m | 19.1 m |
| 9 | 4.77 m | 4.77 m |
| 10 | 1.19 m | 0.596 m |
| 11 | 149 mm | 149 mm |
| 12 | 37.2 mm | 18.6 mm |
Use cases
- 用简单字符串存储位置
- 作为 URL 分享，便于记忆
- 用前缀匹配 + index 快速查邻近点
Examples
Quadtrees
Quadtree 是一种树结构，每个内部节点有 4 个子节点。它用递归四分法来划分二维空间。每个 leaf 保存空间信息。它是二维的 Octree 类比。
Types of Quadtrees
- Point quadtrees
- Point-region (PR) quadtrees
- Polygonal map (PM) quadtrees
- Compressed quadtrees
- Edge quadtrees
为什么需要 Quadtrees？
经纬度可以计算距离，但对大规模数据来说基于 euclidean distance 的全量计算不现实。
Quadtree 能高效查询二维范围内的点（经纬度或坐标）。还可根据阈值决定是否继续细分，配合 Hilbert curve 等映射算法提升 range query performance。
Use cases
- 图像表示、处理与压缩
- Spatial indexing 与 range queries
- LBS（Google Maps / Uber）
- Mesh 生成与图形学
- Sparse data 存储