Code Tips and Snippets


Not yet member?
Click here to register.
Only members can post comments
Fast database stored tree traversal
Posted by pk on Sunday, September 14 2014 - 15:23:22
5 stars levelphp languageMySQL

The simplest way to store a tree structure into a database is obviously the table structure in which each record represents a node, and where a column is used to specify the key of the parent node.

This is by far the most convenient way for tree operation handling (insert, delete a node, etc.).
The tree traversal is very easy and is done with a simple recursive micro-function.

The downside to this advantage (and yes, it is well known: each advantage  generates 1 or n disadvantages.)
lies in the fact that the recursive traversal requires the processing of an SQL query on each function call.

Fortunately, there is an enhanced database structure that allows fast tree traversal:
A single SQL query does the job!

The downside to this advantage (and yes, it is well known: each advantage  generates 1 or n disadvantages.)
lies in the fact that a single update of the tree requires a total re-computing of the structure.

This structure will be particularly suitable when updates are infrequent and access must be done very quickly.

  • very appropriate: web site tree structure (we hope that there is more consulting than structure updates).
  • inappropriate:  forum. (I hope you will understand why ...)

The name of this structure is Modified Preorder Tree Traversal .

I'm not going to reinvent the wheel.
Please use your favorite internet search engine to find a lot of literature on this topic.

I can mention Storing Hierarchical Data in a Database that addresses particularly well the issue.

yakpro rulez!

Site has been updated on Thursday, May 25 2017 - 09:16:27