Кривые Гильберта и geohash

Индекс базы данных — это отсортированный список ключей. Найти ключ или все ключи в отрезке он умеет быстро: двоичным поиском или спуском по B-дереву. Но у точки на карте два числа, широта и долгота, а запрос «все землетрясения в этом прямоугольнике» — двумерный. Если сделать ключом широту, прямоугольник превратится в полосу на весь мир, из которой придётся выбрасывать почти всё. Нужен один номер для точки, такой, чтобы соседи на карте получали близкие номера. Ниже — три способа пронумеровать карту и все 19 073 землетрясения M5+ за 2015–2025 годы, раскрашенные по номеру своей клетки.

При нумерации по строкам цвет меняется по широте: соседние номера — соседи слева и справа, но соседи сверху и снизу отстоят на целую строку. Z-порядок и кривая Гильберта нумеруют карту четвертями: сначала вся четверть, потом следующая, и внутри каждой — так же. Выделите прямоугольник вокруг какой-нибудь дуги землетрясений и сравните, сколько непрерывных отрезков номеров его покрывают: столько раз базе придётся спуститься по индексу.

Идея

Разрежем карту на 2^k × 2^k клеток и пронумеруем их одной линией, которая проходит каждую клетку один раз и при этом как можно дольше задерживается в одном месте: обходит четверть карты целиком, прежде чем перейти к следующей, и внутри четверти — так же, четвертями. Такую линию называют кривой, заполняющей плоскость. Номер клетки становится ключом в индексе, прямоугольник на карте — несколькими отрезками ключей, а соседние записи в индексе — почти всегда соседями на карте.

Первую такую кривую придумал Джузеппе Пеано в 1890 году, ещё как математический курьёз: непрерывная линия, которая проходит через каждую точку квадрата. Год спустя Давид Гильберт предложил более простую — ту, что в сцене. Через семьдесят пять лет их взяли на вооружение программисты.

Z-порядок и geohash

Самый простой способ нумеровать четвертями — перемешать биты координат. Запишем номер столбца x и номер строки y в двоичной системе и составим номер клетки из их битов по очереди: бит y, бит x, следующий бит y, следующий бит x… Старшие биты выбирают четверть, следующие — четверть четверти, и линия номеров рисует букву Z, повторённую на всех масштабах. Этот порядок описал Гай Мортон из IBM в 1966 году для картографической базы данных, его называют Z-порядком или порядком Мортона.

Geohash — тот же Z-порядок, записанный буквами. Его придумал Густаво Нимейер в 2008 году: биты долготы и широты перемешиваются, и каждые пять бит превращаются в символ из 32-буквенного алфавита. У geohash есть удобное свойство: общий префикс строк означает общую клетку, и чем длиннее префикс, тем меньше клетка. В Redis команда GEOADD хранит точку как 52-битный geohash в упорядоченном множестве и ищет соседей по отрезкам этих чисел.

Слабость Z-порядка видна на картинке: между четвертями линия прыгает. После правого нижнего угла одной четверти идёт левый верхний угол следующей, и соседние номера оказываются через полкарты. Поэтому прямоугольник, который пересекает границу четверти, рассыпается на много отрезков.

Кривая Гильберта

Кривая Гильберта тоже обходит карту четвертями, но поворачивает каждую четверть так, чтобы выход из одной был рядом со входом в следующую. Соседние номера на ней — всегда соседние клетки, без прыжков. Номер считается за k шагов: на каждом шаге берётся по биту x и y, они выбирают одну из четырёх четвертей, а координаты внутри неё поворачиваются или отражаются, чтобы следующий шаг смотрел на четверть «в правильной ориентации». Это четыре строки кода, и в задаче ниже их нужно написать самому.

За отсутствие прыжков платят только вычислением: перемешать биты можно за несколько машинных инструкций, а Гильберту нужны повороты. Зато на запросах выигрыш заметный, и поэтому Google в своей библиотеке S2 нумерует клетки сферы именно кривой Гильберта, нанесённой на шесть граней куба.

Код

Три нумерации на сетке поверх карты мира. Сначала — сколько отрезков номеров покрывают прямоугольники вокруг четырёх сейсмически активных дуг, потом — как далеко друг от друга лежат землетрясения, если выстроить их по номеру.

Кривая Гильберта выигрывает на всех четырёх прямоугольниках: для Анд ей хватает 51 отрезка против 72 по строкам и 140 в Z-порядке. Z-порядок здесь хуже даже строк: вытянутые прямоугольники пересекают много границ четвертей, и на каждой линия номеров прыгает. Во второй части видно другое: выстроенные по номеру землетрясения в Z-порядке и по Гильберту чаще всего стоят в трёх клетках от предыдущего, а по строкам — в тринадцати. Прыжков больше чем на 64 клетки у Гильберта 535, у Z-порядка 696, у строк — больше семи тысяч.

Сколько это стоит

Номер клетки — O(k), где k — число бит на координату: и Z-порядок, и Гильберт делают по шагу на бит, а для Z-порядка есть и приёмы с масками, которые перемешивают биты за несколько операций. Запрос прямоугольника — это несколько отрезков номеров, и на каждый — спуск по индексу за O(log n). Сколько отрезков, зависит от размера прямоугольника в клетках и от кривой; на практике сетку выбирают так, чтобы прямоугольник покрывался десятком-другим клеток, и мирятся с тем, что вместе с ним в отрезки попадают лишние точки, — их отсеивает проверка координат.

Те же кривые полезны и без базы данных. Если обходить точки в порядке номеров, получается маршрут, близкий к кратчайшему, — это разбирает задача ниже. А матрица или картинка, разложенная в памяти по Z-кривой, удобнее для кэша: соседи по обеим осям чаще лежат в одной строке кэша.

Задачи

Задача — написать номер на кривой Гильберта и построить по нему маршрут курьера. Один из тестов — все землетрясения из этой статьи.