基於Peano-Hilbert曲線的索引？

Question

我有一個存儲在MySQL中的x，y，z三維點， 我想問一下區域，切片或點的鄰居。 有沒有辦法使用Peano-Hilbert曲線對點進行索引來加速查詢？ 還是有更有效的方式來存儲在MySQL的3D數據？

謝謝阿爾曼。

Answer 1

我個人從未走過這麼遠，但我用Z曲線來存儲2D點。這工作得很好，並沒有覺得有必要嘗試實現希爾伯特曲線以獲得更好的結果。

這應該可以讓你快速過濾掉那些並不靠近的點。在絕對最壞的情況下，您仍然需要掃描超過25％的表格才能找到某個區域內的點。

解決問題的方法是將x y z分成二進制文件，並使用曲線將它們拼接成單個值。我希望我已經準備好了一個SQL腳本，但是我只有一個用於2d z曲線的工具，這個工作要容易得多。

編輯：

對不起，你可能已經知道這一切已經和真的只是尋找SQL樣品，但我有一些補充：

• 我不知道25％的最壞情況3D平面掃描也是如此。它可能更高，現在沒有足夠的智能來告訴你;）。
• 這種類型的曲線將幫助您找到您需要搜索的範圍。如果您有2個座標，則可以將這些座標轉換爲希爾伯特曲線數字，以找出需要查找與您的查詢完全匹配的項目的哪個部分。
• 您可能可以將此概念擴展爲查找鄰居，但爲了使用曲線，仍然「卡住」以查看範圍。

Answer 2

您可以使用該算法創建geohash，並將其擴展爲3個座標。基本上，你定義的將有一個可能的3d點的世界立方體，然後當你添加更多的位時，你縮小了立方體的範圍。然後您一致地定義它，以便左下角具有最小值，並且您可以執行範圍檢查，如：

XXXXa < the_hash < XXXXz