z-order-curve - 如何在范围搜索中使用Morton Order(z阶曲线)？

Question

如何在范围搜索中使用Morton Order？
在wiki中，在“使用一维数据结构进行范围搜索”段落中，

它说

"the range being queried (x = 2, ..., 3, y = 2, ..., 6) is indicated by the dotted rectangle. Its highest Z-value (MAX) is 45. In this example, the value F = 19 is encountered when searching a data structure in increasing Z-value direction. ......BIGMIN (36 in the example).....only search in the interval between BIGMIN and MAX...."

我的问题是:

1)为什么 F 是19？为什么 F 不应该为16？

2)如何获取 BIGMIN ？

3)是否有任何网络博客演示了如何进行范围搜索？

Answer 1

编辑:现在，AWS数据库博客具有a detailed introduction to this subject。

This blog post合理地说明了该过程。

搜索矩形空间x=[2,3], y=[2,6]时:

通过交织最低x和y值的最低位分别为2和2，可以找到最小的Z值(12)。

通过交织最高x和y值的最高位分别为3和6，可以找到最大的Z值(45)。

找到最小和最大Z值(12和45)后，我们现在有了一个可以迭代的线性范围，可以保证包含矩形空间内的所有条目。线性范围内的数据将是我们实际关心的数据的超集:矩形空间中的数据。如果我们只是简单地遍历整个范围，我们将找到我们关心的所有数据，然后再找到一些。您可以测试您访问的每个值，以查看它们是否相关。

一个明显的优化是尝试使必须遍历的多余数据量最小化。这很大程度上取决于您在数据中穿过的``接缝''数量-``Z''曲线必须进行大幅度跳跃才能继续其路径(例如，从Z值31到下面的32)。



这可以通过使用 BIGMIN和 LITMAX函数来标识这些接缝并导航回矩形来缓解。为了最大程度地减少我们评估的不相关数据的数量，我们可以:

记录我们访问过的连续垃圾数据的数量。

决定此计数的最大允许值(maxConsecutiveJunkData)。顶部链接的博客文章使用3表示该值。

如果我们连续遇到不相关数据的maxConsecutiveJunkData段，我们将启动BIGMIN和LITMAX。重要的是，在我们决定使用它们的时候，我们现在位于线性搜索空间内(Z值12到45)，但在矩形搜索空间之外。在Wikipedia文章中，他们似乎选择了maxConsecutiveJunkData的4值；他们从Z = 12开始，一直走到矩形之外(超过15)有4个值，然后才决定现在该使用BIGMIN了。由于maxConsecutiveJunkData随您的口味而定，因此BIGMIN可以用于线性范围内的任何值(Z值12至45)。令人困惑的是，本文仅将19处的区域显示为阴影线，因为这是当我们使用BIGMIN为4的maxConsecutiveJunkData时将被优化的搜索的子范围。

当我们意识到我们已经在矩形之外徘徊太远时，我们可以得出结论，该矩形是非连续的。 BIGMIN和 LITMAX用于标识拆分的性质。 BIGMIN的设计是，给定线性搜索空间中的任何值(例如19)，找到第二个最小值，该最小值将返回具有较大Z值的拆分矩形的一半内(即，将我们从19跳到36)。 LITMAX与之类似，可帮助我们找到最大的值，该值将位于Z值较小的拆分矩形的一半内。在链接的博客文章中的 BIGMIN 函数说明中深入介绍了 LITMAX和 zdivide的实现。