Где смерть Кащеева?

Привет ребят, давайте для начала проверим вашу память. Итак:

«На море на океане есть остров, на том острове дуб стоит, под дубом сундук зарыт, в сундуке — заяц, в зайце — утка, в утке — яйцо» в яйце — смерть Кощея!

А теперь, внимание, вопрос — как это формализовать?
Как приатачить к яйцу иголку и какова временная сложность детача смертии моей. Как перенести сказку в быль, как это выглядит на B-деревьях и почему на самом деле нет разницы между 2D и 1D.
А было все так: давным давно, в неком царстве, некотором государстве, на одном сервисе с шейрингом геолокации очень захотелось Иванушке Дурачку на уровне ЧПУ разделить Москву ^[1](/RU/MOW/) и Область ^[2](/RU/MOS/). И вообще навести порядок, чтобы все лежало по полочкам красиво и по алфавиту. Но не получалось ему сокровища свои посчитать, и аккуратно разложить. А Василису, хоть и дурак, к сбережениям не пускал.
Но решение было найдено.
Совсем недалеко над каким-то златом успешно чах Чахлик, еще и смерть он свою прятал по науке.
И если задача определения региональной (точнее полигональной) принадлежности некой иголки к некому сундуку выходит за рамки данной статьи, то нам ничто не мешает погрузиться в глубины зайца и посмотреть как он устроен на табличном уровне.
PS: и не спрашивайте почему зайца.

Итак — исходная задача состоит в определении неких вхождений в некие рубрики, но давайте уточним ТЗ:

• Есть «шейринг с геолокацией» — примерно 3 миллиона точек
• Которые как-то «лежат» в 300 тысячах кварталов, районов и других административных делений, вложенных друг в друга.
• В любой момент времени требуется найти все обьекты, входящие хоть в район города, хоть в континент.

В общем задача состоит в обработке неких элементов, которые привязаны к некому дереву иеархий.

Начнем с простого — а реализации рубрик, каталогов или просто деревьев. Вариантов реализации не много, точнее нормализованный вариант реализации вообще вроде один:

{
 id: entity_id,
 parent: parentId
}

Есть некий элемент, и у него есть один родитель (если два — уже не деревья). Это все работает хорошо до тех пор, пока нам не надо производить некоторые операции над ветками.

• 1. Найти все подрубрики == найти все районы города
• 2. Найти все элементы в подрубриках == найти все обьекты города
• 3. Найти всех своих родителей наверх == понять в какой стране город
• 4. Что-то посчитать, агрегиговать, сломать или починить.

Эти проблемы актуальны и для рубрик на сайте, и файлов на диске, и вообще чисто теоритических диванных изысканий.
И есть несколько стандартных решений этой проблемы:

• 1. Adjacent Set (AL) — en.wikipedia.org/wiki/Adjacency_list ^[3]
  Таблица вида child,parent[,level], где просто указаны все родители нужного ребенка. Сколько родителей — сколько и записей.
  Это самый простой и самый «нормализованный» вариант. Абсолютно удобен, но может подавать на «выход» очень большие «облака» и генерировать километровые «кишки» таблиц. Из-за большого размера и размазанности работает, в общем, не моментально.
• 2. Materialized Path (MP)
  Это когда мы берем всех своих родителей и «материализуем» в одну строчку через запятую. А потом можем использовать оператор LIKE для поиска нужного.
  В принципе нормальный вариант, любимый студентами. Особенно хорош если перейти от основания 10, в том числе обычной строки, на чуть более бинарный (base32,64,92 или 254).
  Минус только один — не технологично, да и индексы в произвольном месте строки работают не очень красиво.
  PS: есть и технологичные решения — так называемые матричные деревья, когда ID узла это матрицы, а положения элементов — детерминанты их перемножения. С учетом некоммутативности умножения ключик получается реальным. Если после прочтения этого абзаца вы подумали про Жесть — так оно и есть.
• 3. Nested set (NS).
  Nested set table — это такая чтука про которую многие слышали, но мало кто знает как она работает и почему. Для многих NS — это такой плагинчик или библиотечка, которой можно пользоваться. А разбираться — влом.

