MaximSpb,

обычно создается индекс по двум полям и задаются условия на запрос А<широта<В, С<долгота<Д

MaximSpblLocustMaximSpb,

обычно создается индекс по двум полям и задаются условия на запрос А<широта<В, С<долгота<Д

есть понимание как это внутри работает?

Есть. А у Вас?

MaximSpbу меня есть мильён объектов вида (Ид, Долгота, Широта)
Это не много, у меня есть миллиард объектов вида (Ид,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...,...)

MaximSpbКак оптимально искать, абстрагируясь от конкретных БД вообще и SQL в частности. Т.е. Вас интересует как сделать свой поиск? а зачем, если не секрет?

MaximSpb,

Для таких случаем покупают дополнительной оперативки и хранят базу в памяти.
Далее, как все это устроено в базе (если просто и на пальцах), то в виде дерева, уже отсортированного (примеров дофига искать по словам b-tree , ну да ладно), например в базе есть числа:

1368910111545

>9
/ \
>6 >11
/ \ / \
... ... ... ...
т.е. при поиске числа 11 мы его сравниваем с 9, потом с 11 и т.д. вниз по дереву пока не дойдем до него (это ищем нижнюю границу), потом так же ищем верхнюю границу, потом берем все числа внутри... лучше почитать Кайта, у него неплохо все описано... Если индекс по двум полям, то принцип тот же.

Далее, а что у вас за база? которую вы чуть ли не ручками сортируете, что бы потом по ней пробежаться?
Повторюсь, индексы работают по другому. и поиск по индексу более чем оптимальный (самому такой реализовать сложно..., да и нужно ли?)

Далее, 1 миллион - это не много, тем более, что информация у Вас довольно упорядочена и ее мало (всмысле 1 запись - это всего 3 числа), т.е. дерево индекса будет сбалансировано.
Просто сделайте индекс по двум полям (можно даже 2 индекса, по принципам ширина/долгота и долгота/ширина) и посмотрите планы запросов что получилось.
И количество запросов тут практически не при чем...