What are the known ways to store a tree structure in a relational DB?
MysqlDesign PatternsTreeRelational DatabaseMysql Problem Overview
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?
Mysql Solutions
Solution 1 - Mysql
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.
Solution 2 - Mysql
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 - Mysql
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.
Solution 4 - Mysql
I don't think it's hard to build a tree structure with a relational database.
However, an object oriented database would work much better for this purpose.
Using an object oriented database:
parent has a set of child1
child1 has a set of child2
child2 has a set of child3
...
...
In an object oriented database you can build this structure pretty easily.
In a relational database, you will have to maintain foreign keys to parent.
parent
id
name
child1
parent_fk
id
name
child2
parent_fk
id
name
..
Essentially, while you are building your tree structure you will have to join all these tables, or you can iterate through them.
foreach(parent in parents){
foreach(child1 in parent.child1s)
foreach(child2 in child1.child2s)
...