Хранение деревьев в базе данных. Часть первая, теоретическая

Полгода назад написал бандл ClosureTable для фреймворка Laravel 3. Поводом для написания стала вот эта замечательная презентация Билла Карвина о способах хранения и обработки иерархических данных в MySQL с использованием PHP.

Итак. Существует несколько шаблонов проектирования баз данных для хранения и обработки иерархических структур:
  • Adjacency List («список смежности»)
  • Materialized Path («материализованный путь»)
  • Nested Sets («вложенные множества»)
  • Closure Table («таблица связей»)


Что такое Closure Table


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

Таблица связей должна содержать как минимум два поля:
  • ссылку на предка (ancestor)
  • ссылку на потомка (descendant)

Пусть мы работаем над созданием очередной SuperPuper CMS и приступили к разработке модуля редактирования текстовых страниц. Нам понадобятся две таблицы:
  • pages будет содержать данные о странице
  • pages_treepath будет содержать данные об иерархии страниц

Схема таблиц БД
Схема таблиц БД

В качестве примера используем следующую иерархию страниц:

   

Выборка потомков


Вот такой SQL-запрос у нас получится, если мы захотим выбрать все страницы раздела «О компании».

SELECT * FROM pages p
JOIN pages_treepath t ON (p.id = t.descendant)
WHERE t.ancestor = 1


Ветка полученного результата. Стрелки указывают на связи между страницами

«Descendant» означает «потомок», а «ancestor» — предок. Соответственно, чтобы получить все дочерние страницы, мы присоединяем таблицу связей pages_treepath при условии, что идентификатор страницы id имеет то же значение, что и ссылка на потомка descendant. При этом ссылка ancestor на родительскую страницу равняется 1, идентификатору страницы «О компании».

Выборка предков


А теперь снизу вверх: посмотрим всех «родителей» у страницы «Корпоративный».

SELECT * FROM pages p
JOIN pages_treepath t ON (p.id = t.ancestor)
WHERE t.descendant = 11

В этом случае наоборот. Мы ищем страницы выше по иерархии, поэтому присоединяем таблицу связей с условием, что идентификатор страницы id должен равняться ссылке на предка ancestor, а выборку осуществляем по ссылке на потомка descendant, в нашем случае равной 11.

Вставка нового элемента


Можно добавить новую вакансию. Данные ценности в нашем случае не представляют, так что посмотрим на сам запрос.

INSERT INTO pages
VALUES (12, 'Менеджер по продажам',
        '',
        'Требуется офигенный менеджер по продажам',
        '0000-00-00 00:00:00',
        '0000-00-00 00:00:00')
 
INSERT INTO pages_treepath (ancestor, descendant)
    SELECT ancestor, 12 FROM pages_treepath
    WHERE descendant = 4
    UNION ALL
    SELECT 12, 12

С первым запросом все ясно — это простая вставка новых данных. А вот второй запрос стоит разобрать по порядку, так что давайте посмотрим, что тут происходит.


Связи между элементами после вставки новой вакансии

SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4

Выполнив этот запрос, мы получим следующий список связей:
-------------------------
| ancestor | descendant |
-------------------------
|    4     |     12     |
|    1     |     12     |
-------------------------

Добавим к предыдущему запросу еще один путем объединения:

SELECT ancestor, 12 FROM pages_treepath WHERE descendant = 4
UNION ALL
SELECT 12, 12

В список связей добавится связь-ссылка страницы на саму себя:
-------------------------
| ancestor | descendant |
-------------------------
|    4     |     12     |
|    1     |     12     |
|   12     |     12     |
-------------------------

Как видите, данный SELECT-запрос позволяет установить связи между новой страницей и всеми её предками. ancestor — всегда ссылка на предка, descendant — ссылка на потомка. INSERT-запрос, написанный вначале, вставляет полученный результат в таблицу pages_treepath.

Удаление элемента


А теперь закроем вакансию веб-дизайнера.

DELETE FROM pages_treepath
WHERE descendant = 6
 
DELETE FROM pages
WHERE id = 6

Здесь всё просто. Сначала мы удаляем все связи, где ссылка на потомка равняется 6 (страница «Веб-дизайнер»), а затем удаляем и саму страницу.

Удаление вложенного дерева


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

DELETE FROM pages
WHERE id IN (
    SELECT descendant FROM (
        SELECT descendant FROM pages p
        JOIN pages_treepath t ON p.id = t.descendant
        WHERE t.ancestor = 7
    ) AS tmptable
)
 
