13 | 空间检索（上）：如何用Geohash实现“查找附近的人”功能？

作者回复: 回答得很清晰！ 第一个问题，树和跳表都可以，都支持动态修改，并且支持范围查询，可以在log n时间复杂度内完成查询。如果用户量变大，又希望查询效率高。可以用倒排索引。 第二个问题，查询周边两圈就可以了。这样相信你能更好地理解Geohash的原理。当然，还有更多灵活的查询方式，我们下一讲再介绍。

作者回复: 你这个问题很好。的确是这样的，由于地球是球面，直接用经纬度划分格子的话，高纬度地区和低纬度地区的一个格子的范围是不同的。这里其实存在一个误差。因此，真要精准估计区域范围的话，我们应该每隔一个经度或者纬度就累加一个偏差值才对。 不过，在查找附近的人的这类需求上，本来就是非精准检索，因此这个范围表更多是一个参考。帮助我们快速地决定需要使用的Geohash的长度。如果对精度有要求的话，可以按照按文中的思路，扩大范围，减少一个编码长度，取出更大范围的候选集进行精准计算。

作者回复: 你的感觉很敏锐。如果结合后面几课一起看的话，你会发现，这其实更像是一个降维映射。而降维以后的每一个bit，都可以看做是向量的一个维度，都有它自己的意义。 最典型的例子，就是我们在计算附近区域的时候，我们其实还是还原回了原始的两个维度，分别处理。然后再合并回来。 因此，从这个角度来说，我们将这两个维度作为两个向量，单独保存，组合检索，其实也是可以的。只是在特定场景下，转为一维编码，再利用大家熟悉的一维空间的检索技术，会更简单，也更容易被大众接受。

作者回复: 回答得很简明扼要。重点把握得不错。

作者回复: 这是一个很不错的思路，就是根据数据的出现频率来编码压缩。哈夫曼编码就是这样的一种实践。

作者回复: 是的。字符串长度和选择几个比特位作为编码单元是相关的。 一般来说，对于Geohash，我们选择5个比特位作为一个单元，使用base32编码。

作者回复: 问题1: 数据量小的时候怎么做都行。如果出于节约空间的角度出发，用数组和链表(跳表)都可以。这样也可以做二分查找，效率也不算差。当数据量大的时候，如果觉得二分查找还不够快，那么还可以建立倒排索引，直接以编码作为key。 问题2:不错，我们是可以扩展周边区域就可以了。不过如果只扩展周围一圈的邻接区域，那么扩展半径只是4.9公里。如果我希望的扩展半径是10公里，你会怎么做呢？