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