Joomla! Documentation™

Starting with version 11.1 the Joomla Platform now includes native support for storing and retrieving hierarchical information in the form of "nested sets" in database tables. This support is used in the implementation of menus and categories in the core Joomla CMS from version 1.6 onwards, but can of course be used in your own extensions too. This document assumes that you are already familiar with using the JTable, JDatabase and JDatabaseQuery classes to interact with a database, either the Joomla database itself, or some external database.

Introduction

In the nested sets model each data item is stored as a row in the database table in the normal manner. However, additional columns are present in the table to express the hierarchical relationship between the data items. Each data item is referred to as a node and the collection of nodes can be thought of as forming a tree. Nodes can have zero, one or many child nodes. A node that has no children is referred to as a leaf node. A child node can itself have children and this nesting can carry on to arbitrary depth. The table is assumed to hold a single tree with a single node being allocated as the root node. If you need to be able to store multiple trees then simply make the root node of each such tree a child node under the single root node and adjust your code to take this into account.

As each node contains columns labelled "lft" and "rgt" for "left" and "right" respectively, it is tempting to think that the data structure is a binary tree. However, these columns do not store node ids as they are not links to other nodes in the tree, but instead store sequence information. More information can be found on the theory behind nested sets here The term "nested sets" is a little inaccurate as a set is, stricly speaking, an unordered collection of objects. In the Joomla implementation the order of nodes under a parent node is preserved and API calls are available to manipulate the order. A better term would perhaps be "nested ordered sets".

It should be noted that certain operations, such as inserting a new node, can be expensive in terms of disk access when dealing with a large tree and applications should be designed with this in mind.

Getting Started

The essential class is JTableNested, which extends the base JTable class, so instead of extending JTable you should extend your table class from JTableNested instead.

Your table must include a number of standard columns that are required for JTableNested to maintain the tree structure successfully. These are:-

• id (primary key)
• parent_id
• lft
• rgt
• level
• title
• alias
• access
• path

The primary key does not need to be called "id", but it is required. Other columns must have the names listed above.

For example, a suitable MySQL command to create a basic table compatible with JTableNested would be

CREATE TABLE IF NOT EXISTS `#__nestedsets` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `parent_id` int(10) unsigned NOT NULL DEFAULT '0',
  `lft` int(11) NOT NULL DEFAULT '0',
  `rgt` int(11) NOT NULL DEFAULT '0',
  `level` int(10) unsigned NOT NULL DEFAULT '0',
  `title` varchar(255) NOT NULL,
  `alias` varchar(255) NOT NULL DEFAULT '',
  `access` tinyint(3) unsigned NOT NULL DEFAULT '0',
  `path` varchar(255) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  KEY `idx_left_right` (`lft`,`rgt`)
) DEFAULT CHARSET=utf8;

You will, of course, need to add further columns for your specific data requirements. For the purposes of this documentation a column called "payload" will be used to indicate this custom data.

Instantiating the table object

You instantiate the nested sets table object in exactly the same way as you would for a regular table object. For example, if your table class file is located in a /tables directory in your component area, you could use code like this:

JTable::addIncludePath( JPATH_COMPONENT.'/tables' );
$table = JTable::getInstance( 'nestedsets', 'Table' );

This will instantiate your table class called 'TableNestedSets' in the file 'nestedsets.php'. Remember to extend from JTableNested instead of JTable:

class TableNestedSets extends JTableNested
{
// Your properties and methods go here.
}

Adding a root node

The quickest way to add a root node to an otherwise empty table is to use code like this, which can be added to your table class:

/**
 * Add the root node to an empty table.
 *
 * @return    integer  The id of the new root node.
 */
public function addRoot()
{
    $db = JFactory::getDbo();
    $sql = 'INSERT INTO ckm_profiles'
        . ' SET parent_id = 0'
        . ', lft = 0'
        . ', rgt = 1'
        . ', level = 0'
        . ', title = '.$db->quote( 'root' )
        . ', alias = '.$db->quote( 'root' )
        . ', access = 1'
        . ', path = '.$db->quote( '' )
        ;
    $db->setQuery( $sql );
    $db->query();
    
    return $db->insertid();
}

TODO: CHANGE THE ABOVE TO USE JDatabaseQuery.

It is perfectly reasonable to store payload data in the root node. For example, you might like to store component configuration data in the payload column of the root node.

Getting the root node id

To determine the id of the root node use the getRootId method. For example, in this example if the root node is not found, it is created.

$rootId = $table->getRootId();
if ($rootId === false) {
    $rootId = $table->addRoot();
}

Updating a node

Updating the payload data in a node is done in exactly the same way as you would update a record in a regular database table using the JTable class. Given an array of data fields, this code binds it to the table object, checks its validity then stores it in the database table.

$table->bind( $data_array );
$table->check();
$table->store();

Updating a node in such a way that it alters the structure of the tree, for example, by moving a node from one location to another, is a little more involved and is described below. There are also some convenience methods for publishing/unpublished a node and these are also described in more detail below.

Adding a new node

Adding a new node to the table is done in a similar way to adding a row to a normal Joomla table. Data is bound to the Joomla table object using the bind method, followed by calls to check and store. These methods have been overridden in the JTableNested class to provide the additional functionality required for storing nested sets.

However, in order to determine where in the tree the new node is to be inserted, you need to make a call to the setLocation method. The setLocation method takes two arguments, the first is the id of a "reference" node in the tree. The new node will be inserted relative to this node with the relationship being specified by the second argument. Possible values for this relationship are:

