Хранение иерархических структур. Симбиоз «Closure Table» и «Adjacency List»

Когда перед нами встаёт задача хранения и управления иерархическими структурами данных всегда приходится выбирать из довольно ограниченного набора паттернов. Для того чтобы найти наиболее подходящий шаблон необходимо проанализировать особенности каждого способа хранения и обработки данных и оценить их с учётом задачи и специфики используемой СУБД.

Предположим, существует задача, предоставить возможность пользователям сайта оставлять комментарии к публикациям. Комментарии должны иметь древовидную структуру, пользователи должны иметь возможность оставить один или более комментариев к посту, а также отвечать на любые комментарии других пользователей. То есть, нужна система комментариев аналогичная той, что мы можем видеть на Habrahabr. По каким-то причинам, нам не подходят готовые решения, допустим из-за того, что предполагается дополнительная очень сложная бизнес-логика, которая должна быть интегрирована в систему комментариев.

Наша цель – разработать свою реализацию, учитывающую требования нашего приложения.

Что для нас важно?


  1. Минимизировать количество запросов к базе данных. В частности, для извлечения ветки комментариев должно быть достаточно одного запроса.
  2. Получить высокую производительность, поэтому запросы к базе данных, особенно на чтение, должны быть простыми и выполняться быстро даже при большом объёме данных.
  3. Хранить текст комментариев и иерархическую структуру дерева в разных таблицах.
  4. Иметь возможность отсортировать извлечённые из базы данных комментарии, чтобы в результате отобразить их в естественном виде, как древовидную иерархическую структуру или, что ещё лучше, сразу извлечь из базы данных отсортированное дерево.
  5. Контролировать глубину вложенности комментариев.
  6. Гарантировать целостность данных.
  7. Учесть специфику MySQL. Как известно, эта СУБД не поддерживает рекурсивные запросы. Рекурсия в этой СУБД возможна только в хранимых процедурах с ограничением вложенности — не более 255 уровней.
  8. Требования вполне обоснованные и актуальные для многих проектов.

Итак, рассмотрим известные способы хранения и работы с деревьями. Их не так уж и много:

image

Детали реализации этих паттернов отлично рассмотрены в презентации Билла Карвина (Bill Karwin).

Особенность метода «Adjacency List», заключается в том, что без поддержки рекурсивных запросов СУБД, извлечь одним простым запросом произвольную часть иерархии невозможно. Поэтому, в контексте использования MySQL этот вариант нас совершенно не устраивает.

Метод «Path Enumeration» (или как его ещё называют «Materialized Path»), очевидно, нам тоже не подходит, ввиду низкой производительности SQL-запросов SELECT, так как предполагается использование оператора LIKE и поиск по шаблонам вида: ‘1/2/3/4%’. Хранение некого множества в виде строки с разделителями, едва ли уместно в мире реляционных баз данных.

Пожалуй, самый интересный паттерн для работы с древовидными структурами – Nested Sets. Он вполне может быть использован для нашей задачи, но его реализация довольно сложная и он не обеспечивает целостность данных. Ошибка при вставке нового элемента в иерархию или при переносе поддерева из одного места в другое может создать большие проблемы. Необходимость пересчёта и изменения значений части левых и правых индексов элементов поддерева при добавлении нового элемента, вне всяких сомнений, является существенным недостатком Nested Sets.

Последний метод «Closure Table», исходя из наших требований, мог бы стать лучшим выбором, если бы не одно «но» — отсутствие простого способа построить отсортированное дерево из получаемого запросом плоского списка связей.

Давайте рассмотрим этот шаблон работы с древовидными структурами данных подробнее.

Схема связей элементов дерева «Closure Table» выглядит следующим образом:

image

Предположим, у нас есть иерархия комментариев, которая соответствует приведённой выше схеме связей:

Таблица comments:

image

Таблица commentsTree:

image

Получить список всех элементов нужной нам части дерева можно следующим запросом (извлечём дерево начиная от `commentsTree`.`idAncestor` = 1):

SELECT 
`tableData`.`idEntry`,
`tableData`.`content`,
`tableTree`.`idAncestor`, 
`tableTree`.`idDescendant`, 
`tableTree`.`level`, 
`tableTree`.`idSubject` 
FROM `comments` AS `tableData`
JOIN `commentsTree` AS `tableTree` 
  ON `tableData`.`idEntry` = `tableTree`.`idDescendant`
WHERE `tableTree`.`idAncestor` = 1 

В результате получим:

image

Всё просто! Но извлечённые строки нужно преобразовать в отсортированную древовидную иерархию. Именно она нам нужна. Увы, данных для преобразования этого множества в нужную нам форму недостаточно.

Как же нам решить эту проблему?

Вариант 1. Заставим СУБД сортировать дерево


Существует довольно оригинальный способ, при помощи которого можно получить из базы данных сразу отсортированную древовидную иерархию, причём всего одним запросом. Известный разработчик Билл Карвин (Bill Karwin) предложил весьма изящный вариант решения задачи извлечения отсортированного дерева:

SELECT 
`tableData`.`idEntry`, 
`tableData`.`content`, 
`tableTree`.`level`, 
`tableTree`.`idAncestor`, 
`tableTree`.`idDescendant`, 
GROUP_CONCAT(`tableStructure`.`idAncestor`) AS `structure` 
FROM 
`comments` AS `tableData` 
JOIN `commentsTree` AS `tableTree` 
ON `tableData`.`idEntry` = `tableTree`.`idDescendant` 
JOIN `commentsTree` AS `tableStructure` 
ON `tableStructure`.`idDescendant` = `tableTree`.`idDescendant`
WHERE `tableTree`.`idAncestor` = 1 
GROUP BY `tableData`.`idEntry` 
ORDER BY `structure`

В результате мы получим, то что нам нужно:

image

Но, как не сложно заметить, такой способ будет корректно работать только в случае, когда длина идентификаторов idAncestor у всех строк, отвечающих условию запроса, одинаковая. Обратите внимание на следующий фрагмент SQL-запроса: «GROUP_CONCAT(tableStructure.idAncestor ORDER BY tableStructure.level DESC) AS structure». Сортировка строк содержащих множества «12,14,28» и «13,119,12» будет некорректной с точки зрения нашей задачи. То есть, если все идентификаторы в запрашиваемой части дерева одинаковой длинны, то сортировка верная, а в случае если это не так, то структура дерева будет нарушена. Уменьшить количество неправильных сортировок можно, задав начало отсчёта идентификаторов с большого целого числа, например 1000000, указав в SQL запросе при создании таблицы AUTO_INCREMENT=1000000.

Для того чтобы полностью избавится от этой проблемы, можно указать для столбца идентификатора idAncestor параметр ZEROFILL, в этом случае СУБД будет автоматически добавлять атрибут UNSIGNED и идентификаторы буду выглядеть примерно так: 0000000004, 0000000005, 0000000194.

Для некоторых задач, без сомнений, можно использовать этот способ. Но давайте всё-таки постараемся избежать использования двух JOIN’ов при работе с двумя таблицами, функции GROUP_CONCAT(), да ещё и параметра ZEROFILL.

Вариант 2. Симбиоз двух методов «Closure Table» и «Adjacency List»


Давайте ещё раз посмотрим на метод «Closure Table». В плоском списке связей иерархической структуры, который мы получаем всего одним запросом, нам, очевидно, не хватает информации о связи каждого элемента со своим родителем, для того, чтобы мы смогли построить отсортированное дерево. Поэтому, давайте добавим поле idNearestAncestor в таблицу commentsTree и будем сохранять там ссылку на элемент, который является ближайший предком.

image

Таким образом, мы получили симбиоз двух методов «Closure Table» и «Adjacency List». Теперь формирование правильно отсортированной иерархической структуры — тривиальная задача. И самое главное, мы нашли решение, которое полностью отвечает требованиям.

Следующим запросом мы получим необходимые для построения дерева данные:

SELECT 
`tableData`.`idEntry`,
`tableData`.`content`,
`tableTree`.`idAncestor`, 
`tableTree`.`idDescendant`, 
`tableTree`.`idNearestAncestor`, 
`tableTree`.`level`, 
`tableTree`.`idSubject` 
FROM `comments` AS `tableData`
JOIN `commentsTree` AS `tableTree` 
ON `tableData`.`idEntry` = `tableTree`.`idDescendant`
WHERE `tableTree`.`idAncestor` = 1 

Критика «Closure Table»


Шаблон «Closure Table» часто критикуют за то, что необходимо хранить в базе данных связи каждого элемента дерева со всеми его предками, а так же ссылку каждого элемента на самого себя. Чем глубже в иерархии располагается элемент, тем больше записей в таблице необходимо сделать. Очевидно, что добавление новых элементов в конец глубокой древовидной иерархии будет менее эффективным, чем вставка элементов вблизи корня дерева. Кроме этого, стоит отметить, что для хранения деревьев метод Closure Table требует больше места в базе данных, чем любой другой метод.

Для того чтобы объективно оценить значимость этих замечаний, их следует рассматривать в контексте специфики реального проекта. Например, снижение производительности при добавлении нового элемента на двухвостый или тысячный уровень может быть незначительным или некритичным для работы приложения, или же, что ещё более вероятно, такая ситуация вовсе никогда не произойдёт. Как правило, в реальной жизни нет необходимости в иерархических структурах большой вложенности. Кроме этого, в большинстве случаев, принципиальным параметром является скорость извлечения данных, а не записи. Объём дискового пространства, который может потребовать структура дерева едва ли стоит учитывать, так как другие потребители этого ресурса намного более значимые, например логирование посетителей сайта.

Пример моей реализации системы древовидных комментариев основанной на методах «Closure Table» и «Adjacency List» на github.

Используемые материалы

  1. Презентация Билла Карвина (Bill Karwin). http://www.slideshare.net/billkarwin/models-for-hierarchical-data
  2. Обсуждение вопросов сортировки деревьев на stackoverflow. http://stackoverflow.com/questions/8252323/mysql-closure-table-hierarchical-database-how-to-pull-information-out-in-the-c, http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree
  3. Документация MySQL

