Добрый день.

Начну с описания БД.

1. Таблица всех пользователей.
2. Таблица пользователей с текущими координатами их геогр. местоположения.

Пользователь присылает запрос на сервер (PHP) с обновлением гео. координат.
В ответ необходимо эффективно определить идентификаторы всех пользователей в радиусе 500 м для вышеупомянутого пользователя.

Количество пользователей не ограничено.

Варианты.

1. R-tree и его модификации требуют создания дерева в памяти.
2. Множество таблиц, определяющих всех пользователей в 1 км кв.
Пользователь присылает обновление. Идёт поиск по всем существующим таблицам на вхождение точки в прямоугольник. Если "да", то вставить/обновить запись; "нет" - создать новую таблицу с центром в точке запрашивающего пользователя.
Таким образом количество этих таблиц может достичь 511 миллионов (см. площадь Земли).
3. ???
Другие варианты?

btree composite index замечательно сканится с результатом в виде квадрата 500x500 метров.