14 | 空间检索（下）：“查找最近的加油站”和“查找附近的人”有何不同？

作者回复: 的确评论是没有提醒的，不过评论有。所以大家可以多提问。关于geohash去掉一个字符时的查询范围变化，我在这里也补充一下。 Geohash一个字符是5个比特位，由于5是奇数，因此去掉的经纬度的个数是不相等的。比如说去掉了3个经度，2个纬度。因此就会从正方形变成长方形。 而如果再去掉一个字符，那这一次正好反过来，会去掉2个经度，3个纬度。和上一次去掉的3个经度和2个纬度合起来，就正好一共去掉5个经度，5个纬度。因此又恢复成正方形。

作者回复: 你这个思考很好。四叉树能否使用b+树类似的双向链表呢？我来说说我的理解。 如果是满四叉树的话，那么我们可以将所有叶子节点使用双向链表连接起来。当我们查询到一个叶子节点不满足k个结果时，我们需要扩大范围，那么我们可以沿着左右两个方向去扩展。但是，我们是要扩展多少才OK呢？我们并不好判断新节点和当前节点的位置关系。你可以结合我文中的满四叉树的例子看看，如果查询到的节点是0110，其实离它最近的点可能是在1001区域中(见13讲中的区域编码图)，它需要往右边走三个元素才能到达这个节点。因此，遍历并无法判断当前节点和新扩展节点之间的关系。不如递归便捷。 而如果是非满四叉树的话，叶子节点不是一个层级的，并且节点还会分裂。进行链表管理会更加麻烦。

作者回复: 1.叶子节点其实存一个数组，记录所有属于这个区域的点就可以了。当然，如果你对于这个数组中的点还有其他的查询要求的话，也可以根据你的需要选用合适的数据结构，比如说不用数组，改用链表，或者位图。 2.提升的确是有限的，不是数量级的提升。但是在工程实现上，倍数级的提升其实也值得去优化。一次查询+递归返回，比多次查询会有倍数级的提升。

作者回复: 你说的对，肯定会有去重处理。不过16个编码块是覆盖4个编码块的，因此我们直接使用16个编码块的检索结果就好了。否则对四个编码块再进行去重比较，其实代价是差不多的。

作者回复: 是的。极端情况就是所有插入的数据都属于一个小区域，那么根节点就不需要分裂出其他分叉了。

作者回复: 哈哈，的确四叉树的这个用法和思路其实和前缀树很像。从这个角度来看，空间检索和字符串检索是有相似的地方的。 k-d树必须有，不过就像你说的，到了高维度以后，会有着无法精准检索的问题，因此许多高维度的相似检索问题都是使用近似最近邻检索方案来完成，而不是使用k-d树。这在后面会有介绍。

作者回复: 是的，如果是精确距离查找的话，需要用九宫格法查询周围八个格子。性能开销会变大。不过这是精准查找和非精准查找的区别，不是四叉树和数组(或二叉树)的区别。同样是精准距离查找，四叉树和数组相比，依然性能会更好一些。

作者回复: 不会的哦。如果有10这个数据的话，那么它会是和01平行的独立一个分支，并不会合并到01中。 其实你在前面已经说出了正确答案了，就是“数据分布造成的，假设有00，01和10三类节点”。 你可以看这么一个例子，根节点阈值是4，目前只存有3个数据，分别属于00，01和10三个区域。如果再加一个00区域的数据，引发了根节点分裂，那么由于数据分布只在00，01和10三个区域上，因此只需要分裂出这三个叶子节点就好，并不需要分裂出11这个没有存任何数据的叶子节点。

作者回复: 性能会有一些优化。 往上遍历，那么定位到父节点的时间代价只有o(1)，然后再往父节点的其他子节点查找，数据一定是非空的(如果其他子节点数据都是空的，那么通过父节点的数据总量统计可以快速得知，从而能快速返回更上一层)。 但如果是向外遍历，每次都要去检查周边一圈最小单位的格子是否有数据，这里面就可能有大量无效操作。 因此，基于树的查询方案会效率更高，原因是可以快速跳过许多无效检查。

作者回复: 1.内存数据如何持久化存储，这是另一个话题。其实可以参考Redis的做法，通过将内存数据存入磁盘完成持久化。 2.索引是可以单独使用，也可以组合使用的。如果单独使用的话，使用了树形索引，就不需要使用倒排索引;不过也可以组合使用:在上面几层使用树形索引，叶子节点使用倒排索引。具体的组合索引的例子，可以参考第二阶段的测试题中的例子。