Comment mettre en œuvre au mieux la recherche de voisin le plus proche dans mysql?

Bref,

1. Quel devrait être le type de données de latitude et de longitude?
2. Quelle commande SQL dois-je appeler pour obtenir les 100 premiers restaurants les plus proches par exemple?

Détail:

J'ai 100k biz record chacun avec lattitude et longitude. Je vois que MySQL supporte en fait un type de données appelé point. Dois-je utiliser cela à la place?

MySQL prend-il en charge le système de stockage KDTree http://en.wikipedia.org/wiki/File:KDTree-animation.gif

Est-il préférable d'utiliser le type de données ponctuelles plutôt que le type de données flottant normal pour stocker la latitutude et la longitude?

Finalement, je veux trouver des choses comme les 100 premiers restaurants les plus proches des points 105,6 par exemple et mes bases de données contiennent beaucoup de biz et de points. Évidemment, calculer la distance un par un pour chaque enregistrement et pour chaque point serait O (n) et donc nul.

Notez que je connais une solution plus simple décrite dans Comment une application comme Yelp Récupère-t-elle efficacement les informations de distance de la base de données et que je les implémenterai moi-même pour commencer. Voilà une bonne réponse.

Cependant, je pense qu'il y a une crème de la réponse de la culture qui devrait surpasser ce droit? En fait, stocker l'emplacement en fonction de la latitude et de la longitude et trouver des objets les plus proches est un problème très courant, je m'attends à ce que mysql ait un modèle de conception spécial pour cela. At-il cela?

Où puis-je en savoir plus à ce sujet? Merci.

En ce qui concerne les modèles de conception, la question Yelp est assez standard.

Pour une réponse plus complexe, vous aurez probablement besoin de la distance géospatiale. Voici un powerpoint fascinant sur ce sujet (et en voici également une version pdf). Cependant, les mathématiques impliquées sont assez laides.

De leur diapositive:

set @orig_lat=122.4058; set @orig_lon=37.7907;
set @dist=10;

SELECT *, 3956 * 2 * ASIN(SQRT(
POWER(SIN((@orig_lat - abs(dest.lat)) * pi()/180 / 2), 2) +  COS(@orig_lat * pi()/180 ) * COS(abs(dest.lat) * pi()/180) *  POWER(SIN((@orig_lon – dest.lon) * pi()/180 / 2), 2) )) as  distance
FROM hotels dest 
having distance < @dist
ORDER BY distance limit 10

Il y a une réponse plus longue et plus approfondie sur la distance géospatiale sur Stack Overflow .

Mais vous voulez toujours limiter les résultats par la latitude et la longitude.

En fin de compte, j'éviterais le type de données POINT et j'irais avec la latitude / longitude. Il n'y a actuellement aucun moyen de déterminer la distance entre deux POINTS, vous devrez donc de toute façon stocker la latitude / longitude pour ce calcul.

Un dernier lien: vous pouvez également consulter ce fil SO concernant l'accélération des requêtes à l'aide d'index spatiaux.

Les types de données de point sont OK; vous pouvez simplement appeler X (coord) / Y (coord) pour obtenir les valeurs Lat / Lon.

Par exemple:

SELECT id, 
(3959 
    * acos(
        cos(radians(37)) 
        * cos(radians(Y(coord)))
        * cos(radians(X(coord)) - radians(-122)) 
        + sin(radians(37))
        * sin(radians(Y(coord)))
      )
) AS distance 
FROM markers HAVING distance < 25 
ORDER BY distance LIMIT 20;

Trouvez les 100 restaurants les plus proches d'une coordonnée: Voir le code efficace dans http://mysql.rjweb.org/doc.php/latlng Il comprend une fonction stockée pour calculer la distance du "grand cercle".