Как правильно организовать работу с БД в которой хранятся координаты в большом количестве?

Дано: MySql, около 1 млн записей. Основные поля это Широта и Долгота в которых соответственно хранятся координаты.
Необходимо вывести список координат находящихся на определенном расстоянии от заданной координаты. Делаю я это простым способом, от исходно точки высчитаю расстояние и получаю координаты квадрата с известными точками в левом верхнем углу квадарата и в правом нижнем углу квадрата, и по БД провожу выборку запросом: SELECT * FROM $table WHERE lat > '$posLat1' AND lat < '$posLat2' AND lon > '$posLon1' AND lon < '$posLon2'
То есть проводиться сплошное сравнение заданных координат с имеющимися в таблице сплошным перебором. А при таком количестве записей это дело занимает до 4х секунд. Попробовал сделать индекс по полю lat, но результат такой же.
Да и не могу я понять как будет производиться индекс поля содержащего тип Double. Может нужно создать дополнительное поле для lat в которое записывать целое число с отсечением десятичных итд, индексировать это поле и уже предварительно по нему проводить выборку? Вообщем если у кого то есть какие нибудь мысли на этот счет прошу подскажите.