0 前言
两周前，我和大家分享了一篇文章——基于golang实现前缀树Trie. 在这次分享中，我留下了一个引子：当时提到前缀树 Trie 的一类使用场景是应用在 GeoHash 编码的数据结构存储中. 今天我们就来回收这个伏笔，一起探讨一下 GeoHash 的概念和原理，以及其与前缀树 Trie 之间的技术联动.
1 geohash 应用背景
1.1 提出问题
叮！又到饭点了. 居住在北京小家的小徐先生准备出门觅食，他打开手机中的地图 app，检索附近1 公里范围内的餐馆，挑选合适的用餐地点.
用餐完毕后，小徐先生开始发散思路，回头思考一个问题：在地图 app 中，如何对指定范围内的餐馆信息进行精确推送和展示呢？
1.2 粗暴解
小徐先生所生活的城市是北京，毕竟不是像重庆这样的三维立体城市，因此每个点都可以通过经度+纬度 (lng,lat) 这样二维坐标的形式加以标识.
于是乎，一种简单粗暴的实现方式是：
• 我们把地球上所有餐馆的 (lng,lat) 坐标都维护在一个 list 里
• 我们获取到小徐先生所在的北京人家的坐标 (lng0,lat0)
• 遍历 list 中所有餐馆的 (lng,lat) 坐标，求出和 (lng0,lat0) 的相对距离，如果大于指定距离就过滤，小于等于指定距离就保留
• 最终被保留在 list 中的餐馆集合就是我们所求的目标
然而这种方案是骇人听闻的，全量餐馆数据规模何其庞大，每次执行范围检索的时候，都需要全量遍历计算，这样骇人听闻的工作量足以击垮任何一个服务集群.
1.3 索引法
优化计算效率的思路就是以空间换取时间，这个点是万变不离其宗的. 在我们这个场景中，核心的挑战在于如何合理设计我们用于存储位置信息的空间结构.
最常规的实现思路是利用索引提高检索效率，然而在本场景中，我们知道每个位置是由二维的 (lng,lat) 坐标组成的，这要如何设计成索引呢？
这正是今天我们探讨的 geohash 所需要解决的问题. geohash 能把这种二维的经纬度坐标能转换成带有前缀索引性质的一维坐标，我们把这个特殊的一维坐标称为"geohash 字符串". 在 geohash 技术实现中，能在很大程度上保证，两个 geohash 字符串公共前缀的长度越长，对应的两个区域距离就越接近，并且其间的相对距离范围是可以通过公共前缀的长度估算出具体量级的.
大家在这里需要存个心眼，我于此处的描述中特意强调了该性质只能做到 “一定程度上保证”，这是因为在一些边界 case 中，有可能会出现两个位置本身距离很接近，但是 geohash 字符串的前缀却又差别很大的情况. 这个问题我们会在本文 4.1 小节中详细介绍.
下面我们给出几个将经纬度坐标(lng,lat) 转为一维 geohash 字符串的示例：
| 索引 index | 点 point | 经度 lng | 纬度 lat |
| YJXY433V | A | 101 | 77 |
| Y8M76SJ6 | B | 120 | 47 |
| K6BE10DN | C | 12 | -29 |
| PBQE6KPD | D | 178 | -88 |
2 geohash 实现原理
第 1 章聊完后，相信在大家心中已经萦绕了一个很大的疑问：geohash 技术究竟有什么神通，如何能够把一个二维坐标转换为一维坐标，同时能够保证其具备前缀索引的性质的呢？
下面，我们就来从零到一地推演一下 geohash 的实现思路.
2.1 地球投影
地球是个球体，表面是个球面.
我们假想距离地球无穷远处有个光源，将地球表面投影到一个等高的圆柱体侧面. 接下来我们让地球自转一周，并同步地让圆柱体沿着相同的方向按照相同的速度旋转一周，最终我们将整个球面的内容都投射到了圆柱体的侧面之上，其中纬度对应的是圆柱体的高度方向，而经度则对应的是圆柱体的周长方向.
我们沿着经度 -180/180° 的交接位置 “咔嚓”一刀将圆柱体的侧面纵向剪开，将其展开成一个矩形平面图如下：
对照下图来看,地球在纵向上由 -90°~90° 的纬度范围组成,在横向上由 -180°~180° 的经度范围组成. 因此我们把球面投影成一个矩形平面后，矩形的宽、高刻度就分别对应着经度和纬度，宽度方向上自左向右以 -180°为起点，180°为终点，每个刻度的单位为 1° 经度；高度自底向上以 -90°为起点，90°为终点，每个刻度单位为 1° 纬度.
2.2 经纬度二分
现在，由于地球的球形表面已经被我们“展开”成了一张矩形平面，因此每个位置对应的(lnt,lat) 坐标都可以很方便的在矩形平面上进行定位.
下面要谈的内容，就是我们将二维的经纬度坐标转为一维坐标的关键所在.
首先，沿着经度（矩形宽度）的方向进行递归二分，将一个具体经度拆解成一个由二进制数字组成的字符串.
举例说明：
• 第一轮：经度范围为 -180°~180°，可以拆分成 -180°~0° 以及 0°~180° 两部分，如果经度从属于前者，则令首个 bit 位取 0，否则令首个 bit 位取 1；
• 第二轮：-180~°0° 可以拆分为 -180°~-90° 和 -90°~0°，如果经度从属于前者，则令第二个 bit 位取 0，否则令第二个 bit 位取 1；0°~180° 可以拆分为 0°~90° 和 90°~180°，前者令第二个 bit 位取 0，后者令第二个 bit 位取 1
• 第 3 ~ N 轮：重复上述步骤的思路，最终递归二分，将经度表示成一个由二进制数字组成的字符串
同样的流程可以应用在纬度（矩形高度）的递归二分当中，最终每个具体的纬度也可以被拆分成一个由二进制数字组成的字符串.
接下来就是画龙点睛的一笔，我们将沿经度方向的切分和沿纬度方向的切分合并在一起，于是整个矩形平面会被切割成网状，形成一个个小的矩形块.
对于每个矩形块而言，其根据自己所从属的经度区间，会对应有一个经度二进制字符串；同时根据其从属的纬度区间，也会有一个纬度二进制字符串. 接下来我们化二维为一维的关键就是，我们按照经度字符串+纬度字符串依次交错排列的形式，将其组织在一起，最终形成一个一维字符串.
如下图所示，我们能够注意到，这个一维字符串的位数越多，意味着对应的矩形块就越小；同时拥有相同前缀的小矩形块必然从属在同一个大矩形块的范围之内，比如下图左上方的 4 个小矩形：0101、0111、0100、0111 都拥有着公共前缀 "01"，因此，他们都从属于由 "01"表示的这个大矩形块当中.
综上，我们得知这个一维字符串具有前缀索引的性质，他能够保证两个字符串前缀匹配位数越长，两个矩形块的相对位置就越靠近。
下面再补一张简笔画风格的示意图，大家可以进一步对这个流程的本质加以理解.
2.3 Base32编码
最后要聊的是 geohash 的编码格式. 为了进一步节省空间，geohash 采用 Base32 编码替代了原始的二进制字符串.
在通过 2.2 小节的思路生成的二进制字符串中，我们从左向右将每 5 个 bit 分成一组，使用 Base32 编码进行映射，最后能够得到一个更加简短精炼的一维字符串，这就是一个完整版本的 geohash 字符串了.
Base32 编码主要是以 10 个数字字符 ‘0’-‘9’ 加上 26 个英文字母 ‘A’-‘Z’ 组成，并在其中把几个容易产生混淆的字符 'I' 'L' 'O' 以及字母 'A' 去掉了，最终总计保留下来 32 个字符. Base32编码 与十进制数值的映射关系如下表所示：
| 数值 | base32字符 | 数值 | base32字符 |
| 0 | 0 | 16 | H |
| 1 | 1 | 17 | J |
| 2 | 2 | 18 | K |
| 3 | 3 | 19 | M |
| 4 | 4 | 20 | N |
| 5 | 5 | 21 | P |
| 6 | 6 | 22 | Q |
| 7 | 7 | 23 | R |
| 8 | 8 | 24 | S |
| 9 | 9 | 25 | T |
| 10 | B | 26 | U |
| 11 | C | 27 | V |
| 12 | D | 28 | W |
| 13 | E | 29 | X |
| 14 | F | 30 | Y |
| 15 | G | 31 | Z |
下面是遵循 geohash 思路，将一个二进制字符串转为 Base32 编码形式的示例：
基于上述流程，我们可以将地球表面上每个递归二分得到的小矩形块表示成 geohash 字符串的形式. 下图是通过 6 位 geohash 字符串，对北京西二旗附近区域进行切分表示的示例：
2.4 长度决定精度
在 geohash 字符串中，字符串的长度决定了矩形块的大小，进一步决定了距离的精度. 在对经纬度进行递归二分时，每多一轮二分，矩形一个方向上的边长就会减半，因此矩形区域就越小，对应的精度就越高. 下面是 geohash 字符串长度和距离精度的映射关系：
| geohash字符串长度（base32） | lat bits纬度二进制位数 | lng bits经度二进制位数 | lat error纬度方向长度（°） | lng error经度方向长度（°） | km error矩形边长（km） |
| 1 | 2 | 3 | ±23 | ±23 | ±2500 |
| 2 | 5 | 5 | ±2.8 | ±5.6 | ±630 |
| 3 | 7 | 8 | ±0.70 | ±0.70 | ±78 |
| 4 | 10 | 10 | ±0.087 | ±0.18 | ±20 |
| 5 | 12 | 13 | ±0.022 | ±0.022 | ±2.4 |
| 6 | 15 | 15 | ±0.0027 | ±0.0055 | ±0.61 |
| 7 | 17 | 18 | ±0.00068 | ±0.00068 | ±0.076 |
| 8 | 20 | 20 | ±0.000085 | ±0.00017 | ±0.019 |
3 geohash 实现步骤
第二种我们聊完了 geohash 的宏观实现流程，下面我们通过一个具体的案例，来完整地串联一遍 geohash 字符串的生成流程.
3.1 取得经纬度
以小徐先生所在的北京人家小区为例，我们首先取到对应的经纬度信息：(116.311126,40.085003)
3.2 经度递归二分
我们预期生成的 geohash 字符串长度为 6 位，则对应的经度和纬度二进制字符串的 bit 位长度需要为 15 位. 最终取得的 geohash 字符串所对应的矩形块边长范围约为 610 m.
下面我们对经度 116.3111126 进行二分，首轮从 -180°~180°的范围开始，二分的流程如下所示：
| bit | left | mid | right |
| 1 | -180 | 0 | 180 |
| 1 | 0 | 90 | 180 |
| 0 | 90 | 135 | 180 |
| 1 | 90 | 112.5 | 135 |
| 0 | 112.5 | 123.75 | 135 |
| 0 | 112.5 | 118.125 | 123.75 |
| 1 | 112.5 | 115.3125 | 118.125 |
| 0 | 115.3125 | 116.71875 | 118.125 |
| 1 | 115.3125 | 116.015625 | 116.71875 |
| 0 | 116.015625 | 116.3671875 | 116.71875 |
| 1 | 116.015625 | 116.19140625 | 116.3671875 |
| 1 | 116.19140625 | 116.279296875 | 116.3671875 |
| 0 | 116.279296875 | 116.323242188 | 116.3671875 |
| 1 | 116.279296875 | 116.301269532 | 116.323242188 |
| 0 | 116.301269532 | 116.31225586 | 116.323242188 |
最终，我们递归二分得到经度方向上的二进制字符串为 110100101011010，长度为 15 位.
3.3 纬度递归二分
下面我们对经度 40.085003 进行二分，首轮从 -90°~90°的范围开始，二分的流程如下所示：
| bit | left | mid | right |
| 1 | -90 | 0 | 90 |
| 0 | 0 | 45 | 90 |
| 1 | 0 | 22.5 | 45 |
| 1 | 22.5 | 33.75 | 45 |
| 1 | 33.75 | 39.375 | 45 |
| 0 | 39.375 | 42.1876 | 45 |
| 0 | 39.375 | 40.78125 | 42.1876 |
| 1 | 39.375 | 40.078125 | 40.78125 |
| 0 | 40.078125 | 40.4296875 | 40.78125 |
| 0 | 40.078125 | 40.25390625 | 40.4296875 |
| 0 | 40.078125 | 40.166015625 | 40.25390625 |
| 0 | 40.078125 | 40.1220703125 | 40.166015625 |
| 0 | 40.078125 | 40.1000976563 | 40.1220703125 |
| 0 | 40.078125 | 40.0891113282 | 40.1000976563 |
| 1 | 40.078125 | 40.0836181641 | 40.0891113282 |
最终，我们递归二分得到纬度方向上的二进制字符串为 101110010000001，长度为 15 位.
3.4 经纬度字符串拼接
结合经度字符串 110100101011010 和纬度字符串 101110010000001，我们遵循先经度后纬度的顺序，逐一交错排列，最终得到的一维字符串为 11100 11101 00100 11000 10100 01001.
3.5 Base32编码
在一维二进制字符串 11100 11101 00100 11000 10100 01001 的基础上，我们从左往后，以每 5 个 bit 成一组，转为 Base32 编码的表达形式，最终得到的编码结果为 WX4SN9
4 geohash 问题讨论
4.1 边缘性问题
在应用 geohash 技术时，我们需要格外注意其中存在的边缘性局限问题.
我们在实现上，将矩形平面通过递归二分的方式，切分成一个个小的矩形块，而每个矩形块有着自己与毗邻矩形块的交界区域，倘若有两个点分别从属于两个毗邻矩形块，但是又同时靠近于它们的交界线，此时就会出现两个点实际距离接近，但前缀匹配长度不足的情况.
如下图所示，A、B 两个点同属于一个矩形块中，有着更长的公共前缀；C、D、E 三个点和 A 不从属于同一个矩形块，与A 的 geohash 字符串前缀匹配长度相较于 B 而言要更短，然而其本身和 A 的相对距离却是要更接近的.
针对于这种边缘性问题，为了避免在近距离位置检索过程中出现目标的遗漏，我们通常会在通过 geohash 锁定一个小的矩形块后，以其作为中心，将周围 8 个矩形块范围内的点也同时检索出来，再根据实际的相对距离进行过滤.
4.2 最短距离问题
除了边缘性问题外，geohash 还存在一个最短距离问题.
倘若我们想要借助 geohash 技术，找到距离点 A 最近的目标点. 我们以 A 所在矩形为中心，基于“回”字形的拓扑结构向外逐层向外拓宽，此时我们是无法保证靠内侧的“回”字形层次中出现的目标点一定比外层的点距离点 A 更近.
比如以下图为例，点 F 相比于点 G ，在层次上与点 A 更加靠近，但是实际上与点 A 的相对距离要长于点 G.
为了解决这个问题，我们需要在遇到首个目标点后，额外向外扩展几圈，直到保证扩展范围边界与点 A 的相对距离已经长于首个目标点后才能停止扩展流程. 接下来我们需要取出扩展范围内所有的点，分别计算出与点 A 的相对距离，最终取出距离最小的那个点，即为我们所求的结果.
4.3 范围检索思路
应用 geohash 技术的一类场景是：给定一个指定位置作为中心点，想要检索出指定半径范围内的所有点集合.
此时我们的解决思路是，首先求出中点所在的矩形块及其对应的 geohash 字符串，然后基于回字形向外逐层拓宽，直到能保证拓展范围一定能完全包含以中心点为圆心、指定距离为半径的圆后，我们求出拓展范围内所有的点（此时可能有多余的结果），再通过其与中心点的相对距离进行过滤，保留满足条件的目标点集合.
5 geohash 具体实现
本章开始，我会基于 go 语言，和大家一起手撸出一个 geohash 模块.
5.1 geohash 与 trie
首先要对 geohash 字符串的存储数据结构进行选型.
由于 geohash 字符串本身带有前缀索引的前置，通过调整前缀匹配的位数，能够有效地控制检索目标的范围大小. 这种前缀索引属性天然和前缀树 Trie 保持着很高的契合度，能够很好的支持基于前缀索引的范围检索或者统计功能. 因此在本章中，我们选择采用 Trie 作为 geohash 字符串的存储结构.
（更多有关于前缀树 Trie 的设计思路与实现原理，可以参考我之前分享的文章——基于 Golang 实现前缀树 Trie）
与 Trie 相对的是，我们还可以使用类似于红黑树或者跳表这样的有序表结构来实现 geohash 的存储模块，通过有序表的性质，能够给保证在 O(logN) 的时间复杂度量级内完成基于前缀的范围检索操作. 后续在本文第 6 章介绍到的 redis geohash 模块中，采用的就是跳表 skiplist 这种结构.
（更多有关于跳表 Skiplist 的设计思路与实现原理，可以参考我之前分享的文章——基于golang从零到一实现跳表）
按照我的个人观点，在实现 geohash 的技术选型上，Trie 是要优于 Skiplist 的. 我们在操作 Trie 时，操作的时间复杂度只和字符串的长度有关，在 geohash 中应用到 Base32 编码后，字符串的长度一般可以控制在 10 以内，因此整体操作是常数级别的时间复杂度 O(1). 而 Skiplist 的操作复杂度则与数据量级有关，只能做到 O(logN). 在 redis 中之所以选择采用 Skiplist 这种结构实现 geohash 模块，实际上是为了复用其现有的有序集合存储结构 zset，而 zset 底层就是基于 Skiplist 实现的.
5.2 数据结构
下面我们先过一下 geohash 模块中的几个核心类.
• GEOService：geohash 服务类，用户访问的统一入口.
• mu：通过一把读写锁保护 geohash 前缀树的并发安全性
• root：持有的 geohash 前缀树的根节点引用
• geoTrieNode：geohash 前缀树中的节点类型
• children：孩子节点列表. 由于采用 base32 编码，因此最多只能有 32 个 child . 其中 children[0] 对应值为 '0' 的 child，children[31] 对应值为 'z' 的 child，以此类推
• passCnt：途径该节点的子孙节点计数器
• end：标志是否有字符串以当前节点结尾
• GEOEntry：对应与一个 geohash 字符串的矩形区域
• Points： 矩形区域内的点集合
• Hash：geohash 字符串
• GEOPoint：通过经、纬度标识的一个点
• Lng、Lat：经纬度
• Val：点对应的业务信息
下面进行具体的源码展示，同时注释加以补充描述：
// geohash 服务模块
type GEOService struct {
// 读写锁保证并发安全
mux sync.RWMutex
// 前缀树根节点
root *geoTrieNode
}
// geohash 服务模块构造器方法
func NewGEOService() *GEOService {
return &GEOService{
root: &geoTrieNode{},
}
}
// geohash 前缀树中的节点
type geoTrieNode struct {
// 子节点列表，顺序与 base32 一致
children [32]*geoTrieNode
// 途径该节点的字符串数量
passCnt int
// 是否有字符串以该节点结尾
end bool
// geohash 字符串对应的矩形区域
GEOEntry
}
// 1 geoAdd 添加一个经纬度作为，并缓存好对应的信息
// 2 geoHash 传入一组经纬度，获取对应的 geoHash 编码
// 3 geoRadius 传入一个经纬度以及半径，获取指定范围内的坐标
type GEOEntry struct {
// 矩形区域中的点集合，其中 key 通过 ${lat}_${lng} 的格式组成，val 是 point 的引用
Points map[string]interface{
// 矩形区域对应的 geohash 字符串
Hash string
}
// 获取到矩形区域内所有的点集合
func (g *GEOEntry) GetPoints() []*GEOPoint {
points := make([]*GEOPoint, 0, len(g.Points))
for key, val := range g.Points {
lng, lat := g.lngLat(key)
points = append(points, &GEOPoint{
Lng: lng,
Lat: lat,
Val: val,
})
}
return points
}
// 往矩形区域中追加一个新的点
func (g *GEOEntry) add(lng, lat float64, val interface{}) {
if g.Points == nil {
g.Points = map[string]interface{}{}
}
g.Points[g.pointKey(lng, lat)] = val
}
// 将经纬度转为 ${lng}_${lat} 的格式
func (g *GEOEntry) pointKey(lng, lat float64) string {
return fmt.Sprintf("%v_%v", lng, lat)
}
// 将 point 对应的 key ${lng}_${lat} 转为对应的经纬度
func (g *GEOEntry) lngLat(key string) (lng float64, lat float64) {
info := strings.Split(key, "_")
lng, _ = strconv.ParseFloat(info[0], 64)
lat, _ = strconv.ParseFloat(info[1], 64)
return
}
// 一个通过经纬度坐标标识的点
type GEOPoint struct {
Lng, Lat float64
Val interface{}
}
下面简单示意一下，geohash 前缀树中一个节点 geoTrieNode 的数据结构：
5.3 核心方法一览
geohash 服务模块需要对外提供的几个 API 整理如下：
• Hash：将用户输入的经纬度 lng、lat 转为 geohash 字符串
• Get：通过传入的 geohash 字符串，获取到对应于矩形区域块的 GEOEntry 实例
• Add：通过用户传入的经纬度 lng、lat，构造出 point 实例并添加到对应的矩形区域中
• ListByPrefix：通过用户输入的 geohash 字符串，获取到对应矩形区域块内所有子矩形区域块的 GEOEntry 实例（包含本身）
• Rem：通过用户输入的 geohash 字符串，删除对应矩形区域块的 GEOEntry
• ListByRadiusM：通过用户输入的中心点 lng、lat，以及对应的距离范围 radius，返回范围内所有的点集合
5.4 geohash 转换
下面是将用户输入的经纬度转换为对应 geohash 字符串的方法源码示例：
// 通过二分的方式，把经纬度转换成对应的 hash 字符串，固定为 40 位二进制数字组成
// 每 5 个 bit 位由一个 base32 映射得到，因此总共由 8 位 base32 字符组成
func (g *GEOService) Hash(lng, lat float64) string {
// lng 通过二分转为 20 个二进制 bit 位
lngBits := g.getBinaryBits(&strings.Builder{}, lng, -180, 180)
// lat 通过二分转为 20 个二进制 bit 位
latBits := g.getBinaryBits(&strings.Builder{}, lat, -90, 90)
// 经纬度交错在一次，每 5 个 bit 一组，转换成 base32 字符串
var geoHash strings.Builder
var fiveBitsTmp strings.Builder
for i := 1; i <= 40; i++ {
if i&1 == 1 {
fiveBitsTmp.WriteByte(lngBits[(i-1)>>1])
} else {
fiveBitsTmp.WriteByte(latBits[(i-1)>>1])
}
// 位数不足 5 位，则继续累积位数
if i%5 != 0 {
continue
}
// 将每个 bit 位组成的二进制数字转为十进制数值
val, _ := strconv.ParseInt(fiveBitsTmp.String(), 2, 64)
// 转为 base32 编码，并写入到 stringBuilder 中
geoHash.WriteByte(Base32[val])
fiveBitsTmp.Reset()
}
// 返回 geohash 字符串
return geoHash.String()
}
// 递归二分，直到凑齐指定长度的二进制字符串
func (g *GEOService) getBinaryBits(bits *strings.Builder, val, start, end float64) string {
mid := (start + end) / 2
if val < mid {
bits.WriteByte('0')
end = mid
} else {
bits.WriteByte('1')
start = mid
}
if bits.Len() >= 20 {
return bits.String()
}
return g.getBinaryBits(bits, val, start, end)
}
// 将十进制数值转为 base32 编码
var Base32 = []byte{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'M', 'N', 'P',
'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'}
// 将 base32 编码转为十进制数值
func (g *GEOService) base32ToIndex(base32 byte) int {
if base32 >= '0' && base32 <= '9' {
return int(base32 - '0')
}
if base32 >= 'B' && base32 <= 'H' {
return int(base32 - 'B' + 26)
}
if base32 >= 'J' && base32 <= 'K' {
return int(base32 - 'J' + 33)
}
if base32 >= 'M' && base32 <= 'N' {
return int(base32 - 'J' + 35)
}
if base32 >= 'P' && base32 <= 'Z' {
return int(base32 - 'J' + 37)
}
return -1
}
5.5 geohash 查询
下面是通过 geohash 字符串获取矩形区域对应 GEOEntry 的方法：
func (g *GEOService) Get(geoHash string) (*GEOEntry, bool) {
// 加读锁，和写操作隔离，保证并发安全
g.mux.RLock()
defer g.mux.RUnlock()
// 尝试获取到对应的节点
target := g.get(geoHash)
// 倘若节点不存在或者 end 标识 为 false，说明 GEOEntry 不存在
if target == nil || !target.end {
return nil, false
}
// 返回对应的 GEOEntry
return &target.GEOEntry, true
}
// 通过 geohash 字符串，检索 geohash 前缀树
func (g *GEOService) get(geoHash string) *geoTrieNode {
// 移动指针从根节点出发
move := g.root
// 遍历 geohash 字符串的每个字符
for i := 0; i < len(geoHash); i++ {
// 将 base32 编码转为十进制
index := g.base32ToIndex(geoHash[i])
// 如果对应索引的字节点不存在，说明目标一定不存在，直接返回 空
if index == -1 || move.children[index] == nil {
return nil
}
// 移动指针指向对应的孩子节点，开始下一轮遍历
move = move.children[index]
}
// 返回目标节点
return move
}
5.6 geohash 添加
geohash 添加一个 point 的流程，入参包括对应点的经纬度 lng、lat，以及需要在该 point 中存放的业务信息 val：
func (g *GEOService) Add(lng, lat float64, val interface{}) {
// 将经纬度转为对应的 geohash 字符串
geoHash := g.Hash(lng, lat)
// 加写锁
g.mux.Lock()
defer g.mux.Unlock()
// 获取到 geohash 字符串对应的
target := g.get(geoHash)
// 如果目标节点存在并且 end 标识为 true
if target != nil && target.end {
// 则往目标节点对应的 GEOEntry 中追加这个新的节点
target.add(lng, lat, val)
return
}
// 目标节点不存在，则执行遍历
move := g.root
for i := 0; i < len(geoHash); i++ {
// base32 转十进制
index := g.base32ToIndex(geoHash[i])
// 如果路径上的节点有缺失，沿路进行构建
if move.children[index] == nil {
move.children[index] = &geoTrieNode{}
}
// 对途径节点的 passCnt 进行累加
move.children[index].passCnt++
move = move.children[index]
}
// 来到结束位置，将对应节点的 end 标识置为 true
move.end = true
// 把点添加到 geoEntry 中
move.add(lng, lat, val)
move.Hash = geoHash
}
5.7 geohash 前缀查询
通过输入的 geohash 字符串为前缀，检索出所有的 GEOEntry 集合
func (g *GEOService) ListByPrefix(prefix string) []*GEOEntry {
// 加读锁
g.mux.RLock()
defer g.mux.RUnlock()
// 尝试获取目标节点
target := g.get(prefix)
// 如果目标节点不存在，说明以 prefix 为前缀的 GEOEntry 一定不存在，直接返回空
if target == nil {
return nil
}
// 进行深度优先遍历
return target.dfs()
}
func (gn *geoTrieNode) dfs() []*GEOEntry {
var entries []*GEOEntry
// 如果当前节点 end 标识为 true，追加到 list 中
if gn.end {
entries = append(entries, &gn.GEOEntry)
}
// 遍历所有非空的 child 依次进行指定 dfs，并将结果追加到 list 中
for i := 0; i < len(gn.children); i++ {
if gn.children[i] == nil {
continue
}
entries = append(entries, gn.children[i].dfs()...)
}
// 返回 list
return entries
}
5.8 geohash 删除
传入指定 geohash 字符串，删除对应节点的流程：
func (g *GEOService) Rem(geoHash string) bool {
// 加写锁
g.mux.Lock()
defer g.mux.Unlock()
// 通过 geohash 字符串尝试获取到目标节点
target := g.get(geoHash)
// 如果目标节点为空，或者 end 标识为 false，直接终止流程
if target == nil || !target.end {
return false
}
// 走到此处，意味着目标节点一定存在，下面开始检索
// 移动指针从根节点出发
move := g.root
// 遍历每个字符
for i := 0; i < len(geoHash); i++ {
// base32 转十进制索引
index := g.base32ToIndex(geoHash[i])
// 对途径的 child passCnt --
move.children[index].passCnt--
// 如果某个 child passCnt 减至 0，则直接丢弃整个 child 返回
if move.children[index].passCnt == 0 {
move.children[index] = nil
return true
}
move = move.children[index]
}
// 走到结束为止，则将节点的 end 标识置为 false 完成删除
move.end = false
return true
}
5.9 geohash 范围查询
传入中心点，查询指定范围内的点的集合：
// 查询指定范围范围内
// radius 单位为 m.
// m 转为对应的经纬度 经度1度≈111m；纬度1度≈111m
func (g *GEOService) ListByRadiusM(lng, lat float64, radiusM int) ([]*GEOPoint, error) {
// 加一把读锁
g.mux.RLock()
defer g.mux.RUnlock()
// 1 根据用户指定的查询范围，确定所需要的 geohash 字符串的长度，保证对应的矩形区域长度大于等于 radiusM
bitsLen, err := g.getBitsLengthByRadiusM(2*radiusM)
if err != nil {
return nil, err
}
// 2 针对于传入的 lng、lat 中心点，沿着上、下、左、右方向进行偏移，获取到包含自身在内的总共 9 个点的点矩阵
// 核心是为了保证通过 9 个点获取到的矩形区域一定能完全把检索范围包含在内
points := g.getCenterPoints(lng, lat, radiusM)
// 3. 针对这9个点，通过 ListByPrefix 方法，分别取出区域内的所有子 GEOEntry
var rawEntries []*GEOEntry
for i := 0; i < len(points); i++ {
geoHash := g.Hash(points[i][0], points[i][1])[:bitsLen]
rawEntries = append(rawEntries, g.ListByPrefix(geoHash)...)
}
// 4. 针对所有 entry，取出其中包含的所有 point
// 取出 point 之后，计算其与 center point 的相对距离，如果超过范围则进行过滤
var geoPoints []*GEOPoint
// 遍历所有的 entry
for _, rawEntry := range rawEntries {
// 遍历每个 entry 中所有的 point
for _, rawPoint := range rawEntry.GetPoints() {
// 计算一个 point 与中心点 lng、lat 的相对距离
dist := g.calDistance(lng, lat, rawPoint.Lng, rawPoint.Lat)
// 如果相对距离大于 radiusM，则进行过滤
if dist > float64(radiusM) {
continue
}
// 相对距离满足条件，则将 point 追加到 list 中
geoPoints = append(geoPoints, rawPoint)
}
}
return geoPoints, nil
}
下面展示了如何通过半径 radiusM，获取到矩形区域所需要的 geohash 字符串的位数：
func (g *GEOService) getBitsLengthByRadiusM(radiusM int) (int, error) {
if radiusM > 160*1000 || radiusM < 0 {
return -1, fmt.Errorf("invalid radius: %d", radiusM)
}
var i int
for {
if radiusM <= distRank[i+1] {
return 8 - i, nil
}
i++
}
}
var distRank = []int{0, 20, 150, 600, 5000, 20000, 160000}
根据传入的经纬度，计算两点间的距离：
func (g *GEOService) calDistance(lng1, lat1, lng2, lat2 float64) float64 {
return 111 * (math.Pow(lng1-lng2, 2) + math.Pow(lat1-lat2, 2))
}
根据传入的中心点，获取到周围八个矩形区域内的点集合：
func (g *GEOService) getCenterPoints(lng, lat float64, radiusM int) [9][2]float64 {
dif := float64(radiusM) / 111
left := lng - dif
if left < -180 {
left += 360
}
right := lng + dif
if right > 180 {
right -= 360
}
bot := lat - dif
if bot < -90 {
bot += 180
}
top := lat + dif
if top > 90 {
top -= 180
}
return [9][2]float64{
{
left, top,
},
{
lng, top,
},
{
right, top,
},
{
left, lat,
},
{
lng, lat,
},
{
right, lat,
},
{
left, bot,
},
{
lng, bot,
},
{
right, bot,
},
}
}
6 redis geohash
6.1 核心指令
redis geohash 模块涉及到几个核心指令：
• GEOADD：添加一个 point 到 geohash key 当中：
GEOADD key longitude latitude member [longitude latitude member ...]• key：对应为一个 geohash 模块实例的标识键
• longitude：point 的经度
• latitude：point 的纬度
• member：point 在 geohash 模块实例中的名称
• GEOHASH：传入一个 point 对应的名称，查看 point 的信息
GEOHASH key member [member ...]• key：对应为一个 geohash 模块实例的标识键
• member：point 在 geohash 模块实例中的名称
• GEORADIUS：传入一个 point 以及半径，查看指定范围内的点集合
• key：对应为一个 geohash 模块实例的标识键
• longitude：point 的经度
• latitude：point 的纬度
• radius：传入范围的半径，单位可以为 m/km/ft/mi
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]
6.2 实现原理
redis geohash 本质上使用通过有序集合 zset 实现的. zset 对应的 key 即为 geohash 的 key，在 zset 内部，会以 point 对应的 geohash 字符串的十进制数值作为 score，以此来组织排序，建立有序存储结构.
值得一提的一个点是，在将 geohash 字符串转为十进制表达后，针对于纬度取得上下边界是 -85.05112878~85.05112878 而非 -90~90，这个点也是我在读源码的时候发现的，目前还没有找到具体的原因.
在通过 redis 执行 GEORADIUS 指令，会根据中心点 point 以及半径，找到其所属的矩形区域以及其周边的8个矩形区域. 待获得指定范围内所有 point 后，会统一计算和中心点 center point 之间的相对距离，最终只返回满足条件的 point list.
7 总结
本文和大家一起探讨了 geohash 技术，其核心用途是：能将经纬度二维坐标转为带有前缀索引性质的一维 geohash 字符串，这种特殊的字符串能够保证拥有相同前缀的两个点相对距离一定能控制在与公共前缀长度相关的指定范围之内.
在 geohash 技术的实现中，是通过将地球表面投影成矩形平面，并基于经度、纬度方向递归二分的方式进行矩形块切割，因此存在边缘性问题，需要在应用时额外关注.
此外，本文还带着大家一起基于 Go 语言从零到一实现了一个 geohash 服务模块，其中采用前缀树 Trie 作为 geohash 字符串的存储数据结构.
