когда использовать nested sets?

[Sam]

когда использовать nested sets?

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

2. Если да, "большие" это сколько узлов?

 

[Popoff]

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

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

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

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

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

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

 

[Sam]

ого.. помедленнее, я записываю )

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

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

если мы храним просто parent_id и, допустим, level выборки первых детей, по-моему ещё проще, чем в nested sets

 

[vladax]

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

 

[Кром]

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

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

 

[vladax]

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

 

[Кром]

>разве нужны тут какие то статистические выкладки?

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

 

[vladax]

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

 

[Кром]

Я здесь смотрел:
http://dev.e-taller.net/dbtree/

 

[Popoff]

Автор оригинала: Кром
Я здесь смотрел:
http://dev.e-taller.net/dbtree/

От себя могу добавить примочку для перемещения нескольких веток дерева одним sql-запросом:
http://popoff.donetsk.ua/text/work/libs/mysql/tree/move.html
Может, кому будет интересно

 

[vladax]

Кром
Я не ожидал увидеть в этих тестах ничего другого. И так понятно, что действия, влекущие за собой пересчет (всех или части) индексов NS, потребуют времени. Зато выборка делается быстро и удобно. Увы, так не бывает, чтобы и рыбку съесть и на шишке поболтаться.