Storing hierarchical data in a database Part 2a: Modified preorder tree traversal

Second part in this series of discussions/tutorials on storing hierarchical data in a database. You can read the first on here. The original article I read that got me started on these ideas can be found here (you’ll notice the tree diagrams are similar). Most credit should be given to Gijs Van Tulder; I simply modified some of his code and added to his explanation where appropriate.

This time we’re going to take a look at the basics of the modified preordered tree traversal algorithm.

Consider the tree used in part 1, which uses the adjacency list model:

[table: animal_tree, adjacency list model]
| id  | parent_id   | name
|-----+-------------+-------------
| 1   |  0          | Animals
| 2   |  1          | Fish
| 3   |  1          | Mammals
| 4   |  2          | Marine
| 5   |  2          | Fresh Water
| 6   |  4          | Halibut
| 7   |  5          | Rainbow Trout
| 8   |  3          | Dog
| 9   |  3          | Cat
|-----+-------------+-------------

What the modified preordered method does is store the relationships between neighboring nodes in order to recreate the tree structure. We do this by storing “lft” and “rght” (“left” and “right” are reserved SQL keywords) values at each node; as you descend a tree, the left-hand values increase, and likewise, as you ascend the right-hand values increase. It’s hard to visualize until you see it in action:

tree_diag_image-lr_arrow.gif

Pay special attention to the sequence in which these nodes are ordered, as shown by the arrows.

Here’s the presorted table for the above tree:

[table: animal_tree, presorted model]
| lft | rght        | name
|-----+-------------+-------------
| 1   |  18         | Animals
| 2   |  11         | Fish
| 12  |  17         | Mammals
| 3   |  6          | Marine
| 7   |  10         | Fresh Water
| 4   |  5          | Halibut
| 8   |  9          | Rainbow Trout
| 13  |  14         | Dog
| 15  |  16         | Cat
|-----+-------------+-------------

…and one of the first things you probably want to do with your new presorted data? Create a tree. First things first, though. The code behind it is more difficult to understand than the adjacency model but the overhead is greatly reduced because you only need two queries for to retrieve tree information from the database (adjacency uses a new query every time you recursively enter the retrieve function).

In its simplest form the queries are:
(retrieves the left and right values for the starting node)
SELECT lft,rght FROM animal_tree WHERE name="$name";
SELECT * FROM animal_tree WHERE lft BETWEEN $row['lft'] AND $row['right'] ORDER BY lft ASC;
…and that’s it.

Take a look at the code (modified from the example in the Sitepoint article):

//I use my own database classes, but it should be easy enough to follow what's happening.
function get_tree($name="Animal",&$DB) {

$result=$DB->query("SELECT lft,rght FROM animal_tree WHERE name=\"$name\"");
$row=$DB->fetchRow($result);
$result2=$DB->query("SELECT * FROM animal_tree WHERE lft BETWEEN {$row['lft']} AND {$row['rght']} ORDER BY lft ASC");

$right = array();

$row=$DB->fetchAssoc($result2);

$ii=0; //start counter at 0
foreach($row as $row) {
if(count($right)>0) {

/* $right[max#] is the last array element, which holds the
* rght value from the previous row, which is a parent in
* many cases, but if not a parent, it keeps popping-off
* the last element of the $right array - going back up
* the tree until $row[right] (current node) finds its
* parent (the parents rght value is greater than the
* child's rght)
*/
while($right[count($right)-1]$value)
{
print(str_repeat(' ',$value['indent'])."({$value['lft']})".$value['node']."({$value['right']})\n");
}
}

…and in-case you want the path to a particular node:
SELECT * FROM animal_tree WHERE lft$rght ORDER BY lft ASC

..to count the number of descendants: $d=(rght-lft-1)/2

Thanks, again to Gijs for the excellent tutorial. Next time we will explore some ways to modify and manipulate the tree.

About these ads

10 thoughts on “Storing hierarchical data in a database Part 2a: Modified preorder tree traversal

  1. Phil says:

    I have been working with the Modified Preorder Tree Traversal and have been having difficulties writing an efficient method for moving a node with its child nodes.

    I would be grateful if you could publish a method for doing this as my understading of the method is still not quite up to scratch.

  2. iamcam says:

    I’m actually pretty new to the MPTT (blogging as I learn it), but I’ve already figured-out a lot beyond the Sitepoint article.

    My next entry will dive a bit deeper where the Sitepoint article began getting shallow – namely in inserting nodes in specific places within the tree. I already pretty much figured-out conceptually how to move a node and its children, which is definitely another entry in and of itself. Here’s a hint: pull-out the node and its children from the DB into an array, delete those rows, do the appropriate math on the nodes to the right of the group, then at the insertion point, do some more math to make room for the node and children, INSERT into your DB the array you pulled out. Just make sure your math makes sense at each step and you should be fine.

    I’ll get the next entry up as soon as I can…

    • David says:

      Hello man!
      Im “having fun” with MPTT and now Im in the phase of need help. It seems to be easy to folow your way how to move all the node with its childs but not sure how to write it in to a PHP code. Im waiting your upcomming article about this. Would be very very helpful. Im quite new to comming be a good friend with PHP so this is the moment when I can not move. Thanks for reply about the time of your upcomming how-to.

      • Hey David,

        It’s been a while since I posted this article. I’ve left some tips in the comment above. I would suggest working it out on paper first. All the math involved is simple arithmetic – wherever you have the insertion, all the left/right values after get bumped up, deletions subtract. Whether you have children or sibling nodes will tell you how much. The only PHP you need to be concerned about is mapping the SQL data to an array, doing some math on the lft/rght values, then inserting. Pretty basic PHP stuff. I would suggest reading up in the PHP manual or other PHP tutorials first before trying to tackle this.

  3. [...] Last time I introduced the Modified preorder tree traversal algorithm as a method to store relationships between nodes. This time I’ll show you how nodes are inserted into the tree. Note that I’m using MySQL, so you may need to change your queries slightly depending on the DB you’re using. [...]

  4. Alan deLevie says:

    @Phil:
    I recently wrote about a (patented) method for storing hierarchical data in a database which does not require recursion for retrieving the tree as well as altering the tree. It is an improvement (in my opinion) over the path enumeration model.

    Here’s the link: http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/

  5. Alan,

    That third point is interesting and now doubt a fairly simple one to understand, however it seems to me somewhat impractical to use a method such as this when the total depth of the tree is unknown at any given point in the future. I think that is the downside of Chandler’s method – your tables could have an infinite number of columns, each of which are potentially filled with something. It is, however, easy on the eyes and simpler to understand than MPTT, though MPTT still reigns champ in my book.

  6. Manju says:

    How to insert rows into this table? I mean how to calculate the left and right values? Please let us know.
    Thanks,

  7. Hii, actually this is the method to get the tree but how can i store left-right values in the database. i am very much confused. how can the left and right values be automatically stored.?? please reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 399 other followers

%d bloggers like this: