今天你想吃火锅，于是你问 siri，“离我最近的火锅店有哪些？"。

怎么实现这个功能呢？首先你应该抽象地想想，这是一个什么问题？

这是一个「二维空间查找最近邻」问题，而「最近邻」又比较容易让人想到”KNN“。（KNN 是说每个新样本的分类可以用离这个样本最近的 K 个样本的分类来表示，而我们这里要做的并不是一个分类问题，但是 knn 通过哪些手段来找到最近的 k 个样本–尤其是在样本量很大的时候，则非常值得参考。比如说 kd-tree 之类的）。

但是如果我们更多地往「查找」上面想，我们就会想到「二分」，想到「查找树」，想到「哈希」。

先来简化一下这个问题，「一维空间查找最近邻」怎么弄？

这个问题我们都会，比如把所有元素存在一个有序数组中，然后二分查找，查找的时间复杂度为 O(log n)。数组虽然查找快，但是它的缺点是插入、删除、更新的速度太慢了，如果我们希望在保持查找速度的同时提升插入、更新、删除的速度，就要用到树。

那如果现在我们有一个二维空间，怎么建树呢？kd-tree 就是一个建立多维树的方法。但是我们还有别的方法，我们可以想想，怎么把二维空间变成一维。也就是说我们寻找一个函数。

f(x, y) -> z

这个函数必须满足以下特性，假设我们有(x1, y1) 和 (x2, y2)，如果 x1 约等于 x2，并且 y1 约等于 y2，则 z1 约等于 z2；只要 x 或者 y 两个特征中有一个相差很大，z 就必须相差很大。也就是在二维空间接近的两个点的 z 要接近，而在二维空间上距离远的两个点的 z 要远。

GEOHASH 完美的解决了这个问题。GEOHASH 的算法其实非常简单，就是将地理位置的经度和纬度分别二进制化，然后交叉编码。比如一个地理位置的经度编码为 10000，纬度为 10111…，则编码后得到的 geohash 为 1100010101，然后再将这个二进制数进行 base32 编码，比如这里得到的就是 SP…。

现在假设有三个地址，编码是 SP456，SP457，45FP3，显然 SP456 和 SP457 离得比较近。我们成功的将「二维空间查找最近邻」的问题变成了「字符串前缀匹配」的问题。而字符串前缀匹配的问题就简单了，构造一个树做索引就行了。