• before - the new node will be inserted before the reference node but at the same level.
• after - the new node will be inserted after the reference node but at the same level.
• first-child - the new node will be inserted as the first child node of the reference node.
• last-child - the new node will be inserted as the last child node of the reference node.

In this example a new node is inserted as the first child of the reference node.

// Given an array of data fields in $data_array and a reference node id in $reference_id,
// this code will add the new node as the first child of the reference node.

// Get the table object.
// Note that in a model you can replace this with $table = $this->getTable();
$table = JTable::getInstance( 'yourtable' );

// Specify where to insert the new node.
$table->setLocation( $reference_id, 'first-child' );

// Bind data to the table object.
$table->bind( $data_array );

// Force a new node to be created.
$table->id = 0;

// Check that the node data is valid.
$table->check();

// Store the node in the database table.
$table->store();

In order to maintain the integrity of the data structure, the table is locked during a node insertion operation. Bear in mind that adding a new node to a large table is an expensive operation so the table could potentially be locked for a considerable period. You may need to take this into account when designing your application.

Retrieving a single node by id

If you know the id of a node then retrieving it can be done in the same way that you would retrieve a row in a regular Joomla table. For example,

// Get the node id from the request.
$id = JRequest::getInt( 'id' );

// Get the node from the table.
$table->load( $id );

Is it a leaf node?

A leaf node is one that has no child nodes beneath it. To determine if a node is a leaf node you can use code like the following:

// If $id is the id of a node, determine if it is a leaf node.
if ($table->isLeaf( $id )) {
  echo 'This is a leaf node';
else {
  echo 'This is NOT a leaf node';
}

Retrieving a subtree

To retrieve an entire subtree given the id of the base node of the subtree, you can use code like the following

// If $id is the id of a node, retrieve the subtree with this node as its root.
$subtree = $table->getTree( $id );
print_r( $subtree );

This will retrieve an array of all the nodes in the subtree. The array is one-dimensional and lists the nodes in preorder traversal order. Note that if your table is large calling getTree() from the root node will retrieve the entire table and very likely run you out of memory, so use it with caution.

Retrieving a path

To retrieve all the nodes along the path leading to a specified node, you can use code like this:

$pathNodes = $table->getPath( $id );
print_r( $pathNodes );

This will retrieve a one-dimensional array of all the nodes from the root node along the path leading to the specified node.

Publish or unpublish a node or an entire branch

Supporting the publish/unpublish feature is a little more involved than with a regular flat database table as the state of parent and child nodes must also be taken into account. Fortunately, the overridden publish and unpublish methods provided by JTableNested make the management of publish/unpublish almost transparent.

To publish or unpublish one or more nodes use code like the following:

// $ids can be a single node id, or an array of node ids.
$state = 1;        // 0 = unpublish, 1 = publish
$userId = JFactory::getUser()->id;
if ($table->publish( $id, $state, $userId )) {
    echo 'State changed successfully';
}
else {
    echo 'State not changed';
}

The publish method respects rows checked out by other users and will attempt to checkin rows that it can after adjustments are made. The method will not allow you to set a publishing state higher than any ancestor node and will not allow you to set a publishing state on a node with a checked out child.

TODO: Using publish/unpublish with checkin/out requires some additional columns in the table. The documentation should be updated to reflect that.

Changing the order of nodes in a branch

There are a number of different ways of moving a node to a new location in the tree.

To move a node one position before or after its current position, but keeping it at the same level, you can use the orderUp or orderDown methods using code like the following:

if ($table->orderUp( $id )) {
    echo 'Success';
}
else {
    echo 'Failed to move node';
}

More generally, you can move a node by more than one position at a time using the move method. For example, the following code moves the node 2 positions before its current position, at the same level.

// Get the node id to be moved from the request.
$key = $this->_tbl_key;
$this->$key = JRequest::getInt( 'id' );

// Set the direction and magnitude of the move.
// Negative indicates "before", positive "after"
$delta = -2;

// Do the move.
// Notice that the node id is not passed as an argument to
// move; it must already be set in the table object.
if ($table->move( $delta )) {
    echo 'Success';
}
else {
    echo 'Failed to move node';
}

In the most general case, a node can be moved to an arbitrary position in the tree using the moveByReference method. This is very similar to adding a completely new node to the tree in that you need to specify the location to move the node to by reference to some other node.

In this example a new node is inserted as the last child of the reference node.

// Determine the reference node id.
$reference_id = JRequest::getInt( 'reference' );

// Determine the relationship with the reference node.  Possible values are:-
// before - the new node will be inserted before the reference node but at the same level.
// after - the new node will be inserted after the reference node but at the same level.
// first-child - the new node will be inserted as the first child node of the reference node.
// last-child  - the new node will be inserted as the last child node of the reference node.
$relation = 'last-child';

// Determine the node to be moved.
$node_id = JRequest::getInt( 'id' );

// Do the move.
if ($table->moveByReference( $reference_id, $relation, $node_id )) {
    echo 'Success';
}
else {
    echo 'Failed to move node';
}

Deleting a node

Deleting a node given its node id is very simple as the following example illustrates:

// Determine the node id from the request.
$node_id = JRequest::getInt( 'id' );

// Delete the node.
if ($table->delete( $node_id )) {
    echo 'Node deleted';
}
else {
    echo 'Failed to delete node';
}

Note that this operation will also delete all child nodes of the node being deleted, if any are present.