Ниже — практическое сравнение четырёх подходов для задачи «хранить ~1M гео-точек и часто отвечать на k‑NN $найтиближайшиеN$». Для каждого — суть, плюсы/минусы, сложность, оценка потребления памяти/времени и рекомендации когда выбирать.

Общие замечания, важные для всех решений

Метрика: на масштабах города можно использовать евклидову метрику в метрической проекции $UTM,WebMercatorспоправкой$. Для глобальных запросов лучше сравнивать по великому кругу $haversine$ или представить точки как единичные векторы в ECEF $3D$ и искать по косинусу угла.Динамика данных: частые вставки/удаления меняют выбор — некоторые структуры проще обновлять.Точность vs скорость: точные kNN обычно дороже; для высокой нагрузки часто используют приближённые методы $HNSW,Annoy$.Практический объём памяти сильно зависит от реализации/языка/библиотеки. Приведу оріентационные оценки.

1) R‑дерево $R-tree,GiST/RTREE$ Кратко: иерархическая структура прямоугольных MBR $boundingboxes$. Часто используется в СУБД $PostGIS$, доступна на диске.

Плюсы

Хорош для диапазонных и пересечений $bbox,полигоны$ + kNN.Поддерживает динамические вставки/удаления $безполнойперестройки$.Может храниться на диске — подходит для данных, что не помещаются в RAM $B-tree-подобноеповедение$.Простая интеграция со СУБД/пространственными библиотеками.

Минусы

Производительность kNN зависит от перекрытия MBR; в худшем случае много проверок.Тонкая настройка $минимальный/максимальныйфакторветвления$ и качество bulk-load важны.На точные глобальные расстояния часто нужно доп. вычисления $MBRприближает$.

Временная сложность

Среднее: близко к O$logn$ для поиска/узла; kNN — зависит от распределения и перекрытия, практически быстро.Худшее: может деградировать до O$n$ при сильном перекрытии.

Память $ориентир$

В памяти: накладные данные на узлы; для 1M точек обычно десятки МБ до сотен МБ в зависимости от реализации и размера ветвления. На диске — индекс занимает порядки МБ — десятков МБ.

Когда выбирать

Нужны динамические обновления + точные результаты + интеграция в СУБД.Если данные большие и нужно хранить/обслуживать на диске.

2) k‑d дерево
Кратко: бинарное дерево разбиений по осям $для2D—простаяиэффективнаяструктурадляточныхkNN$.

Плюсы

Очень быстрые точные kNN в среднем, особенно для низкоразмерных данных $2D$.Простая реализация, хороша в памяти при аккуратной упаковке.Отлично для статических/редко меняющихся наборов $bulkbuild$.

Минусы

Плохо реагирует на частые динамические вставки/удаления — нужны ре-балансировки или деревья с периодическими перестройками.В худшем $вырожд.распределение$ может деградировать $поискпосетитмногоузлов$.На глобальной сфере надо правильно выбрать проекцию/метрику $можностроитьпо3Dкоординатамнаединичнойсфере$.

Временная сложность

Среднее: O$logn$ на одно NN $точныйkNN—O(logn+k)$, в 2D худшее ≈ O$sqrt(n)$ в специфических случаях.Практическая латентность: обычно микросекунды–миллисекунды на запрос при 1M точек в памяти.

Память $ориентир$

Простая in-memory реализация — порядка tens of bytes на точку плюс сама точка. Для 1M: от 50MB до ~200MB в зависимости от языка/структуры.

Когда выбирать

Данные статичны или редко меняются, требуется точность и низкая задержка.Можно поместить весь индекс в оперативную память.

3) Хеш-таблица с геокодированием $grid/geohash/S2cells$ Кратко: разбить пространство на ячейки $geohash,Hilbert,S2$, хранить хеш->список точек; при запросе берём ячейку + соседние ячейки до тех пор, пока не набрали кандидатов.

Плюсы

Очень простая реализация; O$1$ локальная выборка ячейки.Быстро генерирует кандидатов — хорошая эвристика для kNN.Легко масштабируется $шардингпоячейкам$, просты обновления.Контроль компромисса производительность/точность через размер клетки.

Минусы

Нужно выбирать разрешение ячеек: слишком большое — много точек в ячейке; слишком маленькое — придётся проверять много соседних ячеек.Для некоторых распределений $скопления,границыклеток$ придётся брать много соседних клеток.Сам по себе не даёт гарантии точности — нужно доказывать/проверять кандидатов; может потребоваться большая доп. выборка.

Временная сложность

