我正在考虑使用 geohash-like 索引存储地理空间信息，也许使用希尔伯特曲线。我的问题是关于如何最好地在这样的索引上拆分区域查询。
例如，这个文章展示了人们可能希望如何将区域查询拆分为多个查询，以避免查询显示位置不佳的范围(请参阅这个图像)。如果你想使用像普通 geohash 这样的 Z 曲线用单个查询搜索圆形区域，你将不得不查询整个左下象限，它只占我们所关注区域的一小部分。
在这种情况下，最好将搜索分成几个查询，但是我无法找到有关如何最好地执行此操作的任何信息。是否存在将此类范围查询拆分为覆盖原始区域的较小范围的算法？
1 回答
一旦确定了覆盖查询边界的哈希前缀，就可以开始将该前缀拆分为组成前缀，并在保留之前测试每个前缀是否与查询边界相交。例如，假设您已将前缀 0100 标识为覆盖查询区域。前缀 0100 包含前缀 01000 和 01001，前缀 01000 包含前缀 010000 和 010001，前缀 01001 包括前缀 010010 和 010011 等。当您将前缀重写为较大前缀的集合时(对应于较小的区域)，您可以过滤掉那些与查询边界不相交的前缀。你必须在某个时候停止分裂过程;每次拆分迭代都可能使前缀集合的大小翻倍。例如，您可以创建一个最大前缀集合大小，此时您声明对过滤的满意度;当然，您可以使用其他指标来查找停止点。最后一步，您可以 re-combine“相邻”前缀，以减少您正在执行的搜索次数。例如，如果你留下前缀 01000 和 01001，你可以将它们组合成 0100，以避免搜索 01000，然后搜索 01001(假设搜索过程有超出顺序读取的开销，这是一个好处) 。您需要一个例程来计算哈希前缀的边界框，以便测试与查询边界的交集。这取决于您使用的散列方案。