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

    Привет ребят, давайте для начала проверим вашу память. Итак:
    «На море на океане есть остров, на том острове дуб стоит, под дубом сундук зарыт, в сундуке — заяц, в зайце — утка, в утке — яйцо» в яйце игла — смерть Кощея!

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


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

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

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

    Есть некий элемент, и у него есть один родитель (если два — уже не деревья). Это все работает хорошо до тех пор, пока нам не надо производить некоторые операции над ветками.
    • 1. Найти все подрубрики == найти все районы города
    • 2. Найти все элементы в подрубриках == найти все обьекты города
    • 3. Найти всех своих родителей наверх == понять в какой стране город
    • 4. Что-то посчитать, агрегиговать, сломать или починить.


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

    • 1. Adjacent Set (AL) — en.wikipedia.org/wiki/Adjacency_list
      Таблица вида 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) это:


    • 1. Одна из материализаций skip-list
    • 2. Одна из материализаций B-tree
    • 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… то получится, что любой студент, который на первом курсе пытался вкурить в пределы и сходящиейся последовательности — курил мою траву. Хотя на самом деле это называется Дерево Штерна — Броко


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

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

    Ну ладно, не 4
    CREATE TABLE IF NOT EXISTS `flatindex` (`rid` int(11) NOT NULL,`lvl` tinyint(4) NOT NULL,`prev` int(11) NOT NULL,`parent` int(11) NOT NULL,`innerCnt` int(11) NOT NULL,`fullCnt` int(11) NOT NULL,`cumsum` int(11) NOT NULL,`start` int(11) NOT NULL,`right_key` int(11) NOT NULL,PRIMARY KEY (`rid`),KEY `parent` (`parent`),KEY `start` (`start`))
    
    --INSERT INTO flatindex (rid,lvl) SELECT id,level FROM regions
    
    -- "Первая" операция
    -- innerCnt - количество подрубрик.
    -- В fullCnt "пузырьком" всплывает количество всех подрубрик
    --repeat until affected_rows=0
    UPDATE flatindex as fl1,(SELECT fl1.rid,sum(fl2.fullCnt)+fl1.innerCnt+1 as cnt FROM flatindex as fl1 INNER JOIN flatindex as fl2 ON fl2.parent=fl1.rid GROUP BY fl1.rid) as gr SET fl1.fullCnt=gr.cnt WHERE fl1.rid=gr.rid
    
    
    -- "Вторая операция"
    -- в cumsum записывается количество элементов "левее" в текущей рубрике
    UPDATE flatindex as fl1,
    (SELECT SUM(fl2.fullCnt)+COUNT(*) +1 as fc,fl1.rid as rid
    from flatindex as fl1
    LEFT JOIN flatindex as fl2 ON fl2.parent=fl1.parent
    WHERE fl2.rid<fl1.rid GROUP BY fl1.rid)as gr
    SET fl1.cumsum=gr.fc WHERE gr.rid=fl1.rid
    
    -- "Третья" операция
    -- заполняем первые позиции
    UPDATE flatindex SET start=cumsum+1 WHERE parent=0;
    
    -- repeat until affected_rows=0
    UPDATE flatindex as fl,(SELECT start,rid FROM flatindex)as gr SET fl.start=gr.start+1 WHERE fl.prev=0 and fl.parent=gr.rid;
    UPDATE flatindex as fl,(SELECT start,parent FROM flatindex WHERE prev=0)as gr SET fl.start=cumsum+gr.start WHERE prev!=0 and fl.parent=gr.parent;
    
    -- "Четвертая"
    -- установка правых значений
    UPDATE flatindex SET right_key = start+fullCnt+1;
    



    Вариант 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 для конвертации 2D координат в 1D кривую (об этом пару раз писалось на хабре), а потом сохраняем ее в кодах Грея(два бита на одно деление) и можем делать быстрые выборки по пирамиде (привет ObjectManager).
    Для многих не совсем понятно почему выборки быстрые — следует наверное пояснить. 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, Hilbert, GeoHash(Z коды в base64) и компания — это те же яNestedSet, вид с боку.
    Эти коды часто используются в различных GIS системах, в том числе Bing называется их quad-code и использует для адресации тайлов, и все этого без проблем работает и в 3D и в 4D пространстве.
    Сводя задачки в простую числовую кривую.
    И в стандартный NestedSet.

    Эффект всегда один — все начинает работать.

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

    PS: С вами были kashey и esosedi, которые уже почти 7 лет используют NS и Z коды для выборки обьектов на карту. В число которых попали и отели HotelLook (это которые special.habrahabr.ru/aviasales).
    PPS: Вступайте в ряды Фурье — сходимость! Равенство! Гильбертово пространство!
    PPPS: И не забывайте про мудрость веков!
    • +14
    • 9,4k
    • 8
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 8
      • 0
        Комментарии про Кащея всегда побеждают… Вспомнился такой перл про визуализацию бизнес-данных:

        «Никого уже не удивишь технологией drill-down, изобретателем которой по праву можно считать знаменитого русского просветителя и общественного деятеля Кощея Бессмертного (смерть на конце иголки, иголка в яйце, яйцо в утке, утка в зайце, заяц в сундуке, бла-бла)» за авторством eugenebartosh

        Статья, кстати, гуд)
      • 0
        а потом сохраняем ее в кодах Грея(два бита на одно деление)

        А это как и зачем?
        • 0
          Посмотрите на картинку в конце статьи — это деление ноды на 4 части.
          Выбор ноды по Х — это 0 и 1, выбор ноды по Y — это 0 и 1.
          Итого ноды идут как 00-01-10-11, или 0-1-2-3. Это одновременно и Z код, и 2-битный код Грея.
          Есть варианты «делений» сразу через «несколько уровней», когда на выбор идет сразу через 8-16 нод. Например монга любит сразу на пару уровней Hilber вешать, так как его считать сложно.
          И это уже не Грей будет.
          • 0
            А разве код Грея это не 0-1-3-2? Собственно, вопрос в том, есть ли у кривой Пеано преимущество перед Z-кривой, или там только проблемы с выбором сегментов, пересекающих анализируемую окрестность точки.
            • 0
              Это уже вопрос из момента сохранения локальности данных и области использования, точнее нужных областей выборки.
              Пеано — это вообще «родоначальник» space filling curve, но эта трансформация обладает самым большим «расстоянием».
              Примерно так
              Два значения в Hilbert находятся очень близко друг от друга в 2д эвклидовом пространстве(те исходном)
              Два значения в Morton находятся близко — из-за перекладины в Z вся статистика насмарку.
              Два значения в Пеано находятся не далеко.

              На самом деле в (русской) википедии написано что Hilbert это тоже пеано, но в общем — en.wikipedia.org/wiki/Space-filling_curve

              У Z есть только одно, но очень крутое, преимущество — полная симметрия и очень простое вычисление как «туда» так и «обратно».
        • 0
          Самый большой вопрос: всегда ли рядом находящиеся точки получают близкие коды квадратиков?
          Посмотрите, например, на Пиренеи — часть находится в квадратике 031, а часть в 122, что как бы очень далеко по индексу. Нужен как-то более умный обход квадратов, чем просто Z-кривая.
          • 0
            Любая кривая рекурсивного разбиения будет иметь такую проблему. От конкретной нумерации разбиения квадродерева зависит только некое численное выражение «дальности».
            Одна половина Лондона, от второй всегда будет «далеко», так как по этому место проходит первый уровень разбиния.
            Но кроме Z(и вообще quad) кодов есть еще, например, кривая Серпинского, в основе которой лежит разбиение треугольниками. В ней «далеко» будет в других местах.
            Еще кодирование разбиения в кодах грея — в численном эквиваленте два соседних значениях могут быть далеко, но различаться при этом будут всего на 1 бит(2 по диагонали). И даже нормальная метрика под это дело есть — расстояние Хэминга.
            Простейшие коды 2Д Грея работают просто — переводим X,Y в gray (x ^ x>>1), после чего делаем bitInterlaving и получаем Z код, основанный на кодах грея…

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.