PHP FAQ from PHPclub.ru : Tree / Ns Faq

Деревья в базах данных => Вложенные множества => Часто задаваемые вопросы

Часто задаваемые вопросы

Не могу понять, как устроен Nested Sets! Что мне делать?

popoff
Этот вопрос касается скорее не самих Nested Sets, а Вашего отношения к новому. Большинство людей уверены, что изучить новое им может помочь некая волшебная сила. Как в фильме «Матрица»: вставили дискетку с программой обучения пилота вертолета, пару секунд и готово. Теперь Вы умеете водить вертолеты.

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

Ответ на вопрос «Что мне делать?» такой: прочтите документацию и разберитесь в примерах.

Макс:
Нарисуй на бумаге дерево до перемещения узлов и после перемещения и найди закономерности в изменении левого и правого смещений (а они есть).

su1d
Чтобы понять, надо лишь один раз представить себе дерево и, начиная с корня, «обойти» его по «правилу правой руки», расставляя порядковый номер на каждом элементе при проходе мимо него в обоих направлениях. Проще уже, по-моему, не объяснишь.

Где можно найти описание Nested Sets?

Список ресурсов можно найти здесь:
Смотрите так же
su1d
Проще всего, по-моему, это описано в небольшом PDF'е на русском языке, который лежит у меня рядом со статьей Селко. Там показаны пронумерованные квадратики, и когда «идёшь» по возрастанию номеров, становится понятно как всё устроено.
http://dev.e-taller.net/dbtree/
Хранение древовидных структур в Базах данных
http://phpclub.ru/detail/article/db_tree

Когда нужно использовать Nested Sets? В чем его достоинства и недостатки?

Когда использовать Nested Sets? Правильно я понимаю, что Nested Sets предназначен для больших деревьев? Или всё зависит от того что мне от этого дерева надо, т.е какие наиболее частые запросы?

Макс
В Nested Sets еще уровень вложености для узла хранится и получается очень удобная структура для работы с деревьями. Например для организации структуры категорий с «неограниченной» вложенностью. Например одним запросом можно получить список всех подкатегорий (любого уровня вложенности) для указаной категории. Также можно одним запросом получить список всех родительских категорий для указанной категории – очень удобно для генерации навигации, типа:
каталог >> категория >> подкатегория >> подподкатегория >> ...

popoff
Похоже, четкого ответа на этот вопрос пока нет. Хотя, можно порассуждать.

Вообще говоря, все зависит от того, что тебе от этого дерева надо.

Операции изменения (внесения, удаления, перемещения) на Nested Sets в чистом виде (не Nested Intervals) требуют пересчета значительной части дерева; на больших деревьях это будет несколько дольше, чем при использовании списков смежности. Да и процедуры внесения изменения не столь тривиальны, как в обычных списках смежности.

Если тебе часто нужно искать только непосредственных потомков или выбирать всех родителей для некоторого узла, то такие операции на Nested Sets программируются довольно легко, но во многих случаях на таких операциях при обращении к таблице не будут использоваться индексы; они используются, как известно, если условие where покрывает не слишком большую часть таблицы (раньше это было 30%, сейчас эта цифра меняется в зависимости от разных параметров), при выборке детей и особенно при выборке родителей условие в where запросто может покрыть значительную часть таблицы. При выборке непосредственных детей, их количество обычно значительно меньше общего числа элементов дерева, но при использовании Nested Sets индекс все равно скорее всего использоваться не будет, потому что у этих детей могут быть еще свои дети, и общее количество потомков (не только непосредственных) для данной вершины может оказаться значительным.

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

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

Nested Sets так же хорошо использовать, если основная операция для работы с деревом – это не выборка детей/родителей, а проверка: является зли заданная вершина родителем/ребенком некоторой другой заданной вершины. Если хорошо продумать схему обработки данных, то многие задачи, в которых раньше требовалась выборка из таблицы, можно свести к такой проверке.

