Indexation basée sur la courbe de Peano-hilbert?

Question

J'ai un x, y, z points 3D stockés dans MySQL, Je voudrais demander aux régions, tranches ou points voisins. Est-il possible d'indexer les points en utilisant des courbes Peano-Hilbert pour accélérer les requêtes? Ou y at-il un moyen plus efficace de stocker les données 3D dans MySQL?

merci Arman.

Answer 1

Personnellement, je ne suis jamais allé aussi loin, mais j'ai utilisé une courbe en Z pour stocker des points 2D. Cela a très bien fonctionné, et n'a pas ressenti le besoin d'essayer de mettre en œuvre la courbe d'hilbert pour de meilleurs résultats.

Cela devrait vous permettre de filtrer rapidement les points qui ne sont pas proches. Dans le pire des cas, vous devez toujours scanner plus de 25% de votre tableau pour trouver des points dans une zone.

La façon de procéder est de diviser les x y z en binaire et de les assembler en une seule valeur en utilisant la courbe. J'aurais aimé avoir un script SQL prêt, mais j'en ai juste un pour la courbe en 2D qui est beaucoup plus facile à faire.

Modifier:

Désolé, vous savez peut-être déjà tout cela et vraiment à la recherche d'échantillons SQL, mais j'ai quelques ajouts:

• Je ne suis pas sûr que les 25% pire des cas Le scan est également vrai pour les avions 3D. Il pourrait être plus élevé, ne pas avoir le cerveau en ce moment pour vous dire;).
• Ce type de courbe vous aidera à trouver les plages où vous devez effectuer une recherche. Si vous avez 2 coordonnées, vous pouvez les convertir en nombre hilbert-curve pour trouver la section de votre table dont vous avez besoin pour rechercher les éléments qui correspondent exactement à votre requête.
• Vous pourriez être en mesure d'étendre ce concept pour trouver des voisins, mais pour utiliser la courbe, vous êtes toujours «coincé» pour regarder dans les plages.

Answer 2

Vous pouvez probablement utiliser l'algorithme pour créer un geohash et l'étendre à 3 coordonnées. Fondamentalement, vous définissez aurait un cube du monde de points 3d possibles, et puis que vous ajoutez plus de bits, vous affinez le cube. Vous pouvez ensuite définir constamment pour que le coin inférieur gauche a la plus petite valeur, et vous pouvez effectuer des contrôles de gamme comme:

XXXXa < the_hash < XXXXz