DELETE FROM pages_treepath
WHERE descendant IN (
    SELECT descendant FROM (
        SELECT descendant FROM pages_treepath
        WHERE ancestor = 7
    ) AS tmptable
)

В отличие от предыдущего запроса, этот несколько сложнее и сначала удаляются сами страницы и уже после этого связи между ними (поскольку последние активно используются при удалении первых).

Сложность запросов отчасти объясняется тем, что MySQL не позволяет выполнять запрос на удаление записей с условием WHERE, в котором содержится выборка SELECT из той же таблицы. В случае с MySQL мы вынуждены поместить SELECT-запросы во временную таблицу. А в общем случае наши запросы выглядели бы так:

DELETE FROM pages
WHERE id IN (
    SELECT descendant FROM pages p
    JOIN pages_treepath t ON p.id = t.descendant
    WHERE t.ancestor = 7
)
 
DELETE FROM pages_treepath
WHERE descendant IN (
    SELECT descendant FROM pages_treepath
    WHERE ancestor = 7
)

Если вы внимательно посмотрите на вложенный SELECT-запрос в DELETE-запросе из таблицы pages, то обнаружите, что мы уже рассматривали подобный запрос. Этот от предыдущего отличается только идентификатором страницы. В результате выборки мы получаем все дочерние страницы раздела «Сайты» (включая сам раздел), а затем удаляем все страницы с полученными идентификаторами.

После того, как страницы удалены, остаётся удалить связи между ними. Для этого находим все ссылки на потомков descendant, где ссылка на предка равняется идентификатору страницы «Сайты».

Уровень вложенности


Еще в таблицу связей можно добавить поле, контролирующее уровень вложенности элементов. Это поле позволит составлять более простые запросы на выборку непосредственных предков или непосредственных потомков. Например:

SELECT * FROM pages p
JOIN pages_treepath t ON (p.id = t.descendant)
WHERE t.ancestor = 4
AND t.level = 2

Схема таблиц БД
Схема таблиц БД