Так что, на мой взгляд, использовать ли Nested Sets – это дело, скорее всего, вкуса. В чем-то они лучше, в чем-то быстрее, а в чем-то дольше. Лично я их использую, потому что я к ним привык и у меня есть собственная библиотека функций для работы с такими деревьями. Хотя, видимо, эту библиотеку нужно доработать, что бы она могла работать с деревьями, хранищимися разными способами.

Смотрите так же:
How MySQL Optimizes WHERE Clauses

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

Кром
А можно поподробней о «несоизмеримо высоких удобствах»? С примерами и статистическими выкладками, если есть.

Эти проблемы решаются в один запрос. Разве нужны тут какие-то статистические выкладки?

Кром
Да, нужны. Потому что те результаты тестирований, которые я видел, меня не особенно впечатлили.

По правде говоря, я, собственно, глубоко не забирался.

popoff
Вот с этого и нужно начинать. Сначала разберитесь, и только потом говорите слово «самый» (хороший/плохой, (не)удобный, быстрый/тормознутый).

Смотрите так же:
Как выбрать самый подходящий способ хранения деревьев в моем проекте?

Результаты тестирований можно найти здесь:
http://dev.e-taller.net/dbtree/

Если элементы находятся на одном уровне, для того, что бы поменять их местами, разве нельзя просто поменять местами их значения right и left?

su1d
Cвап сделать можно, конечно, но опять же не вижу выгоды от этого в общем случае: допустим, что ты расположил красиво элементы, отсортировав их по названию, но потом тебе понадобилось сделать то же самое по дате создания – траблы.

popoff
Свап сделать нельзя в случае, если у этих вершин есть потомки. Если Вы не понимаете, к чему это приведет, то результат будет довольно странным. Если количество потомков у этих вершин разное, то нарушится целостность дерева.

Как можно перемещать элементы дерева вверх-вниз на одном уровне?

JVN
Вверх-вниз – это уже не на одном уровне.

Как сортировать элементы дерева?

Может, нужно добавить в дерево еще одно поле, по которому будет производиться сортировка?

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

$i_id – идентификатор родительской вершины в дереве. Следующий запрос выведет всех непосредственных детей этой вершины, отсортировав их по названию:

##SELECT

t_catalog.i_id,
t_catalog.s_name

FROM

t_tree as t1,
t_tree as t2,
t_catalog

WHERE

t1.i_id=".$i_id." and
t2.i_left between t1.i_left+1 and t1.i_right-1 and
t2.i_level = t1.i_level+1 and
t2.i_id=t_catalog.i_id

ORDER BY

t_catalog.s_name##

Зачем что-то где-то в другой таблице хранить, дополнительное поле, если уже есть поле cat_left, по которому все прекрасно можно сортировать? Мне кажется, это очень полезная фичечка. ИМХО здорово без всяких дополнительных полей менять порядок следования в дереве.

JVN
Не получится у тебя все хранить в одной таблице-дереве. Очень медленно это будет работать. В любом случае будет родительская таблица, в которой сами данные храняться. Отсортировать данные при выборке значительно быстрее и проще чем сортировать само дерево в таблице.

popoff
Следует понимать, что есть два типа данных: 1) дерево, 2) информация. Дерево – это собственно структура, которая указывает, какие элементы являются дочерними по отношению к каким (будем называть это родством). Информация всегда остается одной и той же, она не зависит от того, каким именно способом Вы будете указывать родство, толи Вы будете использовать для этого Nested Sets, толи Вы используете какой-либо другой способ.

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

При использовании Nested Sets следует различать два варианта сортировки элементов дерева:

сортировка с учетом структуры, указывающей родство элементов.

Очень удобно, если порядок следования элементов в уровне задается единожды администратором или другим пользователем. Причем администратор говорит, что «этот элемент следует после этого, а тот – после того». Администратор НЕ говорит «элементы сортируются в алфавитном (или в любом другом, зависящем от каких-то значений) порядке».

Если порядок следования элементов в дереве задается какими-то полем, например «отсортировать по алфавиту», то использовать этот способ сортировки не выгодно – лучше сортировать при выборке, не трогая при этом само дерево.

