Welcome to php club

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


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



Для чего нужно хранить отдельно – дерево, отдельно – информацию?

popoff


Потому что если данные хранятся отдельно, то:


  • данные не зависят от способа хранения деревьев. Если Вы захотите изменить способ хранения деревьев, то Вам нужно будет изменить ТОЛЬКО способ хранения деревьев и не трогать сами данные.
  • быстрее выполняются операции поиска элементов в дереве (выборка родительских, дочерних элементов). Об этом сказано в документации:
    http://dev.mysql.com/doc/mysql/en/data-size.html
    Вероятно, на операции обновления дерева (добавление, удаление, перемещение) это тоже влияет.
  • Rin: на ветки дерева можно «повесить» много разных таблиц с различными данными и структурой.

Как распределять информацию между таблицами при использовании деревьев?

Ну, с каталогами все понятно: отдельная таблица – дерево, отдельно – информация о каталоге. А вот как быть с простыми страницами? Допустим в одном из каталогов должен быть список документов. Один и тот же документ может быть расположен одновременно в нескольких каталогах. Как быть в таком случае?


vladax (Отредактировано popoff)
Насколько я понимаю, тебе в разделы (папки) надо класть документы (файлы). Смысл в том, что не надо мешать всё в кучу. В отдельной таблице следует хранить информацию о каталоге (списке папок), и в отдельной таблице – информация о документах (файлах). А в третьей таблице следует хранить информацию о том, какие файлы в каких папках содержатся.


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



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

popoff


1. Списки смежности (AL)
+: выборка всех непосредственных детей для заданной вершины – очень быстро
-: выборка всех детей для заданной вершины (всего поддерева) – долго
-: выборка всех родителей для заданной вершины (определение пути) – долго
-: определить размер поддерева – долго
-: порядок элементов в уровне не может храниться в структуре дерева
-: проверка, является ли одна вершина дочерней по отношению к другой – долго, если вершины не являются непосредственными родственниками
+: добавление новых элементов в дерево – быстро
-: удаление ветки дерева – долго
+: перемещение веток дерева – быстро
+: количество узлов в дереве – не ограничено
?: устойчивость к ошибкам – средняя (если «исчезает» какой-то элемент, то исчезает только соответствущее поддерево)
+: понимание – легко


2. Вложенные множества (NS)
?: выборка всех непосредственных детей для заданной вершины – выполняется одним запросом, но долго (без использования индексов) в случае, если этой вершине соответствует поддерево значительных размеров.
+: выборка всех детей для заданной вершины (всего поддерева) – быстро
?: выборка всех родителей для заданной вершины (определение пути) – выполняется одним запросом, но часто без использования индексов (долго).
+: определить размер поддерева – очень быстро
+: структура дерева позволяет задавать порядок элементов в уровне
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро
-: добавление новых элементов в дерево – долго
+: удаление ветки дерева – быстро
-: перемещение веток дерева – долго
+: количество узлов в дереве – не ограничено
-: устойчивость к ошибкам – низкая (если «исчезает» какой-то элемент, то все дерево становится неправильным)
?: понимание – разобраться в операциях выборки – просто, в операциях модификации – сложно


3. Вложенные интервалы (NI)
?: выборка всех непосредственных детей для заданной вершины – выполняется одним запросом, но долго (без использования индексов) в случае, если этой вершине соответствует поддерево значительных размеров.
+: выборка всех детей для заданной вершины (всего поддерева) – быстро
?: выборка всех родителей для заданной вершины (определение пути) – выполняется одним запросом, но часто без использования индексов (долго)
?: определить размер поддерева – дольше, чем у вложенных множеств, но быстрее чем у списков смежности
+: структура дерева позволяет задавать порядок элементов в уровне
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро
?: добавление новых элементов в дерево – быстро, если есть свободное место. Если свободного места нет, то дольше, чем у списков смежности, но быстрее, чем у вложенных множеств.
+: удаление ветки дерева – быстро
-: перемещение веток дерева – долго, дольше чем у вложенных множеств. Но если есть достаточное свободное место – быстрее, чем у вложенных множеств.
?: количество узлов в дереве – не ограничено, но при большом количестве остается мало свободного места.
-: устойчивость к ошибкам – низкая (если «исчезает» какой-то элемент, то все дерево становится неправильным)
?: понимание – разобраться в операциях выборки – просто, в операциях модификации – сложно, намного сложнее, чем для вложенных множеств


