10

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

它说

“被查询的范围（x = 2, ..., 3, y = 2, ..., 6）用虚线矩形表示。它的最高Z值（MAX）是45。在这个例子中，值在 Z 值递增方向搜索数据结构时遇到 F = 19。......BIGMIN（示例中为 36）......仅在 BIGMIN 和 MAX 之间的区间内搜索......"

我的问题是：

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

2) 如何获得BIGMIN？

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

4

2 回答 2

11

编辑： AWS 数据库博客现在详细介绍了这个主题。

这篇博文很好地说明了这个过程。

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

  1. 最小 Z 值 (12) 是通过交织最低x和y值的位来找到的：分别为 2 和 2。
  2. 最大 Z 值 (45) 是通过交织最高位x和y值的位来找到的：分别为 3 和 6。
  3. 找到最小和最大 Z 值（12 和 45）后，我们现在有了一个可以迭代的线性范围，保证包含矩形空间内的所有条目。线性范围内的数据将成为我们真正关心的数据的超集：矩形空间中的数据。如果我们简单地遍历整个范围，我们将找到我们关心的所有数据，然后是一些。您可以测试您访问的每个值以查看它是否相关。

一个明显的优化是尽量减少必须遍历的多余数据量。这在很大程度上取决于您在数据中穿过的“接缝”数量——“Z”曲线必须进行较大跳跃才能继续其路径的地方（例如，从 Z 值 31 到下面的 32）。

Z顺序曲线范围遍历

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

  1. 记录我们访问过的连续垃圾数据的数量。
  2. 确定此计数的最大允许值 ( maxConsecutiveJunkData)。顶部链接的博客文章使用3此值。
  3. 如果我们maxConsecutiveJunkData连续遇到一些不相关的数据，我们会启动BIGMINand LITMAX。重要的是，在我们决定使用它们时，我们现在位于线性搜索空间内（Z 值 12 到 45）但在矩形搜索空间之外。在 Wikipedia 文章中，他们似乎选择maxConsecutiveJunkData了4; 他们从 Z=12 开始，一直走到矩形外的 4 个值（超过 15 个），然后才决定现在是使用BIGMIN. 因为maxConsecutiveJunkData是随心所欲，BIGMIN可用于线性范围内的任何值（Z 值 12 到 45）。有点令人困惑的是，这篇文章只将 19 岁以后的区域显示为交叉阴影线，因为这是我们使用时将优化的搜索子范围BIGMIN与maxConsecutiveJunkData4。

当我们意识到我们已经在矩形之外游荡得太远了，我们可以得出结论，矩形是不连续的。BIGMIN并LITMAX用于识别分裂的性质。BIGMIN被设计为，给定线性搜索空间中的任何值（例如 19），找到下一个最小值，该最小值将回到具有较大 Z 值的分割矩形的一半内（即从 19 跳到 36）。LITMAX是相似的，帮助我们找到最大的值，它将在具有较小 Z 值的分割矩形的一半内。BIGMIN和的实现在链接的博客文章LITMAX中的功能解释中进行了深入解释。zdivide

于 2016-01-22T22:02:46.443 回答
0

维基百科文章中引用的示例似乎没有经过编辑以澄清上下文和假设。该示例中使用的方法适用于仅允许顺序（向前和向后）搜索的线性数据结构；也就是说，假设不能仅使用其 morton 索引在恒定时间内随机寻找存储单元。

有了这个约束，一个人的策略从一个完整的范围开始，即最小 morton 指数 (16) 和最大 morton 指数 (45)。为了进行优化，人们试图找到并消除查询矩形之外的大片子范围。图中的阴影区域是指如果没有应用这种优化（消除子范围），将会（按顺序）访问的内容。

在讨论了线性顺序数据结构的主要优化策略之后，继续讨论其他具有更好搜索能力的数据结构。

于 2015-05-15T02:28:17.773 回答