What are the known ways to store a tree structure in a relational DB?

Question

There is the "put a FK to your parent" method, i.e. each records points to it's parent.
Which is a hard for read actions but very easy to maintain.

And then there is a "directory structure key" method:

0001.0000.0000.0000 main branch 1
0001.0001.0000.0000 child of main branch one
etc

Which is super easy to read, but hard to maintain.
What are the other ways and their cons/pros?

Answer 1

As always: there is no best solution. Each solution makes different things easier or harder. The right solution for you depends on which operation you will do most.

Naive Approach with parent-id:

Pros:

• easy to implement

• easy to move a big subtree to another parent

• insert is cheap

• Needed Fields directly accessible in SQL

Cons:

• retrieving a whole tree is recursive and therefore expensive

• finding all parents is expensive too ( SQL doesn't know recursions... )

Modified Preorder Tree Traversal ( saving a start- & end-point) :

Pros:

• Retrieving a whole tree is easy and cheap

• Finding all parents is cheap

• Needed Fields directly accessible in SQL

• Bonus: you're saving the order of childnodes within its parentnode too

Cons:

• Inserting / Updating can be very expensive, as you'll maybe have to update a lot of nodes

Saving a path in each Node:

Pros:

• Finding all parents is cheap

• Retrieving a whole tree is cheap

• Inserting is cheap

Cons:

• Moving a whole tree is expensive

• Depending on the way you save the path, you won't be able to work with it directly in SQL, so you'll always need to fetch & parse it, if you want to change it.

I'd prefer one of the last two, depending on how often the data changes.

See also: http://media.pragprog.com/titles/bksqla/trees.pdf