13 | 空间检索（上）：如何用Geohash实现“查找附近的人”功能？
使用非精准检索的思路实现“查找附近的人”
请订阅文章所属专栏。
精选留言(7)
一步1:
用户量不大的时候：直接可以进行计算具体，这里因为用户的数据是一致在变化的，所以保存的数据结构可以使用 树 和 跳表， 都可以在 log(n) 的时间复杂度中进行查询
用户量很大的时候，可以使用倒排索引， 以区域的 key 建 倒排索引
2: 这里可以利用区域编码的特性，在同一大区域下的小区域的前缀是一样的
这里最小的区域范围为 4.9 km * 4.9 km ，那么可以向上找大一级的区域，此时的区域范围为 9.8 km * 9.8 km 此时还是不满足要查询的范围，所以向上找大一级的区域 此时的区域范围为 18.6 km * 18.6 km 就可以了作者回复: 回答得很清晰！
第一个问题，树和跳表都可以，都支持动态修改，并且支持范围查询，可以在log n时间复杂度内完成查询。如果用户量变大，又希望查询效率高。可以用倒排索引。
第二个问题，查询周边两圈就可以了。这样相信你能更好地理解Geohash的原理。当然，还有更多灵活的查询方式，我们下一讲再介绍。2020-04-25 1 5
qinsi把地球的球体表面投影到平面的话，相同Geohash编码长度对应的覆盖区域的大小会随着纬度高低变化的吧作者回复: 你这个问题很好。的确是这样的，由于地球是球面，直接用经纬度划分格子的话，高纬度地区和低纬度地区的一个格子的范围是不同的。这里其实存在一个误差。因此，真要精准估计区域范围的话，我们应该每隔一个经度或者纬度就累加一个偏差值才对。
不过，在查找附近的人的这类需求上，本来就是非精准检索，因此这个范围表更多是一个参考。帮助我们快速地决定需要使用的Geohash的长度。如果对精度有要求的话，可以按照按文中的思路，扩大范围，减少一个编码长度，取出更大范围的候选集进行精准计算。2020-04-24 3
峰GeoHash两维转一维编码，虽然看上去去是这样，但我老觉得很别扭，我想了想，核心我认为它并没有按照传统的单维度作为一个整体去计算，所以我更认为它是两个作用域无限的维度，转换位2*n个0，1维度表示。作者回复: 你的感觉很敏锐。如果结合后面几课一起看的话，你会发现，这其实更像是一个降维映射。而降维以后的每一个bit，都可以看做是向量的一个维度，都有它自己的意义。
最典型的例子，就是我们在计算附近区域的时候，我们其实还是还原回了原始的两个维度，分别处理。然后再合并回来。
因此，从这个角度来说，我们将这两个维度作为两个向量，单独保存，组合检索，其实也是可以的。只是在特定场景下，转为一维编码，再利用大家熟悉的一维空间的检索技术，会更简单，也更容易被大众接受。2020-05-16 2
范闲1.小数据量怎么做都可以.大数据量倒排索引+跳表，倒排加速
2.扩大查询范围，可以将GeoHash的编码减少一位。如果一开始是6位，可以变成5位去查。作者回复: 回答得很简明扼要。重点把握得不错。
2020-04-27 2- 一步这里 GeoHash 编码字符串的长度和 选定几个比特位作为一个单元和编码方式有关
这里是默认 选5个比特位作为一个单元 和 使用 base32 进行编码吗？作者回复: 是的。字符串长度和选择几个比特位作为编码单元是相关的。
一般来说，对于Geohash，我们选择5个比特位作为一个单元，使用base32编码。2020-04-25 
那时刻问题1. 如老师讲过的，在用户量不大的情况下可以采用堆排序对全部用户排序，得到结果。而当用户量增大的时候，需要对二维空间进行编码的方式来解决。区别在于数据量小的情况堆排序可以解决问题，而且不需要额外的空间。当时数据量大的情况，时间复杂度增加，需要来增加空间复杂度，也就是对于空间位置进行二分编码的方式，来降低时间复杂度。
问题2。可以采取您提到精准topk方案，取四个方位的额外4.9km区域，进行综合计算出10km附近的人。作者回复: 问题1: 数据量小的时候怎么做都行。如果出于节约空间的角度出发，用数组和链表(跳表)都可以。这样也可以做二分查找，效率也不算差。当数据量大的时候，如果觉得二分查找还不够快，那么还可以建立倒排索引，直接以编码作为key。
问题2:不错，我们是可以扩展周边区域就可以了。不过如果只扩展周围一圈的邻接区域，那么扩展半径只是4.9公里。如果我希望的扩展半径是10公里，你会怎么做呢？2020-04-24
夜空中最亮的星（华仔）干货满满，很受益2020-04-24 1