MySQL의 성능 1km 내에있는 모든 사용자를 찾을 수

Question

나는, MySQL의 테이블이 서로 표 1km 내에있는 모든 사용자를 찾을 필요가 :

Geo 
---------- 
id(int) 
location(geometry) with spatial index 
username(string) 

가 해결 될 수 :

을 사용자가
1. 으로 반복 전 ... N 각
2. 인덱스를
3. 보내기 MSG를 사용하여 특정 다각형 내의 모든 사용자를 선택 서로

복잡도가 ~ O (n) 이상 (색인에 따라 다름)이 될 수 있습니다.

Answer 1

데이터가 2D이므로 반경을 알고 있으면 데이터에 대한 눈금 지수를 작성할 수 있습니다. 그런 다음 각 셀은 인접한 각 셀에만 메시지를 보냅니다.

셀 할당 계산은 O (n)입니다. 따라서이 작업은 이 최대 셀 점유율 인 경우 n * O(m * m)으로 가져와야합니다.

여기에 아무 것도 보증하기가 어렵다는 점에 유의하십시오. 모든 물건이 반경 1km 안에 있으면 아무 색인도 도움이되지 않습니다. 모두가 다른 사람들에게 보내야합니다. 그렇지 않으면 이차원이 될 것입니다.

Answer 2

mysql은 spatial indexes에 대해 R-Tree을 사용하므로 인덱스가 메모리에 적합하면 O (n) 성능보다 좋아야합니다.