Jak najlepiej wdrożyć wyszukiwanie najbliższego sąsiada w mysql?

Krótko mówiąc,

1. Jaki powinien być typ danych szerokości i długości geograficznej?
2. Jakie polecenie SQL powinienem wywołać, aby na przykład uzyskać pierwsze 100 najbliższych restauracji?

Szczegół:

Mam rekord 100k biz każdy z szerokością i długością geograficzną. Widzę, że MySQL faktycznie obsługuje typ danych o nazwie point. Czy powinienem tego użyć?

Czy MySQL obsługuje system pamięci masowej KDTree http://en.wikipedia.org/wiki/File:KDTree-animation.gif

Czy do przechowywania szerokości i długości geograficznej najlepiej używać punktowego typu danych niż zwykłego typu danych zmiennoprzecinkowych?

W końcu chcę znaleźć rzeczy, takie jak pierwsze 100 restauracji najbliższych punktów 105,6, na przykład, a moje bazy danych zawierają wiele dziwnych punktów i punktów. Oczywiście obliczanie odległości jeden po drugim dla każdego rekordu i dla każdego punktu byłoby O (n) i dlatego jest do kitu.

Zauważ, że jestem świadomy prostszego rozwiązania opisanego w temacie Jak aplikacja, np. Yelp Uzyskaj efektywnie informacje o odległości z bazy danych i zaimplementuję je również na początek. To dobra odpowiedź.

Myślę jednak, że istnieje jeden krem ​​odpowiedzi na uprawę, który powinien przewyższać to prawo? W rzeczywistości, przechowywanie lokalizacji na podstawie szerokości i długości geograficznej oraz znajdowanie rzeczy najbliższych jest bardzo częstym problemem, który, jak sądzę, wymaga od mysql specjalnego wzoru projektowego. Czy to ma?

Gdzie mogę dowiedzieć się więcej na ten temat? Dzięki.

Jeśli chodzi o wzorce projektowe, pytanie Yelp jest dość standardowe.

Aby uzyskać bardziej złożoną odpowiedź, prawdopodobnie będziesz potrzebować odległości geoprzestrzennej. Tutaj jest fascynującym PowerPoint o tym temacie (i tutaj jest wersja PDF, który również). Jednak matematyka jest dość brzydka.

Ze slajdu:

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

Istnieje dłuższa, bardziej szczegółowa odpowiedź na temat odległości geoprzestrzennej w przypadku przepełnienia stosu .

Ale nadal chcesz ograniczyć wyniki według szerokości i długości geograficznej.

Ostatecznie unikałbym typu danych POINT i wybrałbym szerokość / długość geograficzną. Obecnie nie ma możliwości ustalenia odległości między dwoma PUNKTAMI, więc i tak będziesz musiał zapisać szerokość / długość geograficzną dla tego obliczenia.

Ostatni link: możesz również sprawdzić ten wątek SO dotyczący przyspieszania zapytań za pomocą indeksów przestrzennych.

Typy danych punktów są OK; możesz po prostu wywołać X (koordyn) / Y (koordyn), aby uzyskać wartości Lat / Lon.

Na przykład:

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;

Znajdź 100 restauracji najbliższych jakiejś współrzędnej: Zobacz efektywny kod w http://mysql.rjweb.org/doc.php/latlng Zawiera on funkcję zapisaną do obliczania odległości „wielkiego koła”.