基于Peano-Hilbert曲线的索引？

我有一个存储在MySQL中的x，y，z三维点，我想问一下区域，切片或点的邻居。有没有办法使用Peano-Hilbert曲线对点进行索引来加速查询？还是有更有效的方式来存储在MySQL的3D数据？基于Peano-Hilbert曲线的索引？

谢谢阿尔曼。

来源

2010-09-22 Arman

我个人从未走过这么远，但我用Z曲线来存储2D点。这工作得很好，并没有觉得有必要尝试实现希尔伯特曲线以获得更好的结果。

这应该可以让你快速过滤掉那些并不靠近的点。在绝对最坏的情况下，您仍然需要扫描超过25％的表格才能找到某个区域内的点。

解决问题的方法是将x y z分成二进制文件，并使用曲线将它们拼接成单个值。我希望我已经准备好了一个SQL脚本，但是我只有一个用于2d z曲线的工具，这个工作要容易得多。

编辑：

对不起，你可能已经知道这一切已经和真的只是寻找SQL样品，但我有一些补充：

我不知道25％的最坏情况3D平面扫描也是如此。它可能更高，现在没有足够的智能来告诉你;）。
这种类型的曲线将帮助您找到您需要搜索的范围。如果您有2个坐标，则可以将这些坐标转换为希尔伯特曲线数字，以找出需要查找与您的查询完全匹配的项目的哪个部分。
您可能可以将此概念扩展为查找邻居，但为了使用曲线，仍然“卡住”以查看范围。

来源

2010-09-22 12:51:13 Evert

感谢您的回答，我可以尝试Z曲线（或者在3D中，有时它被称为莫顿排序）。我看到了PostgreSQL的一个插件：http://www.sai.msu.su/~megera/wiki/README_q3c也许会有另外一个用于MySQL ... – Arman 2010-09-22 14:36:31

对不起，对于Z的最坏情况-Curve（morton number）为50％，希尔伯特曲线为25％。我在我的博客上写了一组关于Z曲线的一些小文章：http://www.rooftopsolutions.nl/blog/search?criteria=morton – Evert 2010-09-22 15:04:43

您可以使用该算法创建geohash，并将其扩展为3个坐标。基本上，你定义的将有一个可能的3d点的世界立方体，然后当你添加更多的位时，你缩小了立方体的范围。然后您一致地定义它，以便左下角具有最小值，并且您可以执行范围检查，如：

XXXXa < the_hash < XXXXz

来源

2010-09-22 12:52:06

Geohash是一个z曲线。 – Evert 2010-09-22 12:55:35

基于Peano-Hilbert曲线的索引？

回答

相关问题