What are models for storing tree structures and what are their characteristics?

Question

So far I have encountered adjacency list, nested sets and nested intervals as models for storing tree structures in a database. I know these well enough and have migrated trees from one to another.

What are other popular models? What are their characteristics? What are good resources (books, web, etc) on this topic?

I'm not only looking for db storage but would like to expand my knowledge on trees in general. For example, I understand that nested sets/intervals are especially favorable for relational database storage and have asked myself, are they actually a bad choice in other contexts?

Answer 1

The seminal resource for this are chapters 28-30 of SQL for Smarties.

(I've recommended this book so much I figure Celko owes me royalties by now!)

Answer 2

A variation is where you use a direct hierarchical representation (ie. parent link in node), but also store a path value.

ie. for a directory tree consisting of the following:

C:\
   Temp
   Windows
       System32

You would have the following nodes

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

Path is indexed, and will allow you to quickly do a query that picks up a node and all its children, without having to manipulate ranges.

ie. to find C:\Temp and all its children:

WHERE Path LIKE '*1*2*%'

This representation is the only place I can think of where storing id's in a string like this is ok.

Answer 3

@lassevk: This article talks about your approach in more detail and provides code snippets.

Hope this helps.