Комментарии 66
А что на счет порядка элементов на одном уровне?
Правильно ли я понимаю, если я хочу вставить запись в самый низ структуры
То в таблицу treepath придется добавить 4 записи?
Вообще не помешало бы описание сильных и слабых сторон этого подхода.
-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
Попахивает велосипедом. Для постгреса есть нативные инструменты для древовидных данных, например
www.postgresql.org/docs/9.1/static/ltree.html
gbif.blogspot.nl/2012/06/taxonomic-trees-in-postgresql.html
www.postgresql.org/docs/9.1/static/ltree.html
gbif.blogspot.nl/2012/06/taxonomic-trees-in-postgresql.html
НЛО прилетело и опубликовало эту надпись здесь
Можно, конечно, добавить внешние ключи. Однако они потеряют особый смысл, если у нас, например, будет поле
level для уровня вложенности, которое при перестроении дерева всё равно надо будет обновлять. Или, к примеру, мы захотим удалить всю ветку комментариев или тех же страниц. От кастомного запроса, наподобие приведенных, в таком случае не уйти.НЛО прилетело и опубликовало эту надпись здесь
Очень ценные замечания! Честно говоря, не задумывался об этом. Исходил из того, что ORM в различных фреймворках зачастую оперируют таблицами, оставляя выбор добавления ключей за пользователем. Теперь будет пища для размышлений и реализации обозначенного вами в следующих версиях моей библиотечки :)
Чуть более чем странный способ(как мне кажется). Если учесть что поле 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 легко писать запросы к иерархии. Например полуоткрытое дерево можно одним запросом получить.
И самое главное что их легко визуализировать, нарисовали дерево, затем обвели «облачком» те узлы что нужно получить — и стали понятны условия запроса.
Это скорее от того, что сидели и разбирались в этом подходе.
В Nested Sets так же все относительно просто после понимания того, как и зачем выставляются l-key & r-key
В Nested Sets так же все относительно просто после понимания того, как и зачем выставляются l-key & r-key
Nested Sets не обеспечивают referential integrity. Closure Table — обеспечивает. Кроме того, не подскажите, как в Nested Sets запросить только детей первого уровня, а не всё поддерево?
Почему это не обеспечивают ссылочную целостность?
Точно так-же используются суррогатные (автоинкрементные) ключи для ссылок.
Целостность данных обеспечивается транзакциями, нет никакой разницы между методами (ну если только не MYSQL/MyISAM использовать)
Для работы с «уровнями» дерева обычно их обычно кэшируют в отдельном поле LEVEL.
Точно так-же используются суррогатные (автоинкрементные) ключи для ссылок.
Целостность данных обеспечивается транзакциями, нет никакой разницы между методами (ну если только не MYSQL/MyISAM использовать)
Для работы с «уровнями» дерева обычно их обычно кэшируют в отдельном поле LEVEL.
Какие такие суррогатные ключи? Nested Sets использует две специальных колонки с числами, которые не являются foreign ключами.
А зачем, простите их использовать как внешние ключи?
На что им ссылаться? Это же данные о структуре дерева, чем они от других данных-то отличаются?
Для ссылок НА ветку дерева, у каждой строки имеется первичный ключ, т.к. естественного ключа нет — используется суррогатный — автоинкремент например. Хотя на практике для первичного ключа сейчас всегда используют суррогатные ключи даже при наличии естественного.
На что им ссылаться? Это же данные о структуре дерева, чем они от других данных-то отличаются?
Для ссылок НА ветку дерева, у каждой строки имеется первичный ключ, т.к. естественного ключа нет — используется суррогатный — автоинкремент например. Хотя на практике для первичного ключа сейчас всегда используют суррогатные ключи даже при наличии естественного.
В смысле, зачем нужны внешние ключи? За тем, что если это не внешний ключ, а просто Integer колонка, то в эти колонки можно написать любое число, какое только придёт в голову. Если же это внешний ключ, то можно вставить только то число, которое является реальным первичным ключом какой-то строки. Кроме того, если вы попытаетесь удалить эту запись из таблицы, то при отсутствии внешнего ключа таблица останется в несогласованном состоянии. В случае наличия внешнего ключа удалить строку не получится, потому что нельзя удалить строку, на которую остались ссылаться внешние ключи (либо можно удалить через cascade delete)
Вы заблуждаетесь. Транзакции обеспечивают атомарность, а не целостность. Целостность обеспечивают внешние ключи.
Я может и заблуждаюсь, но не понимаю в чем тут проблема.
Структура таблицы Nested Sets
id — первичный суррогатный ключ (автоинкремент)
left — левая граница
right — правая граница
level — уровень вложенности (кэшированное значение, можно пересчитать)
field1 — поле данных 1 (все поля данных можно спокойно вынести в отдельную таблицу, если хочется)
field2 — поле данных 2
…
fieldN — поле данных N
Если нужно сослаться на элемент дерева — ссылаемся на значение id
В чем проблема-то? Где тут нарушение ссылочной целостности? Приведите возможный сценарий.
Целостность данных структуры как вы правильно заметили обеспечивает атомарность транзакций.
Структура таблицы 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 вынесенный в отдельную таблицу.
Нужно изучить на практике, идея интересная, но мне лично напоминает Materialized Path вынесенный в отдельную таблицу.
Цикл — дело конечно гадостное, но куда хуже если у вас потомок будет ссылаться на несуществующего родителя.
Тут мне кажется нет «хуже» или «лучше». Это как говорить — «пусть алгоритм неправильно делит на 5, но куда хуже если он будет неправильно делить на 6».
Алгоритм вставки тривиален, удаления — тоже. Самый неприятный — произвольное перемещение — но все в пределах арифметики. Правильность реализации нужно контролировать ну никак не ключами.
Реальную проблему видел один раз — когда такое дерево положили в MyISAM :-)
Алгоритм вставки тривиален, удаления — тоже. Самый неприятный — произвольное перемещение — но все в пределах арифметики. Правильность реализации нужно контролировать ну никак не ключами.
Реальную проблему видел один раз — когда такое дерево положили в 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
в Nested Sets запросить только детей первого уровня, а не всё поддерево?
Добавить поле generation.
Integrity нет. А для какой цели она вам понадобилась?
<удалено>
В таблицу отношений добавьте ещё поле is_deleted (bool), чтобы физически не удалять отношения и не фрагментировать тем самым таблицу. Ускоряет перемещение пользователем туда-обратно свои записи (например пункты меню).
НЛО прилетело и опубликовало эту надпись здесь
Почему мне кажется что запись:
ancestor — 12
descendant — 12
при вставке не нужна? Ну или не должна быть нужна… костыль какой-то(страница является предком для себя и потомком для себя).
ancestor — 12
descendant — 12
при вставке не нужна? Ну или не должна быть нужна… костыль какой-то(страница является предком для себя и потомком для себя).
А еще тут можно не удалять данные, а удалять только связи. Так быстрее. А данные не имеющие связей чистить по крону ночью :) Также это возможность вернуть ошибочно удаленные данные — их надо просто перепривязат
Если в pages_treepath добавить уровень вложенности, и с уровнем вложености -1 указывать полный путь от корня — то все стандартные запросы к базе данных будут полностью ложится в индэксы. Собственно говоря именно так и делал в конце 90х.
Спасибо за пост, познавательно. Если позволите, хотел предложить разделить запрос:
на два: отдельно выборка и далее вставка.
Я понимаю, что планируется используются запросы по индексам и так далее, но все же лучше перестраховаться. Данная связка может вызвать продолжительную блокировку pages_treepath, что может окажазать ощутимое влияние на производительность. Одна из статей про это на Percona
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 т.к. перестройка дерева вверх и невозможность обеспечения целостности это зло) но чтобы он был реализован средствами СУБД. Поэтому пока все как Вы и сказали :(
У меня превращение плоского списка с записями дерева в «настоящее» дерево программно решено: после выборки происходит превращение.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Хранение деревьев в базе данных. Часть первая, теоретическая