空间搜索geohash概述

概述

通常在一些2C业务场景中会根据用户的位置来搜索一些内容。通常提供位置搜索的都是直接通过redis/mongodb/es等中间件实现的。

但是这些中间件又是怎么实现位置搜索的呢；
查了一番资料，发现背后一个公共的算法Geohash。

Geohash

经度和纬度是2个值，如果能变成一个值，那对搜索莱索就方便很多了。

geohash本质其实是一个二分法，将定位的经纬度，在整个经纬度刻度中不断地二分。

经度和纬度的二进制编码转换

目标经纬度为 123.123456， 12.123456

地球纬度区间是[-90,90]

1. 区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定12.123456属于右区间[0,90]，给标记为1；
2. 然后再将区间[0,90]进行二分， [0,45),[45,90]，可以确定12.123456属于左区间 [0,45)，给标记为0。
3. 递归上述过程12.123456总是属于某个区间[a,b]。 随着每次迭代区间[a,b]总在缩小，并越来越逼近12.123456。

定的纬度x（12.123456）属于左区间，则记录0，如果属于右区间则记录1，序列的长度跟给定的区间划分次数有关；

经度的计算也是同理；

交叉合并经度和纬度的二进制编码

从第 0 位开始，偶数位放经度，奇数位放纬度，得到完整的二进制编码；
然后将二进制编码分组并计算出对应的 Base32 编码

参考文案
https://segmentfault.com/a/1190000042971576