geohash-quadtree-h3.js·4 scenarios
Spatial partitioning patterns: geohash (string prefix), quadtree (recursive subdivision), H3 (Uber hexagonal grid). Use cases: nearby search, ride dispatch, surge pricing, geo-fences.
Запрос звучит просто: «найди всех drivers в радиусе 1 km от точки P». На B-tree (lat, lon) он вырождается в full scan: индекс отсортирован по одному измерению, а нам нужна 2D-близость. Близкие географически точки оказываются разнесёнными в индексе — (37.77, -122.41) и (37.78, -122.42) лежат в B-tree в разных страницах, потому что lat близок, а lon отличается.
Решение — превратить 2D-близость в 1D-порядок (или иерархию ячеек), так чтобы соседи в пространстве оказались соседями в индексе. Подходов несколько, и каждый — компромисс по форме ячейки, обработке границ и стоимости мутаций:
(lat, lon) в base32 строку через interleaving битов. Близкие точки → сходный префикс. Используют Redis GEO, Elasticsearch geo_point, Tinder, Bumble, Yelp.Killer use cases — везде, где нужны 2D-запросы: dispatch (Uber, Lyft, DoorDash), nearby search (Yelp, Foursquare), social proximity (Tinder, Bumble), POI spawning (Pokemon GO), geofencing (fitness apps), surge pricing per cell, market analytics.
«2D индекс — это способ превратить пространственную близость в индексный порядок так, чтобы радиус-запрос превратился в range scan плюс проверку соседей. Geohash делает это через space-filling curve (Z-order), S2 — через Hilbert curve, H3 — через hexagonal grid, quadtree/R-tree — через рекурсивные bounding boxes.»
Главное, что нужно держать в голове: ни один индекс не идеален на границах ячеек. Две точки на расстоянии 10 метров, лежащие по разные стороны cell boundary, могут иметь совершенно разные cell IDs. Поэтому любой radius query — это «cell + соседи + точная фильтрация по haversine», а не одиночный lookup.
Второе — trade-off между разрешением и стоимостью. Высокое разрешение даёт точные ответы, но мелкие cells часто оказываются пустыми, и нужно расширять кольцо поиска. Низкое разрешение даёт густые cells, но больше false positives под точную фильтрацию.
Канвас показывает упрощённый Uber-style dispatch:
rider (Rider app) и driver (Driver app, location ping каждые 4 секунды).dispatch-svc, центральная нода-роутер. На ней висят два ADR: один про общий выбор индекса, второй про edge-case'ы geohash.geohash-idx — base32 prefix index, capacity 80K rps × 2 replicas.quadtree-idx — рекурсивный 4-way split, 60K rps × 2.h3-idx — uint64 cell IDs, res 9 (≈100 m hex), 100K rps × 3 replicas.postgis (PostGIS R-tree GIST, 8K rps × 2). Cold path: profiles, polygons, ride state. Не используем как live dispatch index — rebalancing R-tree на mutations съедает Postgres.Edges — только физические соединения. Ответы идут reverse по тем же edges, отдельных edges «service → client» нет (см. CLAUDE.md, раздел про anti-patterns).
Сценариев четыре, они подобраны так, чтобы пройти от простого prefix scan до production-grade тонкостей H3.
1. Geohash prefix scan (radius 1 km). Rider в SF запрашивает ближайших drivers. Dispatch строит geohash[6] = "9q8yyk" (cell ≈ 1.2 km), делает range scan WHERE geohash LIKE '9q8yyk%'. Возвращается 12 драйверов. Здесь сценарий показывает edge-effect: driver на границе cell может попасть в соседний "9q8yym" и быть пропущен. Решение — geohash::neighbors() даёт 8 соседних cells, мерджим, получаем 21 кандидата, фильтруем точной haversine до 14. P99 ≈ 35 ms.
2. Quadtree hotspot split. Концерт в downtown: drivers сгущаются в одном leaf. Capacity = 8, при инсерте 9-го происходит subdivide — leaf разбивается на 4 child quadrants, 9 драйверов перераспределяются по (lat, lon). Демонстрирует адаптивность quadtree к плотности, но также trade-off: больше depth → больше pointer chasing на lookup, плюс возможный imbalance на skewed data.
3. H3 k-ring expansion (Uber dispatch). Rider request, dispatch вычисляет geoToH3(lat, lon, res=9). Self-cell пустой (на res 9 одна hex ≈ 100 m, плотности драйверов не хватает). Расширяем kRing(cell, k=1) = 7 hexagons — всё ещё мало. kRing(cell, k=2) = 19 hexagons (≈300 m radius) даёт 11 драйверов. Ключевой момент: все соседи на одинаковом расстоянии благодаря hex-геометрии, в отличие от squares где ortho-соседи ближе диагональных. Это даёт честный ETA-ranking.
4. H3 surge pricing. Тот же индекс используется аналитически: aggregate requests by cell, считаем demand/supply ratio, выводим surge_multiplier. Запись cell_surge[hex] = 2.875 с TTL=60s. Один индекс обслуживает и dispatch, и pricing, и market dashboards — это сильная сторона H3. Gotcha: 12 пентагонов на icosahedron имеют 5 соседей вместо 6 — biased aggregations там.
На ноде dispatch-svc висят два ADR; разверни их в Decisions-панели на канвасе. Краткая версия:
ADR-001: Geohash, quadtree, H3 — выбор по нагрузке и геометрии запроса.
Для high-throughput dispatch (1M drivers × 0.25 update/s = 250K writes/s/region) держим H3 cell index в Redis, а полигоны/cold path — в PostGIS на R-tree. PostGIS как primary live index не используем: rebalancing R-tree на mutations убивает Postgres.
ADR-002: Geohash gotchas — edge-effect, polar distortion, prefix ≠ real proximity.
Geohash продают как «близкие точки → сходный prefix», но это полу-правда. Две точки на расстоянии 10 м на границе cells могут иметь префиксы, расходящиеся с 6-го символа. У полюсов cells вытягиваются в полосы. 180-меридиан создаёт wrap discontinuity. Правила: (1) всегда cell + 8 neighbors для radius queries; (2) в polar regions переходить на S2/H3; (3) для cross-meridian queries — два запроса с wrap. Для Tinder/Yelp в средних широтах geohash-6 + соседи работает, для глобального Uber — лучше H3 res 9 + ring(k=2).
(lat, lon) без проекции. На расстояниях >100 м врёт; на больших — катастрофически. Используй haversine или Vincenty для точного расстояния.cell + 8 neighbors — обязательный паттерн.(cell, time_bucket), иначе придётся фильтровать миллионы записей.WHERE lat BETWEEN ... AND lon = const, B-tree (lon, lat) будет быстрее.