Pull to refresh

Comments 66

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

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

Вообще не помешало бы описание сильных и слабых сторон этого подхода.
Нет, таблица 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

Почему нет? Для элемента 4 уровня имеем 4 записи.
Да, конечно, просто не так понял вопрос!
Так если и есть, то не везде. Это один из универсальных способов наряду с перечисленными в начале статьи.
UFO just landed and posted this here
Можно, конечно, добавить внешние ключи. Однако они потеряют особый смысл, если у нас, например, будет поле level для уровня вложенности, которое при перестроении дерева всё равно надо будет обновлять. Или, к примеру, мы захотим удалить всю ветку комментариев или тех же страниц. От кастомного запроса, наподобие приведенных, в таком случае не уйти.
UFO just landed and posted this here
Очень ценные замечания! Честно говоря, не задумывался об этом. Исходил из того, что ORM в различных фреймворках зачастую оперируют таблицами, оставляя выбор добавления ключей за пользователем. Теперь будет пища для размышлений и реализации обозначенного вами в следующих версиях моей библиотечки :)
UFO just landed and posted this here
Как-то помнится на четвертом курсе я писал блог на CodeIgniter (PHP) в качестве ВКР, тоже использовал parent_id. Вот там выверты были с рекурсивным составлением запросов для выборки веток…
Чуть более чем странный способ(как мне кажется). Если учесть что поле descendant скорее всего уникальное(из здравого смысла что у каждого узла в дереве всего один родитель), то можно просто вторую таблицу объединить с первой и завести стандартное поле «parent».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так и есть. Без ограниченности глубины дерева, лучшей скорости поиска и другого
Кроме того, не подскажите, как в 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
Для скорости обычно кэшируют LEVEL, он легко вычисляется.
Тогда запросы тривиальны, никаких группировок, просто WHERE parent.LEVEL = child.LEVEL — 1
в Nested Sets запросить только детей первого уровня, а не всё поддерево?

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

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

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

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