 |
|
Когда нужно использовать 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/