Full Hierarchy — иерархические структуры в базах данных

    Здравствуйте. В этой статье я хотел бы написать про один очень интересный способ хранения иерархических структур в базах данных, не относящийся при этом к общепринятым и общеизвестным трём (Adjacency List, Nested Set, Materialized Path). Я не встречал в интернете упоминания о нём, о чём очень удивлен, ведь, по моему мнению, — это лучший и единственный способ хранить иерархические структуры. При разработке console-like форума я воспользовался именно этим способом, о чём ни на грамм не жалею. Это авторская статья и ни одно предложение не было вставлено метотодом копипаста.

    Вполне возможно, что этот способ известен и называется он иначе. Если так — с удовольствием узнаю, как она называется на самом деле.

    Имхо, этот способ больше всего похож на Materialized Path, с незначительным оттенком Adjacency List. По сравнению с Adjacency List он слегка денормализует базу данных, но с теми преимуществами, что он даёт — это не играет значительной роли.

    Суть способа


    Для каждой иерархической структуры мы создаем две таблицы — таблица с данными и таблица с иерархией. В таблице с данными мы храним то, что нам нужно, единственная ячейка, которая нас здесь интересует — это PRIMARY (`ID`)
    В таблице иерархии мы храним список всех элементов и их родителей с уровнем к каждому родителю. То есть, если у элемента есть 5 родителей — мы храним 5 записей формата (ElemID, ParentID, Level). Таким образом, для описания самого глубокого элемента понадобится количество элементов, равное уровню вложенности.

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

    Примеры


    Итак, какой инструментарий для примера я использую:
    • php 5.3. Важно, чтобы объекты передавались по ссылке, потому 4 версию рекомендую не использовать, или значительно реформировать код
    • mysql. Используются базовые возможности MySQL, потому версия не так важна. Единственное, что, если вы выберете InnoDB — так, думаю, будет лучше
    Изначально я выложу код, который далее в статье объясню:
    Я использую сообственноручно написанный класс для работы с БД (LGPL): pastebin.com/f2642074f. Именно в нём меняем параметры подключения.

    Теперь по поводу самого кода:
    Определяем, какой элемент мы будем хранить в базе. Это объект класс Elem c свойствами $id, $data, $children, $parent: pastebin.com/f78f943d8

    Готовые функции, которыми работаем с базой, и далее они будут описаны: pastebin.com/f314afb10

    Также создадим в нашей базе данных две таблицы:
    CREATE TABLE `Elements` (
     `ID` int(11) NOT NULL AUTO_INCREMENT,
     `Data` varchar(64) NOT NULL,
     PRIMARY KEY (`ID`)
    ) ENGINE=MyISAM DEFAULT CHARSET=utf8;

    CREATE TABLE `ElementsHierarchy` (
     `ElemID` int(11) NOT NULL,
     `ParentID` int(11) DEFAULT NULL,
     `Level` int(11) NOT NULL,
     KEY `ElemID` (`ElemID`),
     KEY `ParentID` (`ParentID`),
     KEY `Level` (`Level`)
    ) ENGINE=MyISAM DEFAULT CHARSET=utf8;


    * This source code was highlighted with Source Code Highlighter.

    Объяснение примеров


    Сразу же после подключения базовых файлов для того, чтобы получить тестовые данные вызовем функцию generateData, где 4 — количество элементов на уровень, 3 — глубина вложенности.

    $tree = generateData(4, 3, null);

    Справа вы можете видеть один из 4 элементов, которые теперь находятся у нас в массиве $tree
    Если сделать print_r ($tree), то можно увидеть, что у нас массив из четырех деревьев по (1 + 4 + 4 * 4 + 4 * 4 * 4) = 85 элементов, то есть 340 элементов вместе. В качестве $elem->data будет его уровень. Приблизительно так:
    #.1
    #.1.1
    #.1.1.1
    #.1.1.2
    #.1.2
    #.2
    #.2.1
    #.2.2

    Добавляем данные в таблицу

    Для того, чтобы их вставить я написал функцию insertTreeRecursive. На каждый элемент нам понадобится два-три запроса. Один — чтобы вставить данные в таблицу `Elements`, один — чтобы взять данные с таблицы `ElementsHierarchy` о родителях и один — чтобы вставить в таблицу `ElementsHierarchy` данные о родителях. Теперь подробнее на примере функции

    Думаю, до этого момента ничего тяжёлого:
    $elem->setId(Db::execute($query));

    Мы вставляем в таблицу `Elements` строку, получаем last_insert_id и присваиваем его текущему элементу. Допустим, ID вставленной записи получилось 37

    Если у данного элемента нету родителей, то в базу идет запрос а-ля:
    INSERT INTO `ElementsHierarchy`(`ElemID`,`ParentID`,`Level`) VALUES ('ID', NULL, 1)

    То есть видно, что элемент на первом уровне от отсутствующего элемента (NULL), то есть родителей не имеет.

    Но вот если у элемента есть родитель, то мы получаем список всех родителей родителя (допустим, ID ближайшего родителя — 15). Получится что-то типа такого:
    |   ElemID   |  ParentID  |  Level  |
    |     15     |    NULL    |    4    |
    |     15     |      1     |    3    |
    |     15     |      5     |    2    |
    |     15     |     10     |    1    |
    Мы заменяем у каждой строки ElemID на ID текущего элемента, увеличиваем Level на единицу и дописываем в конец массива еще родите ID=15 и Level = 1.
    Получилось у нас следующее:
    |   ElemID   |  ParentID  |  Level  |
    |     37     |    NULL    |    5    |
    |     37     |      1     |    4    |
    |     37     |      5     |    3    |
    |     37     |     10     |    2    |
    |     37     |     15     |    1    |
    Вот такую структуру и добавляем в конец таблицы `ElementsHierarchy`. Для нашего $tree, размером в 430 элементов, получилось 1252 строки в таблице иерархии. Чем меньше средний уровень вложенности — чем меньше будет таблица и наоборот. Обратите внимание, что, несмотря на глубину вложенности для вставки одного элемента достаточно 3 простых запроса.

    Получаем данные с таблицы

    Воспользуемся функцией getRowsByParent для получения данных с таблицы:
    $tree = getRowsByParent(2);
    print_r($tree);

    Мы видим, что у нас вывелись элемент #1.1 и все дерево в подмножестве #1.1.*
    Но `ParentID` у нас не ближайшего родителя, а того родителя, по которому мы осуществляли поиск. Потому мы немножко усовершенствуем наш запрос и а также сделаем цикл, который оформит результаты запроса в объект. Вызываем
    $tree = getTreeByParent(2);
    print_r($tree);
    и получаем как раз то, что нам нужно! Одним SELECT'ом!

    Хорошо, но давайте посмотрим дальше. А как же производить UPDATE таблиц? Давайте в качестве теста добавим в таблицу `Elements` еще одно поле:
    ALTER TABLE `Elements` ADD `Marked` BOOL NOT NULL


    И промаркируем все ячейки, которые находятся в глубине дерева 2:
    getTreeByParent(2); Смотрим в базу и видим, что всё получилось. Удаление производится точно так же.

    Сравнение данного способа и Materialized Path


    По предложению хабрасообщества был проведен тест для сравнения скорости выборки из базы данного метода и метода Materialized Path. И у меня есть очень впечатляющие результаты. Я сгенерировал десять 11110 деревьев по 11111 елементов, размером 5*10, то есть 111110 елементов в базе и сделал по ним тесты: Я генерировал 20 случайных ID и искал полное дерево под ними в базе данных. В результате, во всех случаях, Full Hierarchy показывает себя в 5-8 раз лучше, чем Materialized Path (вы можете сами проверить, все исходники тестов — выложены):
    pastebin.com/f65b2fb7d — функции, которые использовались во время тестирования.
    pastebin.com/f793f7c74 — само тестирование и его результат.
    Структура базы `ElementsMP`:
    CREATE TABLE `ElementsMP` (
     `ID` int(11) NOT NULL AUTO_INCREMENT,
     `Data` varchar(64) NOT NULL,
     `Path` varchar(1000) CHARACTER SET latin1 COLLATE latin1_bin DEFAULT NULL,
     PRIMARY KEY (`ID`),
     KEY `Path` (`Path`)
    ) ENGINE=MyISAM DEFAULT CHARSET=utf8;

    * This source code was highlighted with Source Code Highlighter.

    Более того, база не позволяет сделать поле `Path` длиннее 1000 символов (#1071 — Specified key was too long; max key length is 1000 bytes), что значит, что, если у нас средняя длина ID будет 4 символов мы не сможем делать деревья глубже 1000/(4+1), то есть самое глубокое возможное дерево в таком случае — 200 элементов. и 166 при средней длине ключа 5 цифр (если на сайте более 50000 комментариев в среднем)

    Итог


    Возможно, код выше имеет какие-то свои недостатки, но, я уверен, что все недостатки легко исправятся со временем и опытом. Если способ понравится многим, то, думаю, можно будет собраться и написать библиотеку для более удобной работы с ним.

    Благодарности

    Спасибо DkZ из конфы FreeCR, что нарисовал лого для темы.
    Спасибо Kostyan'у, что натолкнул меня на эту идею.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 108

      +1
      Гм, вариация на тему materialized path. Просто информацию о пути вы разложили на несколько записей.
        0
        согласен, я так и написал, что больше всего похоже на materialized path. Но, в отличии от materialized path база работает с числовыми индексами. Плюс, materialized path или ограничен длиной, или поле text, что тоже есть минусом. Несмотря на то, что способ похож на materialized path, я бы не назвал его вариаций.
        Ведь materialized path тоже своего рода вариация Adjacency List. ;)
          0
          Не совсем так.
          Вопрос не в том КАК мы храним (запись, текстовое поле или что-то другое), вопрос в том ЧТО мы храним. А мы, по сути, храним полный путь к ноде.

          В AL хранятся только две соседних ноды.
            0
            Этот способ требует другого подхода в программировании, этот способ имеет другие недостатки и другие преимущества по сравнению с MP. Единственное, что у этого способа похожи идеи.
            ЧТО мы храним

            Храним мы иерархическую структуру. Любым способом. Разница как раз к том, как храним.

            Не вижу смысла продолжать этот разговор, ведь это больше вопрос философии, чем программирования.
              +5
              Мда, грустно :(

              Храним-то мы ИС. Но вопрос в том ЧТО мы храним об ИС.

              А храним мы путь, или соседние элементы.

              Простите, но я не увидел «другого» подхода. Просто на выходе из таблицы я получаю не строку с путем, которую мне надо распарсить. А массив элементов пути.
            0
            Кстати, а какие сложности с хранением MP в текстовых полях?
            размер от 2^16 до 2^32
            Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.

            Выборка поддерева, кстати, тоже делается 1м запросом.
              0
              А вы это поле делаете индексом, или нет? Как у вас в таблице на 100000 строк происходит поиск поддерева?

              Как вы думаете, почему MP не стал таким популярным, как AL и NS? Я сам думал именно о MP, пока не открыл для себя этот способ.
                0
                Конечно делается индексом. Вы же собираетесь по нему искать.

                Записи у вас плодятся неимоверно. Для небольшого форума это может и не критично… но дальше будет хуже

                Общее число записей считается по формуле (n+1)*n/2
                Каждый последующий элемент будет занимать в (n^2 + 3*n +2) / (n^2 + n) раз больше.

                Для n=100 мы имеем 5050 записей. Я тут видел тред на 900 комментариев, это у нас уже 405450 записей.

                В общем можно погонять на вопрос производительности. Но не думаю, что ваш способ быстрее.
                  0
                  Формула недостаточно корретна по той причине, что дерево не растёт вглубь.
                  на 340 объектов у меня получилось 1252 объекта в таблице иерархии.

                  если бы дерево расло вглубь так, как указано в вашей формуле, то в MP в каждом пути приходилось бы держать и работать с достаточно длинными строками, и я сомневаюсь, что MP показал бы себя в этом лучше, чем FH
                    +1
                    А вы не сомневайтесь, вы замерьте
                      +3
                      Основная проблема МП это full-text search в базе.

                      Если дерево не растет вглубь (ввысь) :) то это трава, а не дерево :)

                      У вас, похоже, неглубокое дерево. И в вашем случае проблем с поиском не будет даже по текстовым полям.
                      Они будут расти именно с ростом вложености.

                      Но тут (в случае стандартного решения) у нас есть обходной маневр. Часть с поиском мы можем возложить не на БД, а на Sphinx например.
                      Он нам вернет список ID, которые мы уже и используем в запросе к БД.

                      А в остальном, солидарен с sse. Проведите нагрузочное тестирование разных деревьев способом МП и вашим. И добавьте к топику. Будет более чем интересно :)
                        +1
                        добавил, читайте)
                          +2
                          >> Основная проблема МП это full-text search
                          зачем для строки в MP фуллтекст?? `path` LIKE 'bla%'
                          и обычный строковый индекс.
                    0
                    Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.

                    На счёт этого там тоже, кстати сказано.
                      0
                      Хотя хватит и банального VARCHAR на пару-тройку тысяч байт.

                      Более того, база не позволяет сделать поле `Path` длиннее 1000 символов


                      Я немного недопонял. Может, я не ту документацию читаю? Какие тысячи байт в VARCHAR?
                        0
                        Вы действительно не ту документацию читали

                        dev.mysql.com/doc/refman/5.4/en/storage-engines.html
                          0
                          Ах вот, в чем дело. Благодарю.
                            –5
                            ЖЖЕШЬ
                            0
                            фу, промахнулся ссылкой. Вот :)

                            dev.mysql.com/doc/refman/5.4/en/storage-requirements.html
                              0
                              да я сразу там нашел, что мои сведения устарели :)
                                –1
                                а… понял
                  0
                  В materialized path вообще insert делается 1им запросом.
                  Преимуществ не увидел — они как-то в статье прописаны?
                    +2
                    нууу. для меня преимущества — очевидны.
                    при выборке работаем с числовым индексом, никак не ограничены в уровне вложенности.
                    поиск определённого узла будет быстрее: WHERE `ParentID` = 1453 быстрее, чем WHERE `Path` LIKE '%.1453.%' и т.п.
                      +1
                      Спорное утверждение. Скорость поиска зависит не только от предиката поиска, но еще и от того, сколько строк лежит в таблице. Из статьи совершенно не следует, что выгода от замены предиката на менее трудоемкий превысит потери на поиск в таблице значительно большего размера.

                      У вас есть конкретные цифры — например, для среднего сбалансированного дерева в 500 элементов со средним числом дочерних item в 4?
                        0
                        Должно получиться примерно 500 * 10 записей
                          +1
                          теперь есть, читайте)
                            –1
                            Почитал.
                            Странные у вас тесты, и вот почему:
                            — в жизни вам часто надо извлекать просто рандомный узел?
                            — вы меряете производительность только операции select. Как насчет insert/update?

                            Синтетические тесты мало что доказывают, вы бы на сценариях real world потестировали.
                              0
                              в жизни вам часто надо извлекать просто рандомный узел?
                              Если бы я извлекал не рендомный узел, а какой-то определенный, то меня могли бы обвинить в фальсификации и в том, что я специально выбрал такие числа, на которых более выгоден мой метод. В моих же тестах явно видно — в среднем FH намного быстрее, чем MP

                              вы меряете производительность только операции select. Как насчет insert/update?
                              Хорошо. Чуть позже — гляну

                              Синтетические тесты мало что доказывают, вы бы на сценариях real world потестировали.
                              Консольный форум, как уже говорилось, использует именно эту систему. У меня там не подключено кеширование и акселераторы, я хостюсь на дешёвом хостинге за 5 баксов. Генерация страницы занимает чуть меньше, чем 0.02 секунды. При этом форум с лёгкостью выдержал ХабраЭффект и некоторое замедление в работе было вызвано не движком, а недостаточно широким каналом. Движок же отработал с лёгкостью.

                              Более того, товарищ, который навёл меня на эту мысль (Java-прогер с многолетним стажем) утверждает, что в HighLoad'е, с которым он работал — используется именно этот способ и он очень хорошо себя показывает.
                                –1
                                да нормальный тест инсерт/update не нужно вообще мерить, ведь это редкие нарушающие кеш операции
                            +1
                            Кгм. А вот такой вопрос зачем у вас
                            LIKE '%.1453.%'?

                            Если мы получали этот самый 1453й объект. То у нас должна быть информация о пути к нему.
                            Например, '1.17.234'
                            И тогда наш LIKE превратится в что-то вида

                            LIKE '1.17.234.1453.%';
                            0
                            а получать список родителей можно вообще без запросов XD
                          • UFO just landed and posted this here
                              +1
                              Cудя по тестам — мне надо 0,3 секунды без кеширования для получения из базы дерева размером 11 тысяч узлов. Сколько с кешированием — прикиньте сами. Вот вам и преимущество этого метода.
                              +3
                              Всем: добавлен пункт «Сравнение данного способа и Materialized Path»
                                +1
                                интересный подход! использовали одно время что-то похожее, но число записей переползло за
                                10 000 000, наш велосипед стал ползать и пересели на HBase =)

                                используем систему в биллинге одного оператора моб. связи
                                  0
                                  А почему именно эта СУБД? А не, к примеру, CouchDb?
                                  +5
                                  То, что вы храните в базе, называется транзитивным замыканием графа (дерева, в вашем случае): www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml
                                  Тема не новая, в интернете информации очень много.
                                    0
                                    Спасибо :)
                                    +1
                                    Собственно, всё гениальное просто. При необходимости сделал бы скорей всего также.

                                    А не поможет ли кто линкой на статью на эту тему? А то как то грустно, что термины Adjacency List, Nested Set, Materialized Path почти полностью не о чём. Английский тоже подходит.
                                      +1
                                      AL, NS, MP:
                                      habrahabr.ru/blogs/development/46659/
                                      phpclub.ru/faq/Tree/
                                      Про применение FH в php лично я нигде не видел. Ну и почитайте ссылку, что дал tegger деревом выше.
                                        0
                                        Да мне скорее интересна сухая теория, даже скорее с уклоном в математику, но тут главное не перегнуть.
                                      +2
                                      Более того, база не позволяет сделать поле `Path` длиннее 1000 символов (#1071 — Specified key was too long; max key length is 1000 bytes),

                                      заблуждаетесь
                                      `field` VARCHAR(10000) COLLATE utf8_general_ci DEFAULT NULL,

                                      а про 1000 он говорит совершенно верно — нельзя делать КЛЮЧИ длиннее 1000байт (для myisam)

                                        0
                                        то есть, вы предлагаете сделать это поле не индексом?
                                          +1
                                          то есть я предлагаю:
                                          1. исправить неточность в статье, которая может смутить неопытных разработчиков
                                          2. делать индексы разумных размеров. индекса в 1000 байт хватит за глаза для любой древовидной структуры, какую я только могу придумать. ну или помогите придумать структуру, для хранения пути которой не хватит 1000 байт. даже если придумаете — ну будет использован префикс в 1000. ну отсечётся 99% не попадающих под условие записей. ну будет сканирование по оставшимся. что страшного?
                                          0
                                          Мне больше жульничество с лайком понравилось.
                                          Искать без левого процента совсем несложно.
                                          Но ведь даст такие неудобные цифры! :)
                                          +3
                                          а как ваш метод поведет себя при перестановке узлов, удалении узла и вставке? что то сомневаюсь, что в этом он будет быстрее
                                            0
                                            Удаление ветки — операция вообще тривиальная:
                                            DELETE FROM `Elements`
                                            INNER JOIN `ElementsHierarchy` as `Hier`
                                              ON `Hier`.`ElemID` = `Elements`.`ID`
                                            WHERE `Hier`.`ParentID` = {ID} OR `Elements`.`ID` = {ID}


                                            * This source code was highlighted with Source Code Highlighter.
                                            Вставка в статье описана — два-три запроса. Перемещение тоже могу описать. То получится где-то два-три запроса на всю ветку. Но работа будет происходить только над элементами ветки и не придется менять часть структуры, которая не затрагивается, как происходит в NestedSets.

                                            Кстати. Не знаю, хорошо ли это, но при изменении иерархии таблица с данными будет совершенно свободна, то есть затрагиваться не будет.
                                              0
                                              А если это промежуточный узел, кто пересчитает level и пересадит детей родителю?
                                            0
                                            В Drupal 6 для хранения меню используется вариант Materialized Path, но с ограничением по уровню вложенности. И путь хранится не в одном текстовом поле, а целыми: p1, p2, ..., p9. Еще поле depth.

                                            Ключ сделан по (`menu_name`,`p1`,`p2`,`p3`,`p4`,`p5`,`p6`,`p7`,`p8`,`p9`).

                                            В два селекта вроде можно уложиться достаточно шустрых для получения всех пунктов подменю (сначала определяем путь к нужном пункту меню, а потом селект для выборки потомков).
                                              +5
                                              > Я не встречал в интернете упоминания о нём, о чём очень удивлен

                                              Вы, видимо, совсем не искали.

                                              Ибо, способ чуть моложе вселенной, и применяется часто.
                                              Так же часто и подробно описан.

                                              gsbelarus.com/gs/modules.php?name=News&file=article&sid=314
                                              www.delphikingdom.com/asp/viewitem.asp?catalogid=1263
                                              www.delphikingdom.com/asp/answer.asp?IDAnswer=29168
                                                0
                                                Лет 5 назад, когда нужно было сделать дерево, я придумал практически такую же схему (с небольшими, но не принципиальными отличиями). На мой взгляд, она намного проще и приятнее, чем тот же nested tree.
                                                  +1
                                                  ага, особенно когда нужно ещё и порядок хранить…
                                                  0
                                                  Метод, как выше уже сказано, не то чтобы нов… В общем, он удобен для не очень больших read-only деревьев. Но как только вы захотите менять дерево, вы сразу почувствуете ограничения метода.
                                                    0
                                                    Мне на практике нужно примитивное, неглубокое дерево, без 11000 предков и т.п… Уровней 3-4 думаю будет более чем достачно для вменяемых ветвей комментариев. В данном случае чем «деревянней», тем лучше. А все статьи почему то описывают какие то безумства с данными, имеющими весьма посредственное отношение к реалиям(
                                                    Ну это я так, погундел немножко.
                                                      0
                                                      у всех свои «реалии»…
                                                      0
                                                      А как будут обстоять дела с поиском по не ключевым полям? Да еще и с поискам по всем поддеревьям по этим же не ключевым полям. Думаю, что здесь и индекс-то особо не поможет.
                                                        0
                                                        Ммм. в чем вопрос-то? :)

                                                        Поиск не по ключевым полям всегда будет использовать filesort.
                                                        Это не имеет отношения к дереву :)
                                                          0
                                                          Ну наверно вопрос в том как будут искаться ветки, в которых встречается слово «мама».
                                                            0
                                                            А как будут искаться «неветки» с этим словом? :)

                                                            Повторюсь. Независимо от того дерево у нас или обычная таблица поиск по «неключевым» полям будет одинаков :)

                                                            SELECT * FROM a WHERE b LIKE '%мама%'

                                                            Или я просто не понимаю, что вы хотите :)
                                                        0
                                                        А вот в Sql Server есть родная поддержка иерархий.
                                                          0
                                                          придумают всё что угодно, лишь бы не CONNECT BY…
                                                            0
                                                            а в MySQL есть CONNECT BY?
                                                              0
                                                              Пордон, промазал, это ответ на SQL SERVER иерархии
                                                              В Oracle есть. И все пытаются сделать тоже самое, но не копировать, а извратиться как-то.
                                                          • UFO just landed and posted this here
                                                              0
                                                              точно таким же, каким добился бы в html )
                                                              &img src=«Ссылка» align=«left» />
                                                              &img src=«Ссылка» align=«right» />
                                                                0
                                                                Точнее так:
                                                                <img src="Ссылка" align="left" />
                                                                <img src="Ссылка" align="right" />
                                                              0
                                                              база не позволяет сделать поле `Path` длиннее 1000 символов (#1071 — Specified key was too long; max key length is 1000 bytes), что значит, что, если у нас средняя длина ID будет 4 символов мы не сможем делать деревья глубже 1000/(4+1), то есть самое глубокое возможное дерево в таком случае — 200 элементов. и 166 при средней длине ключа 5 цифр (если на сайте более 50000 комментариев в среднем)

                                                              Materialized path можно строить иначе. В таблице, описывающией иерархию будем хранить ссылку на объект (ElemId) и путь (Path).
                                                              ElemId, Path

                                                              В каждом сегменте пути будем записывать номер узла в поддереве по порядку (а не ElemId). И сделаем размер сегмента пути фиксированной длины (скажем 3 символа), чтобы сортировка по такому пути выдавала нам дерево в естественном порядке.
                                                              "000" -- первый уровень
                                                              "000000" -- второй уровень
                                                              "000001000"
                                                              "000001001"
                                                              "000002"
                                                              "001"
                                                              "002"

                                                              Уровень узла в таком дереве вычисляется по формуле Level = strlen(path) / 3.

                                                              Сейчас в каждом поддере можно создать не более чем 10^3 = 1000 узлов. Но если увеличить основание системы счисления, то емкость дерева возрастет. В php функция base_convert позволяет увеличить базу до 36. Т.е. емкость уже составит 36^3 = 46656. Для комментов этого достаточно. И размер пути получается небольшим. 1000 символов хватит для кодирования 1000/3 = 333 уровней. Ну, а скажем путь к комменту на 20-м уровне составит 20*3 = 60 символов. В MySQL есть аналогичная функция. Поэтому всю математику связанную с пересчетом пути при модификации дерева можно записывать прямо в запросе.

                                                              Конкретно под комментарии стратегию создания пути можно еще оптимизировать. Понятно что, чем глубже уровень, тем меньше «ветвистость» комментов. Максимальное число комментов стоит ожидать лишь на первом уровне. Поэтому только у первого сегмента пути оставим длину 3 символа. А остальные сегменты можно сократить и до 2-х. 1296 комментов на подуровне хватит заглаза. Таким образом путь к комменту на 20 уровне будет составлять всего 41 символ.
                                                              "000" -- первый уровень
                                                              "00000" -- второй уровень (2 символа в сегменте)
                                                              "0000100"
                                                              "0000101"
                                                              "00002"
                                                              "001"
                                                              "002"

                                                              Да, нужно обязательно ограничить длину индекса в таблице MySQL, для поля Path. Это не сильно скажется на производительности, зато позволит прилично сэкономить по памяти.
                                                                +1
                                                                стыдно признаться, но я не совсем понял, как с этим работать? может, вы напишите статью, где детально распишите этот способ с примерами того, как с ним работать?
                                                                  0
                                                                  Так элементарно же. Path обычный текст. Структура его фиксированна. В данном случае на каждый порядковый номер находящийся на одном уровне отводиться 3 символа. Если использовать только цифры, то на одном уровне может находиться только 1000 узлов.

                                                                  Т.е. к примеру у элементов на первом уровне (у которых нет предка) коды будут:
                                                                  000
                                                                  001
                                                                  002
                                                                  003
                                                                  004


                                                                  А коды для элементов которые являются потомками первого элемента (с Path=000) коды будут:
                                                                  000001
                                                                  000002
                                                                  000003


                                                                  Как и у любого метода тут есть свои тонкости и недостатки. К примеру, если потребуется переместить узел в другое место, а id элементов у нас возрастают последовательно (1, 2, 3 ....), то придется произвести пересчет элементов если новый элемент необходимо подключить первым (а не добаить в конец).
                                                                    0
                                                                    Не. Ну суть я понял. Я не понял, как с ним работать. Вот смотри — в тестах я написал функции getTreeByParent_MP и getTreeByParent_FH, которые позволяют одним запросом получить дерево по ID родителя. А как будет выглядеть такая функция для вашего метода? Как будет выглядеть перенос ветки на другое дерево и т.п? Я просто не совсем представляю, как с этим работать. Ну и, тем более, FH не накладывает совершенно никаких ограничений, как я уже говорил. Совершенно никаких.
                                                                      0
                                                                      Все данные по иерархии находятся в Path. Усли у нас есть элемент с 005003010, то для получения всех потомков для родительских элементов нужно будет сделать выборку по вхождения в Path подтроки 005.

                                                                      Перенос элемента потребует знать Path будующего родителя. Тогда к потребуется узнать максимальный номер его последнего потомка и увеличить его на величину шага. Для ускорения процесса max_id последнего потомка можно хранить в таблице подобно тому, как это делается для auto_increment поля для таблицы. Для всех непосредственных потомков этого узла придется сделать update поля Path. Так что все недостатки данного метода по большей части связанными именно при необходимости кроить дерево.

                                                                      ЗЫ. Метода не мой, и даже не мною используется, топикстартер данного треда не я ;)
                                                                0
                                                                интересно. спасибо. попробую использовать.
                                                                  –1
                                                                  писал нечто подобное — спасибо что осветили тему и тут спасибо коментаторам на доп. материал
                                                                    0
                                                                    Вот чего нету так єто возможности сортировки элементов одного уровня, хотя можно соответствующие поле создать в таблице с данными.

                                                                    А теперь нужно взять живую, большую, реальную базу и протестировать все методы на все возможные операции — єто будет интересно :)
                                                                        –1
                                                                        Ваш пример из разряда «как любую структуру БД запихнуть две таблицы».
                                                                        В общем-то, способ очень интересный, но это моделирование БД в самой же БД, потому что примерно таким же способом базы данных и хранят информацию о таблицах и данных внутри себя.
                                                                        Ваш метод интересен, но помоему совершенно не практичен для сложных структурированных БД, потому что вы не сможете писать сложные запросы, крестить и пересекать таблицы и т.д., а для больших задач тысячей мелких selectов не обойдетесь…
                                                                        ИМХО.
                                                                          –1
                                                                          опечатка: «как любую структуру БД запихнуть В две таблицы»
                                                                            0
                                                                            Вы уж простите, но я не совсем вас понял.
                                                                            Давайте начнём с того: какой способ вы предлагаете для хранения иерархических структур и чем этот способ лучше представленного в статье.
                                                                            Объясните также — что мне мешает писать сложные запросы в данном примере? Для меня удивительно такое заявление.
                                                                            Зачем мне тысячи мелких select'ов?
                                                                              –1
                                                                              Извините, я не хотел делать громких заявлений и шокировать вас. Честно говоря, я перед этим прочитал еще одну статью, а когда увидел вашу, она показалась очень схожа и я подумал что это примерно тоже самое, не особо вчитываясь. Так что приношу свои извинения относительно фразы «как любую структуру БД запихнуть В две таблицы».

                                                                              Но все-таки остается вопрос: почему не обойтись одной таблицей elements:
                                                                              id, parentid, parentlevel, data?
                                                                                0
                                                                                если сделать одну таблицу, то parentlevel не нужен, так как в parentid мы можем записать айди единственного элемента. — ближайшего и parentlevel будет у него 1. Если я правильно понял, о чём вы. Этот способ самый известный и логичный, и называется Adjacency List и его главный недостаток — выборка всего дерева начиная от определенной ветки, так как надо выбирать дерево рекурсивно, или другим способом — так же не очень производительным. Этот способ достаточно известен и в интернете можно найти список его недостатков)
                                                                                  –1
                                                                                  Наверное, Вы не совсем поняли меня.
                                                                                  Я понимаю что parentlevel не нужен, но если его добавить, то пример ни чем отличается от вашего.
                                                                                  В parentlevel просчитывается уровень вложенности элемента, тогда чтобы показать все элементы 2 уровня надо буде написать:
                                                                                  SELECT * FROM table WHERE parentlevel=2;
                                                                                  и тем самым не нужно рекурсивно опускаться вниз чтобы досчитать до какого-то уровня.
                                                                                    0
                                                                                    Я понимаю что parentlevel не нужен, но если его добавить, то пример ни чем отличается от вашего.

                                                                                    Если вы так говорите, значит вы или не читали статью, или читали её невнимательно.
                                                                                    чтобы показать все элементы 2 уровня надо буде написать:

                                                                                    Да, но так вы получите только один уровень. Но как получить всё дерево под определенным элементом?

                                                                                    В способе, который предложен в сабже ключевое не уровень элемента, а список ID всех родителей. Таким образом, выбрав определенный ID мы можем простым поиском по индексам найти список всех его детей, независимо от уровня вложенности.
                                                                                      0
                                                                                      Перепутал, коммент стер
                                                                                  0
                                                                                  вложенные множества чем не угодили?
                                                                                    0
                                                                                    я думаю, что все здесь знают о недостатках Nested Sets. Кто-то с этими недостатками смирился, но меня они — не устраивают. Особенно, по той причине, что есть альтернатива лучше.
                                                                                      0
                                                                                      А еще есть Netsted Intervals, у которых этих недостатков меньше, благодаря тому, что left и right задаются рациональными числами. Статья:
                                                                                      www.dbazine.com/oracle/or-articles/tropashko4, математика: arxiv.org/abs/0806.3115v1
                                                                                        0
                                                                                        какие недостатки тебя не устраивают?
                                                                                          +1
                                                                                          insert/update трудоемки.

                                                                                          А для select возможно даже получше чем MP будет.
                                                                                            +1
                                                                                            Тяжелые вставки. Не говоря уже о перемещениях (хотя, фиг с ними, с перемещениями, это не часто нужно).
                                                                                            В классических netsted sets вставка узла заставляет пересчитывать все правое поддерево. Достаточно даже небольшого количества одновременных запросов пользователей на добавление узла, чтобы база просела. Я имею ввиду, например, комменты.
                                                                                              0
                                                                                              можно подумать вставка узла в AL не требует обновления поля сортировки?
                                                                                              0
                                                                                              выше есть уже два сообщения по этому поводу. плюс мне не нравится идеология этого метода. я не говорю, что она плохая, я говорю, что она мне не нравится. Не нравится точно так же, как не нравятся суши. Понимаешь о чём я?
                                                                                                0
                                                                                                да, сатори ещё не постигло тебя…
                                                                                                  0
                                                                                                  а может — тебя? кто знает, кто из нас неправ?
                                                                                                    0
                                                                                                    ты слишком доверяешься своей интуиции. это непростительно даже для профи.
                                                                                                      0
                                                                                                      ну да. а ты в этом разговоре оперируешь фактами.
                                                                                                      вообще действительно на личности начался переход, потому я выхожу из этой обсуждения в этой ветке.
                                                                                                  0
                                                                                                  Вы хотите сказать, что у Вас апдейты будут более лёгкими? Тесты в студию в таком случае…

                                                                                                  Хотя, оценка снизу видна сразу: поскольку у вас просто нормализованный MP, то и производительность больше чем у MP быть не может.
                                                                                                    0
                                                                                                    поскольку у вас просто нормализованный MP, то и производительность больше чем у MP быть не может.

                                                                                                    Ну. Согласно тестам — производительность намного больше, чем в МП. Или вы исключительно про апдейты?
                                                                                                      0
                                                                                                      Разумеется, про апдейты — вставки, переносы… То, что селекты будут быстрыми — это и так понятно.
                                                                                                  0
                                                                                                  и, таки, какие преимущества у NS и NI по сравнению с предложенным в статье способом, кроме того что не используется дополнительная таблица (и преимущество ли это?)
                                                                                                    0
                                                                                                    NS славится чертовски легкими select'ами, с поиском по эффективному ключу. NI добавляет легкие вставки.

                                                                                                    В предлагаемом (защищаемом? ))) Вами методе:
                                                                                                    * для select необходим тяжелый inner join таблицы иерархии самой на себя.
                                                                                                    * присутствует бОльшая избыточность. Хотя программно используется лишь один запрос на вставку, база вставляет несколько записей (для которых нужно создать индекс и все это писать на диск).
                                                                                                    * Если в колонке таблицы многократно дублируются одни и те же значения, то индексы теряют эффективность.
                                                                                                    Все это вместе делает способ представления данных не эффективным.
                                                                                                    Не ясно, чем задается прядок узлов в дереве.
                                                                                                    Про дополнительную таблицу, простите, не понял…
                                                                                                      0
                                                                                                      тяжелый inner join

                                                                                                      Объясните, а откуда такая всеобщая боязнь JOIN'ов?
                                                                                                      Хотя программно используется лишь один запрос на вставку, база вставляет несколько записей

                                                                                                      Почему-то я не сомневаюсь, что в любой СУБД это дело очень хорошо оптимизированно
                                                                                                      Если в колонке таблицы многократно дублируются одни и те же значения, то индексы теряют эффективность.

                                                                                                      Ммм, какая интересная информация. Пруфлинк?
                                                                                                      Не ясно, чем задается прядок узлов в дереве.

                                                                                                      При необходимости — еще одним полем в таблице иерархии, по которому осуществляется сортировка
                                                                                                      Про дополнительную таблицу, простите, не понял…

                                                                                                      В NS и NI, в отличии от FH не создается еще одна таблица, что можно отнести к преимуществам.
                                                                                          0
                                                                                          использую этот же подход, но не храню уровень ибо count его дает
                                                                                            +1
                                                                                            Я как раз на SEF весной рассказывал про аналогичный метод:
                                                                                            www.slideshare.net/xorets/ss-1493870?type=presentation

                                                                                            Там описан метод обновления таблицы связей, который позволяет вставлять любую связь в любое место. Работает все довольно эффективно, мы используем давно и с удовольствием. Вот здесь все расписано в подробностях:
                                                                                            blogs.byte-force.com/media/p/1148.aspx
                                                                                              0
                                                                                              Расскажите пожалуйста поподробнее про условия эксплуатации вашей базы. Какова нагрузка? Кластеризуется ли база? Юзаете ли data sharding?
                                                                                              Или хотя бы какая вашу оценку, насколько решение будет живым в высоконагруженых приложениях.
                                                                                              Спасибо.
                                                                                              +1
                                                                                              База не кластеризуется, никаких ухищрений для распределения нагрузки по разным машинам не предпринималось. Я вообще не уверен, что схема типа шардинга может быть с успехом применена в таких условиях. Надо думать.

                                                                                              Схема точно работает хорошо с десятками тысяч объектов. С существенно большим кол-вом (больше 100 тыс) не проверяли. Уровень вложенности — 5-10.

                                                                                              Это точно работает на порядок (как минимум) быстрее, чем алгоритмы с итеративным выбором во временную таблицу. Ибо от них мы и избавлялись. А вот насколько быстрее вообще всех-всех вариантов, да еще и в разных условиях — я не знаю. Был бы рад, если кто-то взял на себя труд проверить.
                                                                                                0
                                                                                                спасибо
                                                                                                0
                                                                                                Можете привести пример запроса для выбора всех узлов (строк), исключая подчиненных для указанного?
                                                                                                  0
                                                                                                  Вы забыли написать в явном виде те «три простых запроса», которые нужны добрая добавления узла в дерево.

                                                                                                  Only users with full accounts can post comments. Log in, please.