4. Материализованные пути с использованием строк (MS)
?: выборка всех непосредственных детей для заданной вершины – выполняется одним запросом, но с использованием поиска по длинному строковому индексу (level)
?: выборка всех детей для заданной вершины (всего поддерева) – выполняется одним запросом, но с использованием поиска по длинному строковому индексу (tree)
+: выборка всех родителей для заданной вершины (определение пути) – очень быстро (path)
?: определить размер поддерева – выполняется одним запросом, но с использованием поиска по длинному строковому индексу (stree)
-: порядок элементов в уровне не может храниться в структуре дерева (хотя над этим можно подумать) (order)
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро (parent)
+: добавление новых элементов в дерево – очень быстро (insert)
+: удаление ветки дерева – быстро, но дольше чем у вложенных множеств за счет использования индекса по строковому полю (remove)
?: перемещение веток дерева – быстрее, чем у вложенных множеств, но дольше, чем у списков смежности (move)
+: количество узлов в дереве – не ограничено (size)
+: устойчивость к ошибкам – высокая (если «исчезает» вершина, то дерево остается все равно правильным) (error)
+: понимание – разобраться в операциях выборки – просто, в операциях модификации – относительно просто (unders)


5. Материализованные пути (by Tropashko: рациональные дроби, последовательности Farey, фракталы; сильно обобщено) (MT)
?: выборка всех непосредственных детей для заданной вершины – не ясно (level)
?: выборка всех детей для заданной вершины (всего поддерева) – не ясно (tree)
+: выборка всех родителей для заданной вершины (определение пути) – очень быстро (path)
?: определить размер поддерева – не ясно (stree)
+: структура дерева позволяет задавать порядок элементов в уровне (order)
+: проверка, является ли одна вершина дочерней по отношению к другой – очень быстро (parent)
?: добавление новых элементов в дерево – не ясно, (insert)
?: удаление ветки дерева – не ясно (remove)
?: перемещение веток дерева – не ясно (move)
-: количество узлов в дереве – очень сильно ограничено (size)
?: устойчивость к ошибкам – не ясно (в общем случае вершины в дереве не зависимы, но алгоритмы, использующие этот способ хранения дерева, могут налагать некоторые ограничения, влияющие на устойчивость к ошибкам) (error)
-: понимание – очень сложно (unders)


Построим таблицу:

AL NS NI MS MT
level +
tree + +
path
+ +
stree +
order + + +
parent + + + +
insert +
+
remove + + +
move +
size + +
+
error
+
unders +
+

su1d
Когда ты хранишь лишь ссылку на родителя, то получить одним запросом весь путь от элемента дерева к вершине не получится. Надо делать рекурсию. Если же у тебя хранится обход дерева, то всё получается легко, просто и, что немаловажно, быстро. Минус второго подхода в том, что при добавлении/удалении записи, надо пересчитывать часть дерева, но на вебе кол-во обращений на чтение дерева намного больше его изменений, так что такое решение видится более удобным.


На чтении и поиске быстрее вложенные множества быстрее, чем Списки смежности и Материализованные пути со строками, на изменении каталога (добавление/удаление/перемещение) неслабо проигрывает Спискам смежности, но на вебе обычно поиск чего-то посетителем производится намного чаще, чем изменение каталога админом, поэтому всё получается как надо.


Я не хочу и не берусь утверждать, что Nested Sets в общем случае лучше, чем Adjacency List. У каждого способа свои плюсы, у каждого свои минусы. Я использую как тот, так и другой, но чаще всего – вложенные множества. Это – лишь моё личное предпочтение, и вовсе не обязательно оно должно стать чьим-то ещё.


Недостаток метода, предложенного Tropashko (Материализованные пути), в том, что слишком быстро кончается integer. В первом предложенном способе знаменатель возрастает со степенью двойки, что позволяет иметь не более 16 (32) уровней вложенности. Второй способ – последовательности Фейри уже получше, и у самого Тропашко даже получилось создать дерево на 1М узлов. Однако, он пошёл дальше и предложил кодировать дерево через преобразования Мёбиуса, что вроде как уже имеет право на жизнь, хотя даже там числа растут как последовательность Фибоначчи, что тоже налагает существенные ограничения на количество узлов в дереве. Воложенные множества ещё самые добрые, поскольку там зависимость возрастает лишь как 2n.


Cамой пригодной, единственно бесконечной моделью «для всего», похоже, так до сих пор и является лишь Adjacency List. Все остальные методы так или иначе накладывают ограничения на максимальное количество узлов в дереве. На малых объёмах данных и Вложенные Множества очень хороши и удобны. Интерес как раз в том, чтобы найти модель, не сильно ограничивающую объёмы, но и предоставляющую более удобный механизм доступа к записям, чем это делается с Adjacency List.


Смотрите так же:
Когда нужно использовать Nested Sets? В чем его достоинства и недостатки?
При при использовании Nested Sets из-за сортировки на уровне все летит в трубу!


demiurg: SQL Trees
http://www.livejournal.com/users/demiurg/53125.html


 
Комментариев нет. [Показать комментарии/форму]