Geohashing

Проблема: близость не одномерна

Через десять минут ты будешь знать, почему индекс по (lat, lng) не решает задачу «найти рядом», как geohash сворачивает проблему в сравнение строк и где единственный острый край укусит тебя, если забыть о нём.

Локация — это два числа, широта и долгота. Базы хорошо индексируют одно измерение (B-tree на одной отсортированной колонке), но «найти точки рядом» по сути 2D: две точки могут быть соседями, различаясь по обеим координатам, поэтому B-tree на одной lat, или одной lng, или даже составной (lat, lng) не вернёт компактное множество близких строк — сортировка по широте ставит точку в Париже рядом с точкой в Бостоне (та же широта, противоположные стороны океана). Цель пространственного кодирования — отобразить 2D-пространство на 1D сортируемый ключ так, чтобы близкие в пространстве точки были обычно близки в ключе — тогда один диапазон индекса покрывает географическую окрестность.

Как работает geohash: чередование и Base32

Geohash рекурсивно делит мир пополам. Долгота охватывает −180…180, широта −90…90. Чтобы закодировать точку, ты многократно делишь каждый диапазон пополам: долгота в нижней или верхней половине? Бит 0 или 1. Затем широта: нижняя или верхняя половина? Ещё бит. Ты чередуешь биты долготы и широты (lng, lat, lng, lat, …), сужая прямоугольник каждый раз, и получившаяся битовая строка группируется в 5-битные куски, кодируемые символами Base32. Итог — короткая строка вроде u4pruyd.

Два свойства, делающие его полезным:

• Длина = точность. Каждый лишний символ сжимает ячейку примерно в 32× по площади. 5-символьный geohash — ячейка в несколько км; 7 символов — ~150 м; 9 символов — несколько метров. Ты выбираешь длину под нужную точность.
• Общий префикс = близость. Две точки в одной ячейке делят весь geohash; две точки в близких ячейках обычно делят длинный префикс. Так u4pruy* — это «всё в этой ~150 м ячейке», а range scan базы WHERE geohash BETWEEN 'u4pruy' AND 'u4pruz' возвращает точки в этой ячейке — используя обычный строковый индекс, без специальной пространственной базы.

encode(lat, lng): чередуй биты, деля каждый диапазон пополам

lng ∈ [-180,180]: верхняя половина? → 1
lat ∈ [ -90, 90]: верхняя половина? → 0
lng (уже):        нижняя половина?  → 0
lat (уже):        верхняя половина? → 1
...                                 → 10010...  →  Base32  →  "u4pruyd"

длина префикса  размер ячейки (примерно)
   4 символа       ~40 км
   5 символов      ~5 км
   6 символов      ~1 км
   7 символов      ~150 м
длина общего префикса ↑  ⇒  точки ближе друг к другу

Проблема границы

Вот ловушка, кусающая каждый поиск близости на geohash. Поскольку кодирование делит фиксированные глобальные диапазоны, смежные точки могут упасть на противоположные стороны границы ячейки и получить дико разные коды. Два водителя в 10 метрах друг от друга, но седлающие край ячейки, могут не делить никакого префикса — один u4pruy…, другой u4prv0… — хотя они почти друг на друге. Если твой запрос «рядом со мной» просто выбирает собственную ячейку пассажира (WHERE geohash LIKE 'u4pruy%'), ты пропустишь ближайшего водителя просто потому, что он на метр зашёл в соседнюю ячейку.

Стандартная починка: поиск близости должен запрашивать ячейку пассажира и её восемь соседних ячеек (сетку 3×3 вокруг точки), затем вычислять точные расстояния в этом множестве кандидатов и оставлять истинно ближайших. Вычисление восьми соседних geohash — известный алгоритм, и множество кандидатов мало, так что это дёшево — но забыть это самый частый баг geohash, и он проявляется как «приложение говорит, ближайший водитель в 800 м, когда один припаркован через улицу».

Quadtree, S2 и H3: альтернативы

Geohash — одна точка в пространстве дизайна; та же идея «1D ключ из 2D пространства» имеет уточнения:

• Quadtree. Дерево, рекурсивно делящее регион на четыре квадранта, подразделяя лишь там, где данные плотны. В отличие от geohash с фиксированной сеткой, оно адаптируется к плотности — редкие области остаются грубыми, горячие (центр города) подразделяются глубоко — что держит каждый лист в ограниченном числе точек. Geohash по сути — quadtree фиксированной глубины, закодированный строкой.
• S2 (Google). Проецирует сферу на куб и отображает каждую грань кривой Гильберта. Кривая Гильберта имеет лучшую локальность, чем Z-порядок geohash (меньше диких прыжков на швах), и ячейки S2 более однородны по площади по всему миру, избегая искажения geohash у полюсов.
• H3 (Uber). Шестиугольная сетка. У шестиугольников ключевое преимущество для близости: каждый сосед на одинаковом расстоянии (у шестиугольника шесть равноудалённых соседей), тогда как диагональные соседи квадратной ячейки дальше рёберных — что делает «расширение к соседям» чище, а рассуждение о расстоянии более однородным. H3 был построен ровно под задачу заказа поездок «водители рядом со мной».

Вместе эти три альтернативы разделяют ту же ключевую идею geohash — кодировать 2D-пространство в 1D-ключ — но каждая меняет простоту на лучшую локальность, однородную площадь ячеек или более чистую геометрию соседей. Без шага расширения к соседям (или структуры, которая его усиливает) ты будешь пропускать близкие точки, какую бы схему ни выбрал.

Ось трейдоффа: geohash крайне прост и работает на любом строковом индексе; S2/H3 дают лучшую локальность, более однородные ячейки и более чистую математику соседей ценой библиотеки и более сложной модели ячейки. Для «сохранить локацию и сделать range scan рядом в Postgres/Redis» geohash часто достаточно; для серьёзной геопространственной аналитики или однородного глобального индексирования тянись к S2 или H3.