Tuesday, 3 March 2009

Fetching tree data with PHP from MySQL with only one query

Sometimes you may want to store some tree data in your database, for example navigation menus, where each of the "node" has children.

The most obvious way of fetching it would be of course to model the fetching algorithm similar to the nature of the data itself: recursively.

There is one problem with this method though, large trees will require dozens of queries, not to mention the storage in your client's runtime (eg. PHP).

Here is another method for describing tree data, which requires at most three queries to fetch just about anything you could fetch with hundreds if not thousands of recursive calls.

First, the structure of the database table would look like this

`id` int(10) unsigned NOT NULL auto_increment,
`order` int(10) unsigned NOT NULL COMMENT \'in which order to sort within the same parent\',
`indent` int(10) unsigned NOT NULL COMMENT \'the indentation level\',
`data` varchar(255) collate ascii_bin NOT NULL COMMENT \'a message to show\',
KEY `order` (`order`,`indent`)
The "order" column is there so you don't have to mess with the auto incrementing id column. It allows you to reorder the nodes individually.
The "indent" defines the "indentation" of the node - you may think of it denoting the node's deepness inside a tree.

The simplest code would then look like this:
$res = mysql_query('SELECT * FROM `'.TABLE_NAV.'` ORDER BY `order`,`indent`');
echo '<div style="border: 1px solid black"><pre>',PHP_EOL;
while($item = mysql_fetch_assoc($res)) {
echo str_repeat(' ',$item['indent']), $item['data'], PHP_EOL;
echo '</pre></div>',PHP_EOL;
I've added some indentation so you can get a feel for it.

You could also group the tree data into "navigation panes" by just adding a new column to it. Every node should then contain an id (not to be confounded with the id column, you just make up some common identifiers, a number would be the best) describing to which "navigation pane" that node belongs to.

The upside of this method is efficiency while fetching the data. The downside is you will need more work when deleting or reordering subtrees. That shouldn't be an issue for common cases, as you usually don't modify or delete the tree that often.

This organisatory model does not protect your data's consistency. For example, when reordering a node on it's own "indentation level", you will also need to reorder its children (to increment/decrement `order` by the same amount). The same goes for `indent`.

Here is a working PoC, just
  1. edit the "<edit me>" values in dbconf.php
  2. run install.php - no message should appear :-)
  3. view index.php
I hope you've found it useful and come back.

Note: the presented code is only a proof of concept, and there's much room for improvement. As such, I don't assume any responsability for any harms the code may do to your system. I do, however, assume the responsability for the concept itself.

1 comment:

  1. Interesting concept, it's pretty logical.
    I use a left_side/right_side method (read about it in a book somewhere) but I'll have to give this one a try.