Продолжение следует.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 66

    0
    А что на счет порядка элементов на одном уровне?
      0
      В статье забыл об этом упомянуть. За порядок может отвечать поле position, которое следует добавить в таблицу pages. От нуля и до бесконечности. В своей реализации я так и сделал.
        +2
        Может тогда в таблице pages_treepath? ибо в pages оно будет ни о чем, оторвано от логики
          +1
          Так в таблице pages_treepath оно ведь дублироваться будет. А так ведь страницы, категории и прочие — сортируемые ведь вещи. И к связям сортировка имеет лишь то отношение, что по позиции можно выбрать предыдущие или следующие элементы (prev siblings, next siblings).
      +1
      Правильно ли я понимаю, если я хочу вставить запись в самый низ структуры
      -level 1
      --level 2
      ---level 3
      ----level 4
      

      То в таблицу treepath придется добавить 4 записи?

      Вообще не помешало бы описание сильных и слабых сторон этого подхода.
        0
        Нет, таблица treepath хранит все связи. То есть каждый предок хранит информацию о своих дочерних элементах. В данном случае получится следующая таблица:

        ancestor | descendant | level
        ------------------------------
            1          1           0
            2          2           0
            3          3           0
            4          4           0
        ------------------------------
            1          2           1
            2          3           1
            3          4           1
        ------------------------------
            1          3           2
            2          4           2
        ------------------------------
            1          4           3
        

          0
          Почему нет? Для элемента 4 уровня имеем 4 записи.
            0
            Да, конечно, просто не так понял вопрос!
        0
        Попахивает велосипедом. Для постгреса есть нативные инструменты для древовидных данных, например
        www.postgresql.org/docs/9.1/static/ltree.html
        gbif.blogspot.nl/2012/06/taxonomic-trees-in-postgresql.html
          +1
          Так если и есть, то не везде. Это один из универсальных способов наряду с перечисленными в начале статьи.
        • UFO just landed and posted this here
            –1
            Можно, конечно, добавить внешние ключи. Однако они потеряют особый смысл, если у нас, например, будет поле level для уровня вложенности, которое при перестроении дерева всё равно надо будет обновлять. Или, к примеру, мы захотим удалить всю ветку комментариев или тех же страниц. От кастомного запроса, наподобие приведенных, в таком случае не уйти.
            • UFO just landed and posted this here
                0
                Очень ценные замечания! Честно говоря, не задумывался об этом. Исходил из того, что ORM в различных фреймворках зачастую оперируют таблицами, оставляя выбор добавления ключей за пользователем. Теперь будет пища для размышлений и реализации обозначенного вами в следующих версиях моей библиотечки :)
                • UFO just landed and posted this here
                    0
                    Как-то помнится на четвертом курсе я писал блог на CodeIgniter (PHP) в качестве ВКР, тоже использовал parent_id. Вот там выверты были с рекурсивным составлением запросов для выборки веток…
                  0
                  messsage deleted
              0
              Чуть более чем странный способ(как мне кажется). Если учесть что поле descendant скорее всего уникальное(из здравого смысла что у каждого узла в дереве всего один родитель), то можно просто вторую таблицу объединить с первой и завести стандартное поле «parent».

              Если же это поле неуникально, то, как выше писали коллеги, дополнительная таблица тольго добавит огромных проблем с целостностью — с ее помощью можно создавать циклы, полные графы и превращать структуру базы в макаронного монстра.
                0
                Фишка как раз в уходе от поля parent, в уходе от рекурсии и большого количества join-ов. Обратите внимание, что любой из приведенных запросов использует всего лишь один join. И дерево по такой таблице связей строится достаточно легко.

                А что касается проблем с целостностью, то я думаю, что это зависит от реализации интерфейса по работе с такой системой. Если интерфейс правильно организован, пользователь не сможет нагородить огород и всё поломать.
                  0
                  Если учесть что поле descendant скорее всего уникальное(из здравого смысла что у каждого узла в дереве всего один родитель),

                  Это проблема с терминологией автора поста (ему стоило бы использовать «потомки» вместо «дочерние элементы» и «предки» вместо «родители»). На самом деле в этой дополнительной таблице хранится транзитивное замыкание графа (в данном случае — дерева).

                  Из проблем самого подхода, даже если отвлечься от потенциальных проблем с ссылочной целостностью — квадратичный рост объема данных при увеличении дерева в глубину.
                    0
                    Уже посмотрел исходную презентацию. Я действительно запутался в терминологии — в презентации все понятнее и с картинками. А рост не квадратичный, на самом деле — для более-менее сбалансированного дерева, объем второй таблицы будет N*высоту дерева ~ N*log(N), а высота редко бывает больше 5-7, как мне кажется.
                      0
                      Это очень сильно зависит от характера роста дерева, почему я и оговорился о «росте в глубину». В вырожденном случае линейного списка будет как раз квадратичный рост.
                        0
                        Ну так давайте и хеш-таблицы никогда не юзать, ссылаясь на то, что самый пессимистичный вариант — это O(N)
                          0
                          Ну так я и не говорил, что транзитивное замыкание следует никогда не юзать. Просто о худшем случае всегда нужно помнить, например в случае хеш-таблиц — о коллизиях в используемой хеш-функции. А то ведь бывает и так: bugs.php.net/bug.php?id=60623
                            0
                            И всё же деревья с очень большой глубиной — это довольно редкое явление. По крайней мере, можно всегда постараться перепроектировать дерево, чтобы обеспечить лучшую балансировку.
                  +1
                  Опыт показал что иерархические данные обычно очень редко меняются, но часто запрашиваются. А в этом случае Nested Sets рулят и бибикают, по скорости работы выборок им нет равных. Да и запросы как ни странно выходят проще и нагляднее, даже в случае сложных выборок.
                    0
                    Мне как раз наоборот субъективно кажется, что у Closure Table запросы попроще :) И еще нравится, что связи отделены от самих сущностей.
                      +1
                      Ну связи можно спокойно отделить в любом подходе, отдельно хранить таблицу данных, отдельно — таблицу связей.

                      Для Nested Sets легко писать запросы к иерархии. Например полуоткрытое дерево можно одним запросом получить.
                      И самое главное что их легко визуализировать, нарисовали дерево, затем обвели «облачком» те узлы что нужно получить — и стали понятны условия запроса.
                        +1
                        Это скорее от того, что сидели и разбирались в этом подходе.
                        В Nested Sets так же все относительно просто после понимания того, как и зачем выставляются l-key & r-key
                        0
                        Nested Sets не обеспечивают referential integrity. Closure Table — обеспечивает. Кроме того, не подскажите, как в Nested Sets запросить только детей первого уровня, а не всё поддерево?
                          0
                          Почему это не обеспечивают ссылочную целостность?
                          Точно так-же используются суррогатные (автоинкрементные) ключи для ссылок.
                          Целостность данных обеспечивается транзакциями, нет никакой разницы между методами (ну если только не MYSQL/MyISAM использовать)
                          Для работы с «уровнями» дерева обычно их обычно кэшируют в отдельном поле LEVEL.
                            0
                            Какие такие суррогатные ключи? Nested Sets использует две специальных колонки с числами, которые не являются foreign ключами.
                              0
                              А зачем, простите их использовать как внешние ключи?
                              На что им ссылаться? Это же данные о структуре дерева, чем они от других данных-то отличаются?

                              Для ссылок НА ветку дерева, у каждой строки имеется первичный ключ, т.к. естественного ключа нет — используется суррогатный — автоинкремент например. Хотя на практике для первичного ключа сейчас всегда используют суррогатные ключи даже при наличии естественного.
                                +1
                                В смысле, зачем нужны внешние ключи? За тем, что если это не внешний ключ, а просто Integer колонка, то в эти колонки можно написать любое число, какое только придёт в голову. Если же это внешний ключ, то можно вставить только то число, которое является реальным первичным ключом какой-то строки. Кроме того, если вы попытаетесь удалить эту запись из таблицы, то при отсутствии внешнего ключа таблица останется в несогласованном состоянии. В случае наличия внешнего ключа удалить строку не получится, потому что нельзя удалить строку, на которую остались ссылаться внешние ключи (либо можно удалить через cascade delete)
                              0
                              Вы заблуждаетесь. Транзакции обеспечивают атомарность, а не целостность. Целостность обеспечивают внешние ключи.
                                0
                                Я может и заблуждаюсь, но не понимаю в чем тут проблема.

                                Структура таблицы Nested Sets

                                id — первичный суррогатный ключ (автоинкремент)
                                left — левая граница
                                right — правая граница
                                level — уровень вложенности (кэшированное значение, можно пересчитать)
                                field1 — поле данных 1 (все поля данных можно спокойно вынести в отдельную таблицу, если хочется)
                                field2 — поле данных 2

                                fieldN — поле данных N

                                Если нужно сослаться на элемент дерева — ссылаемся на значение id

                                В чем проблема-то? Где тут нарушение ссылочной целостности? Приведите возможный сценарий.
                                Целостность данных структуры как вы правильно заметили обеспечивает атомарность транзакций.
                                  0
                                  Нарушение ссылочной целостности, в несколько натянутом смысле термина: пересекающиеся (а не вложенные) диапазоны left-right. В случае adjacency list на колонку parent_id можно можно поставить внешний ключ, ссылающийся на id в той же таблице, и, таким образом, избежать возможных проблем с нарушением целостности дерева.
                                    0
                                    Проблема в том, что СУБД ничего не знает про свойство left и right как чисел, являющихся границами поддерева. Соответственно в left и right вы можете запихать любое число. Единственное, что вас сдерживает — это, дай бог, правильно написанный код, обрабатывающий вставку и удаление строк в эту таблицу. Closure Table с помощью внешних ключей даёт больше гарантий, потому что СУБД гарантирует ссылочную совместимость (хотя этого не достаточно для 100%-ной целостности).
                                      0
                                      В Closure Table точно так-же легко вставить ссылочно-правильные данные, но логически бессмысленные данные например сделать цикл, сославшись на родителя как на ребенка.

                                      Нужно изучить на практике, идея интересная, но мне лично напоминает Materialized Path вынесенный в отдельную таблицу.
                                        0
                                        Цикл — дело конечно гадостное, но куда хуже если у вас потомок будет ссылаться на несуществующего родителя.
                                          +1
                                          Тут мне кажется нет «хуже» или «лучше». Это как говорить — «пусть алгоритм неправильно делит на 5, но куда хуже если он будет неправильно делить на 6».

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

                                          Реальную проблему видел один раз — когда такое дерево положили в MyISAM :-)
                                            0
                                            Подскажите, пожалуйста, в чем была проблема и чем все закончилось?
                                              0
                                              Так очевидно же — нарушение целостности дерева. В myisam транзакций нет, а любая операция с деревом затрагивает много строк. В итоге часть строк изменилась, часть нет.

                                              Восстановили из бэкапа, таблицы перевели в InnoDB (база была по ошибке создана в MyISAM)
                                          0
                                          напоминает Materialized Path вынесенный в отдельную таблицу

                                          Так и есть. Без ограниченности глубины дерева, лучшей скорости поиска и другого
                                  0
                                  Кроме того, не подскажите, как в Nested Sets запросить только детей первого уровня, а не всё поддерево?

                                  Очень, очень медленно и осторожно :) Не быстрее, чем все поддерево:
                                  select c.leftKey, c.rightKey 
                                  from Tree c inner join Tree p 
                                    on c.leftKey between p.leftKey and p.rightKey 
                                  where 
                                    p.leftKey between $l and $r
                                    and c.leftKey between $l and $r
                                  group by c.leftKey, c.rightKey
                                  having count(*) = 2
                                  
                                    +1
                                    Для скорости обычно кэшируют LEVEL, он легко вычисляется.
                                    Тогда запросы тривиальны, никаких группировок, просто WHERE parent.LEVEL = child.LEVEL — 1
                                    0
                                    в Nested Sets запросить только детей первого уровня, а не всё поддерево?

                                    Добавить поле generation.

                                    Integrity нет. А для какой цели она вам понадобилась?
                                  0
                                  <удалено>
                                    0
                                    В таблицу отношений добавьте ещё поле is_deleted (bool), чтобы физически не удалять отношения и не фрагментировать тем самым таблицу. Ускоряет перемещение пользователем туда-обратно свои записи (например пункты меню).
                                      0
                                      во многих БД это так и сделано только уровнем ниже, так что is_deleted — это ненужный велосипед на мой взгляд.
                                        0
                                        в MySQL5 есть такое?
                                    • UFO just landed and posted this here
                                        0
                                        Почему мне кажется что запись:
                                        ancestor — 12
                                        descendant — 12

                                        при вставке не нужна? Ну или не должна быть нужна… костыль какой-то(страница является предком для себя и потомком для себя).
                                          0
                                          Костыли будут в алгоритмах без этой записи
                                            0
                                            Ссылка на самого себя действительно позволяет без костылей формировать запросы на выборку ветки. Такой записью, если хотите, помечается возможность ноды быть как предком, так и потомком.
                                            0
                                            А еще тут можно не удалять данные, а удалять только связи. Так быстрее. А данные не имеющие связей чистить по крону ночью :) Также это возможность вернуть ошибочно удаленные данные — их надо просто перепривязат
                                              0
                                              Есть такое дело. Хотя, в принципе, такую вещь можно было бы применить и к другим методам хранения деревьев. Разве что не к Adjacency List, наверное.
                                              0
                                              Если в pages_treepath добавить уровень вложенности, и с уровнем вложености -1 указывать полный путь от корня — то все стандартные запросы к базе данных будут полностью ложится в индэксы. Собственно говоря именно так и делал в конце 90х.
                                                0
                                                Спасибо за пост, познавательно. Если позволите, хотел предложить разделить запрос:
                                                INSERT INTO pages_treepath (ancestor, descendant)
                                                SELECT ancestor, 12 FROM pages_treepath
                                                WHERE descendant = 4
                                                UNION ALL
                                                SELECT 12, 12

                                                на два: отдельно выборка и далее вставка.
                                                Я понимаю, что планируется используются запросы по индексам и так далее, но все же лучше перестраховаться. Данная связка может вызвать продолжительную блокировку pages_treepath, что может окажазать ощутимое влияние на производительность. Одна из статей про это на Percona
                                                  0
                                                  Еще одно полезное замечание! Учту это в следующих версиях библиотечки ;)
                                                  +1
                                                  Презентация о моделях иерархических данных MySQL и PHP от Била Карвина из Percona:
                                                    0
                                                    Так у меня на нее и ссылка в начале статьи :)
                                                    0
                                                    данный подход не обеспечивает древовидности, это стандартная модель ненаправленного графа связей. В MariaDB есть специальный движок для работы с графами. Древовидность — это возможность получить дерево в 1 запрос, а не получить все связи элемента. Думаю AL в конечном счёте и то побыстрее будет работать чем это огромная таблица связей.
                                                      0
                                                      А какая РСУБД может возвращать дерево вместо списка найденных записей? Обычно этот метод комбинируется с AL (в pages добавляется parent_page) для простоты формирования дерева из списка выбранных записей.
                                                        0
                                                        Вы правы, о таких РСУДБ мне неизвестно. Поэтому, я отвечу несколько абстрактно — древовидность бы обеспечила та РСУБД, которая бы предоставляла возможность делать UNION/JOIN по иерархическим структурам некими внутренними механизмами где задаются цели запроса и критерии отбора элементов дерева. Конечно это уже не в рамках (PL/)SQL. Т.е. нужен отдельный парсер, синтаксис(+движок хранения если мы о MySql говорим) для иерархических запросов. Я ЗА любой из алгоритмов(кроме NS т.к. перестройка дерева вверх и невозможность обеспечения целостности это зло) но чтобы он был реализован средствами СУБД. Поэтому пока все как Вы и сказали :(
                                                        0
                                                        У меня превращение плоского списка с записями дерева в «настоящее» дерево программно решено: после выборки происходит превращение.

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