Как работают быстрые карты: Contraction Hierarchies и Quadkeys

А давайте немного поговорим про карты. Вот пара кейсов из жизни разработчиков карт. Пишет Kanat Zhussipov (Senior Software Engineer, Python):

🛰 Почему ваш навигатор не тормозит? Разбираем Contraction Hierarchies (CH) Представьте: вы строите маршрут из Нью-Йорка в Бостон. Между ними ~350 километров дорог, тысячи развязок, заправок и десятки тысяч жилых тупиков в штате Коннектикут. Если искать путь обычным алгоритмом Дейкстры, он будет «заглядывать» в каждый двор по пути, проверяя: «А вдруг через эту парковку в Стэмфорде доехать до Бостона быстрее?». Это занимает секунды. Google Maps или OSM выдают результат за миллисекунды. Секрет — в Contraction Hierarchies (CH). 🏙 Пример: NY ➔ Boston Вместо того чтобы работать с «плоской» картой, CH превращает её в строгую иерархию, где каждому перекрестку присвоен ранг важности. 1. Выезд из Нью-Йорка (Climbing the Ladder) Вы стартуете из Таймс-сквер. Алгоритм запускает поиск, но с железным правилом: идти только к узлам с более высоким рангом. С узкого переулка он сразу перескакивает на авеню, оттуда — на шоссе I-95. Как только вы оказались на I-95, алгоритм «забывает» про существование съездов в маленькие городки. Для него их ранг ниже, а значит, они «невидимы». 2. Магия Shortcuts (Прыжки через штаты) На этапе подготовки (Preprocessing) алгоритм уже «схлопнул» скучные участки дорог. Вместо сотен мелких узлов на трассе между городами, у нас есть один Shortcut (ярлык) с весом, равным общему времени в пути. Поиск из Нью-Йорка просто «летит» по этим ярлыкам, не тратя ресурсы на обсчет каждого километра. 3. Встреча в Бостоне (The V-Shape Search) Одновременно запускается поиск из Бостона навстречу. Он тоже идет только «вверх» по иерархии: От вашего отеля в Бэк-Бэй ➔ на городскую магистраль ➔ на то же шоссе I-95. Два поиска встречаются в «самой высокой» точке (на главной магистрали). Область поиска выглядит не как огромный круг, а как два узких луча, направленных друг на друга. 🚀 Почему это System Design Masterpiece? Скорость: Поиск сокращается с миллионов операций до нескольких сотен. Точность: В отличие от эвристик (типа A*), CH гарантирует математически кратчайший путь. Space-Time Tradeoff: Мы тратим немного памяти на хранение ярлыков (Shortcuts), чтобы получить колоссальный выигрыш в скорости ответа (Latency). Итог: Когда вы едете в Бостон, алгоритм видит мир как сеть скоростных хайвеев. А когда вы ищете дорогу в соседний двор — он работает на «нижних этажах» той же самой иерархии.

А вот еще был случай. Пишет Ivan Petrakov (Senior Staff Software Engineer, Ruby on Rails): Н

аш поиск по карте занимал 3 секунды на запрос. Пользователи зумили и двигали карту. Каждое движение запускало новый запрос к базе. 3 секунды каждый раз. Карта казалась сломанной. Мы снизили до 300мс. Улучшение на 900%. Вот как. Старый подход: мы хранили широту и долготу в двух отдельных колонках. Каждый поиск использовал ST_DWithin или bounding box запрос с PostGIS. Работало нормально на маленьких данных. С 2 миллионами точек стало слишком медленно. Решение: quadkeys. Quadkey - это одна строка, которая кодирует местоположение на сетке тайлов карты. Думайте о нем как о почтовом индексе, но для тайлов карты. Чем длиннее строка, тем точнее локация. Зум уровень 1: мир - это 4 тайла (quadkeys: 0, 1, 2, 3) Зум уровень 15: каждый тайл - примерно квартал Вот что мы изменили: 1. Добавили колонку quadkey к каждой геолоцированной записи. Мы предрассчитали quadkeys для каждого поддерживаемого зум-уровня (с 10 по 18). 2. Заменили PostGIS bounding box запросы на простой поиск по префиксу строки. Вместо: WHERE ST_DWithin(point, user_location, radius) Теперь: WHERE quadkey LIKE '0213012%' Поиск по префиксу строки на индексированной колонке работает очень быстро. 3. Добавили составные индексы: (zoom_level, quadkey). 4. Предагрегировали количество точек на quadkey для кластерных представлений. При отдалении показываем кластеры с количеством. Не нужно загружать отдельные точки. Результат: 3 секунды стали 300мс. Карта работает мгновенно. Пользователи могут зумить и двигать карту без ожидания.