Но именно этим и будем разбираться, потому что Nested set table (http://en.wikipedia.org/wiki/Nested_set_model ^[4]) это:

• 1. Одна из материализаций skip-list ^[5]
• 2. Одна из материализаций B-tree ^[6]
• 3. В прямом переводе просто — вложенные интервалы
• 4. Они совсем не страшные.
• 5. Обеспечивают линейное хранение.
• 6. И они именно то, что нам нужно

Отличие от «обычных» child-parent схем заключается в том, что некий parent содержит два неких «числа» — начало своего интервала, и конец. А все его дети содержат «числа» где-то между этими значениями. Визуализировать можно по разному, в Википедии можно найти несколько страшных вариантов деревьев. Но если взять обычное дерево, разделить по уровням и нарисовать на бумажке — получатся списки с пропусками.

А взмахом палочки эта картинки превращается в B-tree. Потому что разницы, идеалогически, нет.
В неком роде nested-set адресацию можно считать неким «space filling curve», некой кривой которая неразрывно рекурсивно пересекает все элементы некого дерева в порядке обхода.
Если начальный интервал задать в 0-1, потом разделить в точке 1/2, а потом 1/4,2/4,3/4,8/16,50/128… то получится, что любой студент, который на первом курсе пытался вкурить в пределы и сходящиейся последовательности — курил мою траву. Хотя на самом деле это называется Дерево Штерна — Броко ^[7]

Для многих cамое сложное в NS это их построение. Многих людей сразу пугают эти left/right/st и другие страшные слова и картинки употребляемые на различных сайтиках.
На самом деле NS это просто интервалы, просто утверждение что детей можно найти где-то в коридоре значений родителей. Это не деревья, это числа, которые хранятся в плоских таблицах базы данных. Непрерывный ряд на числовой кривой.

В итоге строить NS можно проще:
Вариант 1:

В базе данных считаем количество своих детей (COUNT(id)), а потом количество этого количества (count(count)). Таким образом «методом пузырька» полна емкость поднимается наверх. Остается только найти своего соседа, и как-то взять у него офсет — полную емкость его соседов левее.
Это 4 SQL запроса, некоторые из которых надо выполнить пару раз.

Вариант 2:

Преобразуем наше дерево в matpath, сортируем через strnatsort и подвешиваем некий auto_incriment на этот порядок. Числовая кривая готова. Остается только найти своего соседа (например справа), и использовать его «число» как правую границу.

В обоих случаях вставка и удаление — O(n), а иногда и O(1).

NS это просто два числа, интервал между «булками» которого спрятано все самое вкусное. В общем случае кривая не обязана состоять из целых чисел, более того отлично ложится на дроби. Берем уже упомянутого Штерна — Броко и получаем кривую Коха.

Надеюсь вы дочитали до этого момента, поняли что такое Вложенные Интервалы, осталось понять чем же они так хороши.
Представим что у вас есть список всех отелей Hotellook(Aviasales). Представим что у вас есть привязка этих отелей в странам-регионам-городам-районам. Задача — найти все отели в Орехово-Борисово Южное (узкая выборка), все 5-ти звездочные отели Турции (большая выборка), и все отели в квадрате 100 метров от вас.

Решение ситуации 1:

WHERE hotels_to_regions_ns.id between ns.left and ns.right

Решение ситуации 2:

WHERE hotels_to_regions_ns.id between ns.left and ns.right

В том и секрет — никакой разницы нет. И в обоих случаях работает быстро.

Решение ситуации 3 подразумевает некий координатный поиск. Но в обычных БД это очень сложная и дорогая операция — поиск по двойному ключу, или же по 2D(spatial) ключу — просто сложно, дорого и генерируется много чтений из разных мест диска. Ну просто потому что порядок хранения данных на диске 1D.
Но решение ситуации остается почти что тем же самым:

WHERE hotels_to_mortoncode.z between ns.zleft and ns.zright

Где мы используем Morton, он же Z-curve code ^[8] для конвертации 2D координат в 1D кривую (об этом пару раз писалось ^[9] на хабре), а потом сохраняем ее в кодах Грея(два бита на одно деление) и можем делать быстрые выборки по пирамиде (привет ObjectManager ^[10]).
Для многих не совсем понятно почему выборки быстрые — следует наверное пояснить. Morton коды, кроме того что являются «адресацией по quadtree» обладают еще одним свойством — коды для обьектов, которые рядом, будут рядом.

maps multidimensional data to one dimension while preserving locality of the data points

Z — не самое удачное решение, но отлично подходит для быстрых выборок групп(тайлов) обьектов. Z-коды «держат» локальность данных, в том числе для обьектов одной ноды коды будут вообще одинаковые, или их вариативность будут зажата между left и right значениями элемента NS.
Плюс — NS, как я уже говорил — некая материализация skip-листов, числовой кривой или даже B-деревьев. Технически разницы нет. Так что, когда вы храните данные в NS вы храните их в B-tree… то… подождите…

В общем Z ^[8], Hilbert ^[11], GeoHash(Z коды в base64) и компания — это те же яNestedSet, вид с боку.
Эти коды часто используются в различных GIS системах, в том числе Bing называется их quad-code ^[12] и использует для адресации тайлов, и все этого без проблем работает и в 3D и в 4D пространстве.
Сводя задачки в простую числовую кривую.
И в стандартный NestedSet.
Эффект всегда один — все начинает работать.

Вот и сказочке конец, а кто слушал — молодец.

PS: С вами были kashey и esosedi, которые уже почти 7 лет используют NS и Z коды для выборки обьектов на карту. В число которых попали и отели HotelLook (это которые special.habrahabr.ru/aviasales/ ^[13]).
PPS: Вступайте в ряды Фурье — сходимость! Равенство! Гильбертово пространство!
PPPS: И не забывайте про мудрость веков!

Автор: kashey

Источник ^[14]