Что такое модели для хранения древовидных структур и каковы их характеристики?

Question

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

Какие другие популярные модели? Каковы их характеристики? Какие хорошие ресурсы (книги, интернет и т. Д.) По этой теме?

Я не только ищу хранилище БД, но и хотел бы расширить свои знания о деревьях в целом. Например, я понимаю, что вложенные наборы / интервалы особенно благоприятны для хранения реляционных баз данных, и я спросил себя, действительно ли они плохой выбор в других контекстах?

Answer 1

В этом варианте вы используете прямое иерархическое представление (т. Е. Родительскую ссылку в узле), но также сохраняете значение пути.

т. для дерева каталогов, состоящего из следующего:

C:\
   Temp
   Windows
       System32

У вас будут следующие узлы

Key     Name     Parent     Path
1       C:                  *1*
2       Temp       1        *1*2*
3       Windows    1        *1*3*
4       System32   3        *1*3*4*

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

т. найти C: \ Temp и все его дочерние элементы:

WHERE Path LIKE '*1*2*%'

Это представление - единственное место, где я могу думать о том, где можно хранить id в такой строке, как это нормально.

Answer 2

Основным ресурсом для этого являются главы 28-30 SQL для умных .

(я так рекомендовал эту книгу, что, по моему мнению, Celko уже должен мне гонорары!)

Answer 3

@ lassevk: В этой статье более подробно рассказывается о вашем подходе и предоставляются фрагменты кода.

Надеюсь, это поможет.