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

Solution 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.

Closure table

Pros:

  • Easy to implement

  • Finding all parents is cheap

  • Inserting is cheap

  • Retrieving whole trees is cheap

Cons:

  • Needs an additional table

  • Takes up a lot of space compared to other approaches

  • Moving a subtree is expensive

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

Solution 2:

Modified Preorder Tree Traversal

This is a method which uses a non-recursive function (usually a single line of SQL) to retrieve trees from the database, at the cost of being a little trickier to update.

Diagram showing numbered hierarchical tree**

Section 2 of the Sitepoint article Storing Hierarchical Data in a Database for more detail.

Solution 3:

I'd say the "golden way" to store a hierarchical data structure is to use a hierarchical database. Such as, for instance, HDB. That's a relational database that handles trees quite well. If you want something more powerful, LDAP might do for you.

A SQL database is ill-suited to this abstract topology.