На каждый запрос — O(#кандидатов) для проверки; если разрешение хорошее, обычно значительно меньше n.Характерно быстрое время генерации кандидатов $O(1)похешу$.

Память $ориентир$

Хеш-таблица + списки: зависит от числа ячеек с данными. Для разумного разрешения — comparable с простым массивом данных плюс указатели: десятки–сотни МБ.

Когда выбирать

Хотите простую, масштабируемую систему с быстрыми ответами и возможностью шардинга.Подходит для приближённых/гибридных схем: geohash -> локальный точный поиск $k-dtree/bruteforceвячейке$.Очень хорошо для динамических данных и горизонтального масштабирования.

4) Простой перебор $brute‑force$ Кратко: хранить массив точек и на каждый запрос вычислять расстояние до всех точек, затем выбрать N ближайших.

Плюсы

Очень простая реализация; минимальные накладные структуры.Не требует перестроек, хорошо параллелится $SIMD,GPU$.Гарантированно точный результат.

Минусы

O$n$ на запрос — для n=1e6 это дорого: на одном ядре сотни миллисекунд до секунд в зависимости от точности расстояния $haversinevsприблизительные$.При высокой QPS $сотни/тысячизапросоввсекунду$ неприемлемо.Тяжёлая нагрузка на CPU, даже при оптимизациях.

Оценка времени $примерныечисла$

Если вычислять "тяжёлый" haversine/арктангенсы для 1e6 точек — обычно десятки–сотни миллисекунд на запрос на современном CPU; с нагрузкой QPS>10 придётся масштабировать по ядрам/машинам.С оптимизациями $напримерсравнениев3Dвекторами,SIMD$ можно снизить время, но всё равно линейная зависимость остаётся.

Когда выбирать

Небольшая частота запросов $развнесколькосекунд$, или прототип/отладка.Когда допускается батч-обработка, либо вы планируете использовать GPU/векторные ускорители.

Дополнительные варианты и приближённые методы

Приближённые NN $HNSW,Annoy,FAISS$: очень быстрые kNN $субмиллисекундные$, память больше $несколькоразразмерданных$, возможная небольшая потеря точности. Отлично при высоком QPS и когда допускается approximate.Пространственно упорядоченные индексы $Morton/Z-order$ + B-tree: хороши для дисковых/распределённых реализаций.Комбинации: geohash -> candidate set -> точный kd-tree/R-tree/ brute force внутри ячеек.

Какие требования к памяти и времени учесть при выборе $чек-лист$

QPS и целевое время отклика $p95latency$: нужен sub-ms, ms, или сотни ms?Точность: допустима ли приближённость? Если нет — требуются точные структуры.Динамичность: частые вставки/удаления или в основном статичный набор?Память на машину $хочетсявRAMвесьиндекс?$ или допустимо хранение на диске/СУБД?Распределение точек: равномерно по поверхности или сильно кластерованные?Метрика расстояния: локальная проекция/евклидова или глобальная $haversine$?Параллелизм и масштабирование: можно ли горизонтально шардировать?Реализация/экосистема: готовые библиотеки $libspatialindex,nanoflann,FLANN,HNSWlib,PostGIS$ vs писать с нуля.Накладные расходы языка/GC $Go/Java/Pythonтребуютбольшиенакладныенаобъекты$.

Рекомендации по сценариям

Нужны точные kNN, данные статичны и весь индекс помещается в RAM: k-d tree $илиnanoflann$ — быстрый и компактный, либо 3D kd-tree для глобальной сферы.Нужна поддержка частых динамических обновлений + точность +/или диск: R-tree $либоСУБДсGiST/RTREE$.Высокий QPS и допустимы приближённые ответы: HNSW $HNSWlib$ или Annoy — очень быстрые, часто лучший выбор для production kNN.Простая масштабируемая система с гибридной стратегией: geohash grid для первичного фильтра → точный поиск внутри кандидатов.Небольшой QPS или прототип: brute-force $впамяти$ — самый простой путь.

Коротко по практическим числам $ориентирами$

Объём сырых координат для 1e6 точек $x,yкакdouble$: ~16 MB. С идентификаторами/метаданными/индексом — реально 50–300+ MB в production-зависимости от языка и структуры.Brute-force на 1e6 точек: десятки–сотни ms на запрос на одном ядре $зависитотфункциирасстояния$. Неприемлемо при QPS>10–100.k-d / R-tree в памяти: запросы в диапазоне micro–milliseconds до low milliseconds при k небольшом; HNSW — sub-ms.

Итог

Если нужна точная и быстрая $низкаялатентность$ обработка большого потока kNN-запросов — предпочитайте in-memory индекс: kd-tree для статичных 2D/3D, либо приближённый граф $HNSW$ если допустима аппроксимация.Если данные динамичны и/или должны храниться на диске/в СУБД — R-tree/GiST.Если важна простота/шардинг — geohash/grid + локальный поиск.Brute-force — только для низкой нагрузки/прототипов или для векторизованного GPU-ускорения.

Если хотите, могу:

предложить конкретные библиотеки/реализации для выбранного языка $C++/Go/Java/Python/Postgres$;прикинуть примерную память и латентность для вашей конкретной нагрузки $QPS,требуемаяp95,частотаобновлений,точность$.