Каковы известные способы хранения древовидной структуры в реляционной БД?

Ответ 1

Как всегда: лучшего решения нет. Каждое решение делает разные вещи проще или сложнее. Правильное решение для вас зависит от того, какую операцию вы будете делать больше всего.

Наивный подход с parent-id:

Плюсы:

• легко реализовать

• легко перемещать большое поддерево в другой родительский

• Вставить дешево

• Необходимые поля, напрямую доступные в SQL

Минусы:

• Получение целого дерева рекурсивно и поэтому дорого

• найти всех родителей тоже дорого (SQL не знает рекурсии...)

Измененный обход дерева предзаказов (сохранение начальной и конечной точки):

Плюсы:

• Получение всего дерева легко и дешево

• Поиск всех родителей дешев

• Необходимые поля, напрямую доступные в SQL

• Бонус: вы также сохраняете порядок дочерних элементов в своем родительском классе

Минусы:

• Вставка/обновление может быть очень дорогостоящим, так как вам, возможно, придется обновлять множество узлов.

Сохранение пути в каждом Node:

Плюсы:

• Поиск всех родителей дешев

• Извлечение всего дерева дешево

• Вставка дешевая

Минусы:

• Перемещение цельного дерева дорого

• В зависимости от того, как вы сохраняете путь, вы не сможете работать с ним непосредственно в SQL, поэтому вам всегда нужно извлекать и анализировать его, если вы хотите его изменить.

Я бы предпочел один из двух последних, в зависимости от того, как часто изменяются данные.

Смотрите также: http://media.pragprog.com/titles/bksqla/trees.pdf

Ответ 2

Измененный обход дерева порядка

Раздел 2 статьи Sitepoint Сохранение иерархических данных в базе данных

alt text http://sitepointstatic.com/graphics/sitepoint_numbering.gif

Ответ 3

Я бы сказал, что "золотой путь" для хранения иерархической структуры данных - это использование иерархической базы данных. Например, HDB. Это реляционная база данных, которая хорошо обрабатывает деревья. Если вам нужно что-то более мощное, LDAP может сделать для вас.

База данных SQL не подходит для этой абстрактной топологии.

Ответ 4

Мне не сложно построить древовидную структуру с реляционной базой данных.

Однако объектно-ориентированная база данных будет работать намного лучше для этой цели.

Использование объектно-ориентированной базы данных:

parent has a set of child1  
child1 has a set of child2  
child2 has a set of child3  
...  
...

В объектно-ориентированной базе данных вы можете легко создать эту структуру.

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

parent  
id  
name  

child1  
parent_fk  
id  
name 

child2  
parent_fk  
id  
name  

..

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

foreach(parent in parents){
   foreach(child1 in parent.child1s)
    foreach(child2 in child1.child2s)

...