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

As it currently stands, this question is not a good fit for our Q&A 开发者_StackOverflow中文版format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 10 years ago.

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?

---

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

---

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.

---

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.

---

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)

...