¿Cómo implementar mejor la búsqueda de vecinos más cercanos en mysql?

Entonces, en resumen,

1. ¿Cuál debería ser el tipo de datos de latitud y longitud?
2. ¿Qué comando SQL debo llamar para obtener los primeros 100 restaurantes más cercanos, por ejemplo?

Detalle:

Tengo 100k biz record cada uno con latitud y longitud. Veo que MySQL realmente admite un tipo de datos llamado punto. ¿Debo usar eso en su lugar?

¿MySQL es compatible con el sistema de almacenamiento KDTree http://en.wikipedia.org/wiki/File:KDTree-animation.gif

¿Es mejor usar el tipo de datos de punto en lugar del tipo de datos flotante regular para almacenar latitud y longitud?

Finalmente, quiero encontrar cosas como los primeros 100 restaurantes más cercanos a los puntos 105,6, por ejemplo, y mis bases de datos contienen muchos negocios y puntos. Obviamente, calcular la distancia uno por uno para cada registro y para cada punto sería O (n) y, por lo tanto, es una mierda.

Tenga en cuenta que conozco una solución más simple que se describe en Cómo Aplicación como Yelp Recuperar información de distancia de la base de datos de manera eficiente y la implementaré yo también para empezar. Esa es una buena respuesta.

Sin embargo, creo que hay una crema de la respuesta del cultivo que debería superar ese derecho? De hecho, almacenar la ubicación en función de la latitud y la longitud y encontrar las cosas más cercanas es un problema muy común, espero que mysql tenga un patrón de diseño especial para eso. ¿Tiene eso?

¿Dónde puedo obtener más información al respecto? Gracias.

En cuanto a los patrones de diseño, la pregunta de Yelp es bastante estándar.

Para una respuesta más compleja, probablemente necesitará la distancia geoespacial. Aquí hay un powerpoint fascinante sobre ese tema (y aquí también hay una versión en pdf de eso). Sin embargo, las matemáticas involucradas son bastante feas.

De su diapositiva:

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

Hay una respuesta más larga y más profunda sobre la distancia geoespacial en Stack Overflow .

Pero aún desea limitar los resultados por latitud y longitud.

En última instancia, evitaría el tipo de datos POINT e iría con la latitud / longitud. Actualmente no hay forma de determinar la distancia entre dos PUNTOS, por lo que de todos modos tendrá que almacenar la latitud / longitud para ese cálculo.

Un último enlace: también puede consultar este hilo SO con respecto a la aceleración de las consultas mediante índices espaciales.

Los tipos de datos de puntos están bien; solo puede invocar X (coord) / Y (coord) para obtener los valores Lat / Lon.

Por ejemplo:

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;

Encuentre los 100 restaurantes más cercanos a alguna coordenada: consulte el código eficiente en http://mysql.rjweb.org/doc.php/latlng Incluye una función almacenada para calcular la distancia de "gran círculo".