Средняя зарплата в IT

110 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 8 385 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 22

    0
    А где же вариант «использовать более подходящую бизнес требованиям субд»? в данном случае, очевидно, стоило реляционную заменить на графовую
      +2
      Что? Использовать отдельную СУБД для комметов только? Зачем увеличивать сложность системы, если можно просто немного подумать?
        –2
        Количество «древовидных» моделей будет только увеличиваться. Дерево комментариев, граф друзей, таксономия разделов и тд и тп. Зачем в этих условиях вообще связываться с реляционными субд — ума не приложу.
          0
          Вы не совсем правы.

          Современные реляционные СУБД вполне позволяют хранить в реляционной форме описание иерархических структур и делать по ним выборки. Тут рекомендую почитать про рекурсивные запросы. Не уверен поддерживает ли их MySQL но если даже нет то это проблема одного продукта а не всех реляционных баз.
            0
            Можно пример такого рекурсивного запроса?
              0
              www.postgresonline.com/journal/archives/131-Using-Recursive-Common-table-expressions-to-represent-Tree-structures.html
              www.postgresql.org/docs/8.4/static/queries-with.html
              habrahabr.ru/post/73700

              можно найти и больше инфы.

              Кроме того, я видел как такие вещи довольно успешно применяются в «энтерпрайзе», то есть это не отдельная малоизвестная фитчя.
                0
                Вы имеете ввиду что-то типа этого?

                -- PostgreSQL --
                WITH RECURSIVE temp1 ( "ID","PARENT","DESCRIPTION",PATH, LEVEL ) AS (
                SELECT T1."ID",T1."PARENT", T1."DESCRIPTION", CAST (T1."ID" AS VARCHAR (50)) as PATH, 1
                    FROM KPO T1 WHERE T1."PARENT" IS NULL
                union
                select T2."ID", T2."PARENT", T2."DESCRIPTION", CAST ( temp1.PATH ||'->'|| T2."ID" AS VARCHAR(50)) ,LEVEL + 1
                     FROM KPO T2 INNER JOIN temp1 ON( temp1."ID"= T2."PARENT")      )
                select * from temp1 ORDER BY PATH LIMIT 100
                

                Сколько времени вам потребуется, чтобы понять, что тут происходит и где ошибка?

                -- OrientDB --
                select id , parent , description , $path , $depth from (
                	traverse child from (
                		select from kpo where id = 'KPO'
                	)
                )
                

                А тут?
                  0
                  Если честно то имея опыт работы с первым я вполне понимаю что там происходит. И симметрично — я не представляю как работает второй пример. Хотя я не берусь утверждать что разобравшись с OrientDB не переменю свое мнение.
          +1
          А если все перечисленное выше — дай бог 10% функциональности проекта?

          Зачем в данном случае связываться с нереляционными СУБД — ума не приложу.
            0
            Можно пример такого проекта?
              0
              habrahabr.ru
                –1
                Ой ли?

                — все посты из хабов на которые подписан такой-то пользователь и всех подхабов и для каждого инфу о лайках, просмотрах, добавлениях в избранное, числе комментариев

                — комментарии к такой-то публикации и для каждого информацию о том сколько и как их лайкнуло и как лайкнул их такой-то пользователь

                — последние публикации сотни пользователей с максимальным рейтингом из такого-то региона

                — список тэгов проставленных публикациям, в которых такой-то пользователь хотя бы один комментарий добавил в избранное

                Страшно даже представить эти SQL запросы :-)
      0
      Для того чтобы использовать графовую базу данных в проекте, нужно иметь разработчиков, которые с ней умеют работать.
        0
        Вы так говорите, будто этому учиться нужно пару лет :-)
      +1
      А где сравнение производительности?
      Что-то мне подсказывает что апдейтить индексы на больших деревьях быстрее(для nested set), чем вставлять тысячи строк на каждую новую, а на небольших количествах данных (до 10 тысяч) разница мне кажется несущественна.
        +1
        Интересно, что мешает добавить к полям Nested Sets еще parent и level и получить неограниченно масштабируемую структуру с преимуществами обоих моделей — и NS и AL? (Ну, кроме произвольной сортировки, ОК)
        Всегда считал такой подход «золотым стандартом» для хранения древовидных структур. Я ошибаюсь?
          +1
          А зачем хранить parent? Родителя можно получить по ключам left и right.
          Сам использую Nested Sets для хранения дерева сайта, level нужен в моем случае, чтобы не крутить рекурсию для построения меню сайта, дерево сайта получается из одного запроса бд и одного цикла программного.
            0
            Для того, чтобы в любимой ORM можно было написать что-то вроде

            'relations' => [
              'parent' => ['type' => 'belongsTo', 'model' => self::class, 'by' => '__parent_id']
            ]
            


            и затем иметь возможность
            $this->parent;
            
          –1
          Про CT уже было на хабре, довольно неплохо расписано.

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

          Самое читаемое