空间检索（下）：「查找最近的加油站」和「查找附近的人」有何不同？
上一讲我们讲了，对于查询范围固定的应用需求，比如「查找附近的人」，我们可以根据规划好的查询区域大小，均匀划分所有的空间，然后用 GeoHash 将坐标转换为区域编码，以该区域编码作为 Key 开始检索。这样，我们就可以查到并取出该区域中的目标数据，对这些数据进行精准计算然后排序输出了。
但是，并不是所有应用的查询范围都是不变的。在一些基于地理位置的服务中，我们并不关心检索结果是否就在我们「附近」，而是必须要找到「最近」的一批满足我们要求的结果。这怎么理解呢？
我来举个例子，我们在长途自驾游的时候，突然发现车快没油了。这个时候，我们要在一个导航地图中查找最近的 k 个加油站给车加油，这些加油站可能并不在我们附近，但地图又必须要返回最近的 k 个结果。类似的情况还有很多，比如说，我们要查询最近的医院有哪些，查询最近的超市有哪些。那对于这一类的查询，如果当前范围内查不到，系统就需要自动调整查询范围，直到能返回 k 个结果为止。
对于这种需要动态调整范围的查询场景，我们有什么高效的检索方案呢？今天，我们就来探讨一下这个问题。
直接进行多次查询会有什么问题？
我们就以查找最近的加油站为例，一个直观的想法是，我们可以先获得当前位置的 GeoHash 编码，然后根据需求不停扩大查询范围进行多次查询，最后合并查询结果。这么说比较抽象，我们来分析一个具体的位置编码。
假设我们当前地址的 GeoHash 编码为 wx4g6yc8，那我们可以先用 wx4g6yc8 去查找当前区域的加油站。如果查询的结果为空，我们就扩大范围。扩大查询范围的思路有两种。
第一种思路是，一圈一圈扩大范围。具体来说就是，我们第一次查询周边 8 个邻接区域，如果查询结果依然为空，就再扩大一圈，查询再外圈的 16 个区域。如果还是不够，下一次我们就查询再外圈的 24 个区域，依此类推。你会发现，这种方案的查询次数会成倍地增加，它的效率并不高。
查询周边区域查询周边区域
逐步扩大查询周边区域
另一种思路是，我们每次都将查询单位大幅提高。比如说，直接将 GeoHash 编码去掉最后一位，用 wx4g6yc 再次去查询。如果有结果返回，但是不满足要返回 Top K 个的要求，那我们就继续扩大范围，再去掉一个编码，用 wx4g6y 去查询。就这样不停扩大单位的进行反复查询，直到结果大于 k 个为止。
扩大查询单位扩大查询单位
逐步扩大查询单位
和第一种查询思路相比，在第二种思路中，我们每次查询的区域单位都得到了大范围的提升，因此，查询次数不会太多。比如说，对于一个长度为 8 的 GeoHash 编码，我们最多只需要查询 8 次（如果要求精准检索，那每次查询就扩展到周围 8 个同样大小的邻接区域即可，后面我就不再解释了）。
这个检索方案虽然用很少的次数就能「查询最近的 k 个结果」，但我们还需要保证，每次的查询请求都能快速返回结果。这就要求我们采用合适的索引技术，来处理 GeoHash 的每个层级。
比如说，如果使用基于哈希表的倒排检索来实现，我们就需要在 GeoHash 每个粒度层级上都分别建立一个单独的倒排表。这就意味着，每个层级的倒排表中都会出现全部的加油站，数据会被复制多次，这会带来非常大的存储开销。那我们是否有优化存储的方案呢？
我们可以利用 GeoHash 编码一维可排序的特点，使用数组或二叉检索树来存储和检索。由于数组和二叉检索树都可以支持范围查询，因此我们只需要建立一份粒度最细的索引就可以了。这样，当我们要检索更大范围的区域时，可以直接将原来的查询改写为范围查询。具体怎么做呢？
我来举个例子。在检索完 wx4g6yc8 这个区域编码以后，如果结果数量不够，还要检索 wx4g6yc 这个更大范围的区域编码，我们只要将查询改写为「查找区域编码在 wx4g6yc0 至 wx4g6ycz 之间的元素」，就可以利用同一个索引，来完成更高一个层级的区域查询了。同理，如果结果数量依然不够，那下一步我们就查询「区域编码在 wx4g6y00 至 wx4g6yzz 之间的元素」，依此类推。
