如何在范围搜索中使用Morton Order（z order curve）？
How to use Morton Order(z order curve) in range search?
如何在范围搜索中使用Morton Order？
来自wiki，在段落"Use with one-dimensional data structures for range searching"，
它说
"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) 有没有网络博客演示如何进行范围搜索？
维基百科文章中引用的例子似乎没有经过编辑来阐明上下文和假设。该示例中使用的方法适用于仅允许顺序（向前和向后）查找的线性数据结构；也就是说，假设不能仅使用其 morton 索引在恒定时间内随机寻找存储单元。
有了这个约束，一个人的策略从一个完整的范围开始，即最小莫顿指数 (16) 和最大莫顿指数 (45)。为了进行优化，人们试图找到并消除查询矩形之外的大片子范围。图中的阴影区域指的是如果未应用此类优化（消除子范围）将（顺序）访问的内容。
在讨论完线性时序数据结构的主要优化策略后，接着谈其他具有更好寻道能力的数据结构。
编辑： AWS 数据库博客现在有 a detailed introduction to this subject.
This blog post 合理地说明了这个过程。
搜索矩形时 space x=[2,3], y=[2,6]:
- 最小 Z 值 (12) 是通过交错最低
x 和 y 值的位找到的：分别为 2 和 2。
- 通过交错最高
x 和 y 值的位来找到最大 Z 值 (45)：分别为 3 和 6。
- 找到最小和最大 Z 值（12 和 45）后，我们现在有一个可以迭代的线性范围，保证包含矩形 space 内的所有条目。线性范围内的数据将是我们实际关心的数据的 超集 ：矩形 space 中的数据。如果我们简单地遍历整个范围，我们将找到我们关心的所有数据，然后再找到一些。您可以测试您访问的每个值，看看它是否相关。
一个明显的优化是尽量减少必须遍历的多余数据量。这主要是您在数据中穿过的 'seams' 数量的函数——'Z' 曲线必须进行大幅跳跃才能继续其路径的地方（例如，从下面的 Z 值 31 到 32） .
这可以通过使用 BIGMIN 和 LITMAX 函数来识别这些接缝并导航回矩形来缓解。为了尽量减少我们评估的不相关数据的数量，我们可以：
- 记录我们访问过的连续垃圾数据的数量。
- 决定此计数的最大允许值 (
maxConsecutiveJunkData)。顶部链接的博客 post 使用 3 作为此值。
- 如果连续遇到
maxConsecutiveJunkData条不相关的数据，我们发起BIGMIN和LITMAX。重要的是，在我们决定使用它们的时候，我们现在处于线性搜索 space（Z 值 12 到 45）但 外部 矩形的某个位置搜索 space。在维基百科文章中，他们似乎选择了 4 的 maxConsecutiveJunkData 值；他们从 Z=12 开始，一直走到矩形外的 4 个值（超过 15），然后才决定现在是使用 BIGMIN 的时候了。因为 maxConsecutiveJunkData 由您决定，所以 BIGMIN 可用于线性范围内的任何值（Z 值 12 到 45）。有点令人困惑的是，该文章仅将 19 之后的区域显示为交叉影线，因为这是搜索的子范围，当我们使用 BIGMIN 且 maxConsecutiveJunkData 为 4 时将被优化掉。
当我们意识到我们已经超出矩形太远时，我们可以得出 non-contiguous 中的矩形的结论。 BIGMIN 和 LITMAX 用于标识拆分的性质。 BIGMIN 旨在，给定线性搜索中的任何值 space（例如 19），找到下一个最小值，该值将回到具有较大 Z 值的分割矩形的一半内（即跳转我们从 19 到 36）。 LITMAX 类似，帮助我们找到 Z 值较小的分割矩形的一半内的最大值。 BIGMIN 和 LITMAX 的实现在链接博客 post.
的 zdivide 功能解释中有深入的解释
如何在范围搜索中使用Morton Order？ 来自wiki，在段落"Use with one-dimensional data structures for range searching"，
它说
"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) 有没有网络博客演示如何进行范围搜索？
维基百科文章中引用的例子似乎没有经过编辑来阐明上下文和假设。该示例中使用的方法适用于仅允许顺序（向前和向后）查找的线性数据结构；也就是说，假设不能仅使用其 morton 索引在恒定时间内随机寻找存储单元。
有了这个约束，一个人的策略从一个完整的范围开始，即最小莫顿指数 (16) 和最大莫顿指数 (45)。为了进行优化，人们试图找到并消除查询矩形之外的大片子范围。图中的阴影区域指的是如果未应用此类优化（消除子范围）将（顺序）访问的内容。
在讨论完线性时序数据结构的主要优化策略后，接着谈其他具有更好寻道能力的数据结构。
编辑： AWS 数据库博客现在有 a detailed introduction to this subject.
This blog post 合理地说明了这个过程。
搜索矩形时 space x=[2,3], y=[2,6]:
- 最小 Z 值 (12) 是通过交错最低
x和y值的位找到的：分别为 2 和 2。 - 通过交错最高
x和y值的位来找到最大 Z 值 (45)：分别为 3 和 6。 - 找到最小和最大 Z 值（12 和 45）后，我们现在有一个可以迭代的线性范围，保证包含矩形 space 内的所有条目。线性范围内的数据将是我们实际关心的数据的 超集 ：矩形 space 中的数据。如果我们简单地遍历整个范围，我们将找到我们关心的所有数据，然后再找到一些。您可以测试您访问的每个值，看看它是否相关。
一个明显的优化是尽量减少必须遍历的多余数据量。这主要是您在数据中穿过的 'seams' 数量的函数——'Z' 曲线必须进行大幅跳跃才能继续其路径的地方（例如，从下面的 Z 值 31 到 32） .
这可以通过使用 BIGMIN 和 LITMAX 函数来识别这些接缝并导航回矩形来缓解。为了尽量减少我们评估的不相关数据的数量，我们可以：
- 记录我们访问过的连续垃圾数据的数量。
- 决定此计数的最大允许值 (
maxConsecutiveJunkData)。顶部链接的博客 post 使用3作为此值。 - 如果连续遇到
maxConsecutiveJunkData条不相关的数据，我们发起BIGMIN和LITMAX。重要的是，在我们决定使用它们的时候，我们现在处于线性搜索 space（Z 值 12 到 45）但 外部 矩形的某个位置搜索 space。在维基百科文章中，他们似乎选择了4的maxConsecutiveJunkData值；他们从 Z=12 开始，一直走到矩形外的 4 个值（超过 15），然后才决定现在是使用BIGMIN的时候了。因为maxConsecutiveJunkData由您决定，所以BIGMIN可用于线性范围内的任何值（Z 值 12 到 45）。有点令人困惑的是，该文章仅将 19 之后的区域显示为交叉影线，因为这是搜索的子范围，当我们使用BIGMIN且maxConsecutiveJunkData为 4 时将被优化掉。
当我们意识到我们已经超出矩形太远时，我们可以得出 non-contiguous 中的矩形的结论。 BIGMIN 和 LITMAX 用于标识拆分的性质。 BIGMIN 旨在，给定线性搜索中的任何值 space（例如 19），找到下一个最小值，该值将回到具有较大 Z 值的分割矩形的一半内（即跳转我们从 19 到 36）。 LITMAX 类似，帮助我们找到 Z 值较小的分割矩形的一半内的最大值。 BIGMIN 和 LITMAX 的实现在链接博客 post.
zdivide 功能解释中有深入的解释