mysql - 基于Peano-hilbert曲线的索引？

Question

我在 MySQL 中存储了 ax,y,z 3D 点，我想询问区域、切片或点邻居。有没有办法使用 Peano-Hilbert 曲线来索引点以加速查询？还是有更有效的方法将 3D 数据存储在 MySQL 中？

谢谢阿曼。

Answer 1

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

这应该允许您快速过滤掉肯定不在附近的点。在绝对最坏的情况下，您仍然需要扫描超过 25% 的表格才能找到某个区域内的点。

解决方法是将 xyz 拆分为二进制并使用曲线将它们拼接成单个值。我希望我已经准备好一个 SQL 脚本，但我只有一个用于 2d z 曲线的脚本，这要容易得多。

编辑：

抱歉，您可能已经知道所有这些，实际上只是在寻找 SQL 示例，但我有一些补充：

• 我不确定 25% 的最坏情况扫描是否适用于 3D 平面。它可能更高，现在没有脑力告诉你;)。
• 这种类型的曲线将帮助您找到需要搜索的范围。如果您有 2 个坐标，则可以将它们转换为希尔伯特曲线数，以找出您需要在表的哪个部分查找与您的查询完全匹配的项目。
• 您也许可以扩展此概念以查找邻居，但为了使用曲线，您仍然“卡住”在范围内查找。

Answer 2

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

XXXXa < the_hash < XXXXz