Nested sets
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.
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).
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.
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:
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/
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;
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()
{
...
}Excellent article on MySQL.com
Author: thunder Sources: Joe Celko, Rolf Brugger
DBMS Online magazine: Joe Celko article Sitepoint article: Hierarchical Data in a Database Nested Set trees