A Lengthier Introduction to DB_NestedSet

A little more work, and a little more discussion with Daniel Khan finally has my tools for interacting with PEAR::DB_NestedSet complete. There’s a mistake in the documentation for the moveTree method that had me thrown for a while. Since it’s taken a while to get to grips with this module, I thought a summary of how I’ve used it might be in order.

Please note that this is a fairly hastily put together piece, which does not delve into all the intricacies of the package but should give an experienced PHP coder with a basic understanding of the theory behind nested sets with the information they need to get up and running. For some backgrounf on nested sets I’d recommend this article.

Configuration and Instantiation

To use the module with a database, you will need a table with (mostly integer) fields for at least:

Node ID
Node Parent
Left
Right
Order_Number
Level
Name (I use a varchar for this one)

and another field for category locks so that NestedSet can make changes withour worrying about simultaneous changes confusing matters. Mine has the following fields:

lockId (char(32))
lockTable (char(32))
lockStamp (int(11))

I’m initially using the module to represent a navigation menu so I also added a ‘url’ field to allow me flexibility in where each link points, and a ‘permissions’ field so I can determine which of my users can see a given node. I defined how my field names match the required ones my setting up an array:

$table_match = array(
	'id' => 'id',
	'parent' => 'rootid',
	'lft' => 'l',
	'rght' => 'r',
	'order_num' => 'norder',
	'level' => 'level',
	'name' => 'name'
);

The key for each array entry is the database field name I’ve used and the value assigned to it is the name the module prefers.

The one other value we need is the DSN for accessing our database. eg:

$dsn = 'mysql://user:password@host/database'

With all of those in place we can start up our object:

$nestedSet =& DB_NestedSet::factory('DB', $dsn, $table);

You also need to tell NestedSet which tables in the database it is using. Mine are called ‘categories’ and ‘cat_locks’, so I tell it to use those with:

$nestedSet->setAttr(array(
	'node_table' => 'categories',
	'lock_table' => 'cat_locks'
));

With all that in place, $nestedSet is ready for us to interact with.

Adding Nodes

NestedSet supports storing multiple ’trees’ within one database table, each of which can have its own root node. To create a root node we use the following method:

$parent = $nestedSet->createRootNode(array('name' => 'Home'), false, true);

This creates a root node with the name ‘home’ (we can set other attributes by including them in the array, and returns it as an object in $parent.

We can add sub-nodes with:

$subnode = $nestedSet->createSubNode($parent, array('name'  => 'Sub Node'));

This returns the sub-node as an object in $subnode. Adding further subnodes is as simple as repeating this method with $parent replaced with whichever object you want this node to be a child of. So to add another element which is a sibling of “Sub Node” we would use:

$siblingnode = $nestedSet->createSubNode($parent, array('name' => 'Sub Node Sibling'));

and to add a child of that node we could use:

$third = $nestedSet->createSubNode($siblingnode, array('name' => 'Level 3'));

NestedSet takes care of all the database access for you, so once you’ve made these calls there’s no need to worry about telling it to store your values.

Changing Node Properties

Once you have your nodes created, you may well want to add or change some of the information associated with them. In order to do that we can make use of the setAttr() method. Say we wanted to change the name of a node with id = 3:

$ournode = $nestedSet->pickNode(3);
	$changes = $nestedSet->setAttr(array('name' => 'A new name'));

Deleting Nodes

To delete a node, we want to make use, unsurprisingly, of the deleteNode() method. All the method requires is the numeric ID of the node that you want to delete. ie.

$delete = $nestedSet->deleteNode(2);

The method returns “true” if the node is successfully deleted, and “false” otherwise. Remember that deleting a node could “orphan” any “children” it might have had, so use with caution.

Moving/Copying Nodes

Rather than employ a moveNode() method to move single nodes, which if used wrongly could leave orphaned nodes all over the place, the developers of NestedSet have implemented the moveTree() method which allows you to copy or move a node and all of its children in one go.

moveTree() takes four arguments:

id of the node you want to move/copy
name of the “target” node
a constant defining how you want the new position to relate to that target node
optionally a boolean saying you want to copy rather than move the tree

The method offers three constants to describe how you want to make the move: NESE_MOVE_BEFORE, NESE_MOVE_AFTER, NESE_MOVE_BELOW

So in other words, if you want to move node number 4 (and any of its children) to be a child of node 2 you would use:

$move = $nestedSet->moveTree(4, 2, NESE_MOVE_BELOW);

If instead of moving it you wanted to copy, and instead of making it a child you wanted to make it a sibling coming next in order, you would use:

$copy = $nestedSet->moveTree(4, 2, NESE_MOVE_AFTER, 1);

Producing Output

Before we can produce output, we need to specify exactly which nodes we want to output. If we want all the nodes from all the trees in the database, we would use:

$data = $nestedSet->getAllNodes(true);

To retrieve all nodes within the tree that $id is a member of we would use:

$data = $nestedSet->getBranch($id, true);

And to get all the descendants of node $id:

$data = $nestedSet->getSubBranch($id,true);

This produces an associative array called $data containing all of the nodes. Just as with any associative array we can iterate through it in a variety of ways and make any changes we want, so say we wanted to add a “url” field based on the name of each node we could use:

foreach ($data as $id => $node) {
		$data[$id]['url'] = "/option/".urlencode($node['name']);
	}

NestedSet supports a number of “output drivers” or mechanisms for connecting with other tools to produce our output. The most commonly used option is the “Menu” driver which can be used with PEAR::HTML_Menu to output HTML representations. To use that we first need to define some parameters eg:

$params = array(
		'structure' => $data,
		'titleField' => 'name',
		'urlField' => 'url'
	);

Here “structure” is the associative array with our data in it, and “titleField” and “urlField” are the keys in that array for the title and URL of each node.

With that array in place we have a few more steps to produce our output. Firstly, we want to get an Output object from NestedSet. This will allow us to access the data in a method that is useful for our different output systems. We use a factory method with the parameters we just defined and the name of the driver we want to use:

$output =& DB_NestedSet_Output::factory($params, 'Menu');
	$structure = $output->returnStructure();

At this point, $structure will contain a “nested” array which looks rather like the structure of our tree. You might like to try:

print_r($structure);

to take a look.

If you want to make use of HTML_Menu, this is the data you pass on to it:

$menu =& new HTML_Menu($structure, 'sitemap');

should do the trick.

Since I tend to use Smarty for all my templating, I have taken to assigning $structure into smarty and then use a custom plugin to iterate over it and produce the menus. You can find that plugin here.

Conclusion

Once you’re up and running with NestedSet it provides a simple way of maintaining tree structures and using them in web applications. While it’s not the appropriate choice in all contexts (I wouldn’t choose it if I were using XML to store my data, for example) it’s well worth a little investigation.

Configuration and Instantiation#

Adding Nodes#

Changing Node Properties#

Deleting Nodes#

Moving/Copying Nodes#

Producing Output#

Conclusion#