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

Question

如何在范围搜索中使用Morton Order？从维基中,在"使用一维数据结构进行范围搜索"一节中,

它说

"被查询的范围(x = 2,...,3,y = 2,...,6)由虚线矩形表示.其最高Z值(MAX)为45.在此示例中,值在以增加的Z值方向搜索数据结构时遇到F = 19. ...... BIGMIN(示例中为36).....只搜索BIGMIN和MAX之间的间隔...."

我的问题是:

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

2)如何获得BIGMIN？

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

Answer 1

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

这篇博文可以很好地说明这个过程.

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

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

一个明显的优化是尽量减少必须遍历的多余数据量.这很大程度上取决于您在数据中交叉的"接缝"数量 - "Z"曲线必须进行大跳跃以继续其路径的位置(例如,从Z值31到32以下).

这可以通过使用BIGMIN和LITMAX函数来识别这些接缝并导航回矩形来减轻.为了最大限度地减少我们评估的无关数据量,我们可以:

1. 记录我们访问过的连续垃圾数据的数量.
2. 确定maxConsecutiveJunkData此计数的最大允许值().在顶部链接的博客文章使用3此值.
3. 如果我们maxConsecutiveJunkData连续遇到一些无关数据,我们会启动BIGMIN和LITMAX.重要的是,在这处我们决定使用他们的地步,我们现在我们的线性搜索空间内的某处(Z值12〜45),但外面的矩形搜索空间.在维基百科的文章中,他们似乎选择了一个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和实现.LITMAXzdivide