Если Вы хотите автоматически отсортировать дерево по значению в какому-либо поле, то использование этого способа крайне не оправдано. Для того, что бы сделать одно перемещение в дереве, требутся пересчитать в среднем половину вершин дерева. Если Вы будете сортировать методом быстрой сортировки, то Вам придется пересчитывать значительную часть дерева n*log2(n) раз. То есть для дерева в 1000 вершин Вам нужно будет совершить около 10000 перемещений. Один раз переместить вершину в дереве – это долго. Сделать 10000 перемещений – это оооооочень долго.

У этого способа сортировки есть еще один очень важный недостаток – он зависит от выбранного Вами способа хранения дерева. Если Вы захотите использовать другой способ хранения деревьев, не Nested Sets, то этот способ сортировки Вам уже может не подойти.

сортировка без учета структуры, указывающей родство элементов.

Это тот самый способ, который в предыдущем ответе предложил JVN. Он не зависит от способа хранения дерева, в нем легко можно задавать сортировку по разным полям (например, сейчас сортируем по алфавиту, а потом – по стоимости).

Я рекомендовал бы использовать этот способ всегда, даже когда порядок задается единожды администратором и не зависит от значений в каких-либо полях (в таком случае добавляется специальное служебное поле, в котором этот порядок указывается). Это значительно упростит процедуру изменения способа хранения дерева в Вашем проекте. Используйте сортировку с учетом структуры дерева только в случае, если Вы твердо уверены в том, что способ хранения деревьев никогда не изменится.

При при использовании Nested Sets из-за сортировки на уровне все летит в трубу!

Лучше чем Nested Sets я ничего не встречал. Но из-за сортировки на уровне все летит в трубу!

popoff
Ну почему же. Отличительной особенностью Nested Sets по сравнению с Adjacency List как раз является то, что в самом дереве можно (именно *можно*, а не «только так и возможно») задавать порядок следования узлов в пределах уровня; в Adjacency List для этого нужно было бы вводить дополнительное поле. Но пользоваться этой возможностью совсем не обязательно: пожалуйста, можно сортировать в любом удобном порядке.

Другое дело, если Вы хотите выбрать одним запросом не один уровень, а сразу все дерево или отдельную его ветку и отсортировать его при этом не в такой последовательности, как это задано в структуре дерева. Но это уже совсем другая задача. Она, как правило, не решается одним запросом. Она не решается одним запросом не только в Nested Sets, но и в Adjacency List и во всех других способах.

В Nested Sets есть возможность по крайней мере выбрать все дерево, расположив узлы в порядке, заданном самой структурой дерева. В Adjacency List даже этого нельзя.

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

Смотрите так же: Как выбрать самый подходящий способ хранения деревьев в моем проекте?.

Для чего нужно использовать транзакции при обновлении дерева?

popoff
Для того, что бы понять ответ на этот вопрос, Вам следует разобраться в двух вещах:

какие операции нужно выполнять для обновления дерева?
Для поиска ответа на этот вопрос смотрите сюда:
Не могу понять, как устроен Nested Sets! Что мне делать?
Где можно найти описание Nested Sets?
для чего нужны транзакции?
Для поиска ответа на этот вопрос смотрите документацию по My SQL?:
http://dev.mysql.com/doc/mysql/en/ansi-diff-transactions.html

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

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

vladax
У меня проблема была в том, что вклинивались другие потоки. На моем хостинге более старая версия My SQL? без поддержки транзакций, поэтому мне пришлось блокировать таблицы от других потоков.

Для чего в дереве дополнительно хранится уровень вложенности?

Хранить уровень вложенности необязательно – это избыточная информация.

su1d
Именно! Избыточная. Эта избыточность ускоряет выборку всех потомков элемента на одном уровне.

А есть какие-нибудь данные о том, какой выигрыш дает эта избыточность?

su1d
Выигрыш – реализация получения всех потомков элемента одним простым запросом без джойнов, вместо запроса с несколькими джойнами таблицы на саму себя, чтобы узнать уровень элемента. Проигрыш – размер поля INT, умноженный на число записей (общий объем этой избыточной информации) – это не слишком много.

PHP FAQ from PHPclub.ru: Tree/NsFaq ...