Nested sets

Category:Database

Nested Sets - Working with hierarchical data trees

One of the most commonly used methods of representing trees of data within a database is the adjacency list model, where each record has a column dedicated to identifying the 'parent' record for this particular row of data. Using the parent identifier it becomes possible to work your way up from any node in the tree back to the uppermost parent or ancestor (also commonly referred to as the root node). In this way, you can recurse through the tree data and build up programmatically an array structure representing the tree.

However, this recursion business is somewhat expensive in terms of processor cycle consumption.

Enter then, an appropriate alternative method for handling tree data suited to situations where the tree needs to be read much more often than it needs to be changed or modified.

Nested sets, or the modified preorder inverse tree traversal

The nested sets approach involves giving each node of the tree two integer references, one on its left hand side and the other on its right hand side. The left hand side of the root node is always '1'. The rest of the tree is numbered by travelling down the left hand side and up the right hand side of every node until you get back to the right hand side of the root node, where the number used will be exactly twice the number of nodes in the tree. Please see the reference articles for further information on this.

Nested_sets_model.php

This is the heart of the machine; the model class that actually does the reading, writing and manipulation of the tree. It is not intended to be used directly by your controllers, rather to be extended by another model class that you write in order to give it the "character" required. In this sense, it really ought to be an abstract class, which is how I wrote it in the first place before remembering that PHP4.x doesn't support abstract classes. Consequently, I've rewritten it a little to make it compatible with PHP4.x installations. PHP5 users can use it as it is, a concrete class, or mod it back to being an abstract class as they see fit.

This base class is extended in the usual fashion:

class Categories_model extends Nested_sets_model 
{
        function Categories_model() {
               parent::Model();
        }
}

The extending class should provide the properties for the table name to use, as well as identifying the column names of the left value, the right value and the primary key (where appropriate).

Categories_demo files

Also included in the package are files to provide a demo, using the notion of categories and subcategories for our data tree. Included is a controller, a model and a view, which can be dropped into the relevant locations to enable the demo. This also illustrates how the Nested_sets_model base class is extended for use within the application.

Download the package

You can download a ZIP file containing the Nested_sets_model.php model class file, the Categories_demo files, a sample .sql file with demo data, a README and an INSTALL file here:

File:CI_Nested_Sets-0_9.zip

Discussion

I've started a forum topic for this package to help with providing feedback, criticism, bug reports etc. The thread can be found here:

http://codeigniter.com/forums/viewthread/47671/

Adjacency List Emulation

It's been mentioned a few times on the forum, so here are some sample queries to help emulate retrieving parent node data 'adjacency list' style (parentid, parentname etc). These queries use the included category_demo data to illustrate the technique. Naturally, you'll need to modify them to suit your own implementation / database schema

Select parentid and parentname for each row in the tree

SELECT     cat.categoryname       AS name,
           cat.categoryid,
           parent.categoryname  AS parentname,
           parent.categoryid        AS parentid

FROM       categories_demo    AS cat

           LEFT JOIN categories_demo AS parent
           ON parent.leftval = (
                SELECT           MAX(rel.leftval)
                FROM             categories_demo AS rel
                WHERE            rel.leftval < cat.leftval AND rel.rightval > cat.rightval
            )

ORDER BY cat.leftval ASC;

Get the level (depth) of each node

SELECT     cat.categoryname,
           cat.categoryid,
          (COUNT(parent.categoryname) - 1) AS depth
FROM       categories_demo AS cat,
           categories_demo AS parent
WHERE      cat.leftval BETWEEN parent.leftval AND parent.rightval
GROUP BY   cat.categoryid
ORDER BY   cat.leftval;

Errata

PHP4.x users will need to modify the private function declarations at the bottom of Nested_sets_model.php by removing the "private" keyword.

e.g.

private function _setNewNode() 
{
     ...
}

should become

function _setNewNode()
{
    ...
}

Further Reading

Excellent article on MySQL.com

Credits

Author: thunder Sources: Joe Celko, Rolf Brugger

References

DBMS Online magazine: Joe Celko article Sitepoint article: Hierarchical Data in a Database Nested Set trees