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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

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* 

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

ie. найти C: \ Temp и все его дети:

WHERE Path LIKE '*1*2*%' 

Это представление единственное место, я могу думать о том, где хранить идентификаторов в строке, как это хорошо.

Answer 3

@lassevk: This article говорит о своем подходе более подробно и предоставляет фрагменты кода.

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