NestedSet Behavior

The nested_set behavior allows a model to become a tree structure, and provides numerous methods to traverse the tree efficiently.

Many applications need to store hierarchical data in the model. For instance, a forum stores a tree of messages for each discussion, a CMS sees sections and subsections as a navigation tree, and in a business organization chart, each person is a leaf of the organization tree. Nested sets are a good way to store such hierarchical data in a relational database and manipulate it. The name “nested sets” describes the algorithm used to store the position of a model in the tree; it’s also known as “modified preorder tree traversal.”

Basic usage

In schema.xml, use the <behavior> tag to add the nested_set behavior to a table:

<table name="section">
  <column name="id" required="true" primaryKey="true" autoIncrement="true" type="integer" />
  <column name="title" type="varchar" required="true" primaryString="true" />
  <behavior name="nested_set" />
</table>

Rebuild your model, run the table creation SQL again, and you’re ready to go. The model now has the ability to be inserted into a tree structure:

$s1 = new Section();
$s1->setTitle('Home');
$s1->makeRoot(); // make this node the root of the tree
$s1->save();

$s2 = new Section();
$s2->setTitle('World');
$s2->insertAsFirstChildOf($s1); // insert the node in the tree
$s2->save();

$s3 = new Section();
$s3->setTitle('Europe');
$s3->insertAsFirstChildOf($s2); // insert the node in the tree
$s3->save();

$s4 = new Section();
$s4->setTitle('Business');
$s4->insertAsNextSiblingOf($s2); // insert the node in the tree
$s4->save();

/* The sections are now stored in the database as a tree:
    $s1:Home
    |       \
$s2:World  $s4:Business
    |
$s3:Europe
*/

You can continue inserting new nodes as children or siblings of existing nodes, using insertAsFirstChildOf(), insertAsLastChildOf(), insertAsPrevSiblingOf(), and insertAsNextSiblingOf().

Once you’ve built a tree, you can traverse it using the numerous methods the nested_set behavior adds to the query and model objects. For instance:

$rootNode = SectionQuery::create()->findRoot(); // $s1
$worldNode = $rootNode->getFirstChild();        // $s2
$businessNode = $worldNode->getNextSibling();   // $s4
$firstLevelSections = $rootNode->getChildren(); // [$s2, $s4]
$allSections = $rootNode->getDescendants();     // [$s2, $s3, $s4]
// you can also chain the methods
$europeNode = $rootNode->getLastChild()->getPrevSibling()->getFirstChild(); // $s3
$path = $europeNode->getAncestors(); // [$s1, $s2]

The nodes returned by these methods are regular model objects, with access to their properties and related models. The nested_set behavior also adds inspection methods to nodes:

echo $s2->isRoot();       // false
echo $s2->isLeaf();       // false
echo $s2->getLevel();     // 1
echo $s2->hasChildren();  // true
echo $s2->countChildren();// 1
echo $s2->hasSiblings();  // true

Each of the traversal and inspection methods results in a single database query, regardless of the node’s position in the tree. This is because the information about a node’s position is stored in three columns, named tree_left, tree_right, and tree_level, whose values are determined by the nested set algorithm — much more effective for read queries than a tree using a simple parent_id foreign key.

Manipulating nodes

You can move a node — and its subtree — across the tree using moveToFirstChildOf(), moveToLastChildOf(), moveToPrevSiblingOf(), and moveToNextSiblingOf(). These operations are immediate and don’t require saving the model afterwards:

// move the entire "World" section under "Business"
$s2->moveToFirstChildOf($s4);
/* The tree is modified as follows:
$s1:Home
  |
$s4:Business
  |
$s2:World
  |
$s3:Europe
*/

// now move the "Europe" section directly under root, after "Business"
$s3->moveToNextSiblingOf($s4);
/* The tree is modified as follows:
    $s1:Home
    |        \
$s4:Business $s3:Europe
    |
$s2:World
*/

You can delete the descendants of a node using deleteDescendants():

// delete the entire "World" section of "Business"
$s4->deleteDescendants();
/* The tree is modified as follows:
    $s1:Home
    |        \
$s4:Business $s3:Europe
*/

If you delete() a node, all its descendants are deleted in cascade. To avoid accidental deletion of an entire tree, calling delete() on a root node throws an exception — use the query class’s delete() method instead to delete an entire tree.

Filtering results

The nested_set behavior adds numerous methods to the generated query object, useful for building more complex queries. For instance, to get all the children of the root node ordered by title:

$children = SectionQuery::create()
    ->childrenOf($rootNode)
    ->orderByTitle()
    ->find();

Alternatively, if you already have an existing query, you can pass it to the model object’s methods to filter results:

$orderQuery = SectionQuery::create()->orderByTitle();
$children = $rootNode->getChildren($orderQuery);

Multiple trees

When you need to store several trees for a single model — for instance, several threads of posts in a forum — use a scope for each tree. This requires enabling scope tree support in the behavior definition via the use_scope parameter:

<table name="post">
  <column name="id" required="true" primaryKey="true" autoIncrement="true" type="integer" />
  <column name="body" type="varchar" required="true" primaryString="true" />
  <behavior name="nested_set">
    <parameter name="use_scope" value="true" />
    <parameter name="scope_column" value="thread_id" />
  </behavior>
  <foreign-key foreignTable="thread" onDelete="cascade">
    <reference local="thread_id" foreign="id" />
  </foreign-key>
</table>

Now, after rebuilding your model, you can have as many trees as required:

$thread = ThreadQuery::create()->findPk(123);
$firstPost = PostQuery::create()->findRoot($thread->getId());  // first message of the discussion
$discussion = PostQuery::create()->findTree($thread->getId()); // all messages of the discussion
PostQuery::create()->inTree($thread->getId())->delete();       // delete an entire discussion
$firstPostOfEveryDiscussion = PostQuery::create()->findRoots();

Using a RecursiveIterator

An alternative way to browse a tree structure extensively is to use a RecursiveIterator. The nested_set behavior provides an easy way to retrieve such an iterator from a node, and to parse the entire branch in a single iteration:

$root = SectionQuery::create()->findRoot();
foreach ($root->getIterator() as $node) {
    echo str_repeat(' ', $node->getLevel()) . $node->getTitle() . "\n";
}

The iterator parses the tree recursively, retrieving the children of every node. This can be quite effective on very large trees, since the iterator hydrates only a few objects at a time.

Beware, though, that the iterator executes many queries to parse a tree. On smaller trees, prefer getBranch(), which executes only one query and hydrates all records at once:

$root = SectionQuery::create()->findRoot();
foreach ($root->getBranch() as $node) {
    echo str_repeat(' ', $node->getLevel()) . $node->getTitle() . "\n";
}

Parameters

By default, the behavior adds three columns to the model — four if you use the scope feature. You can use custom names for the nested set columns. The following schema illustrates a complete customization of the behavior:

<table name="post">
  <column name="id" required="true" primaryKey="true" autoIncrement="true" type="integer" />
  <column name="lft" type="integer" />
  <column name="rgt" type="integer" />
  <column name="lvl" type="integer" />
  <column name="thread_id" type="integer" />
  <column name="body" type="varchar" required="true" primaryString="true" />
  <behavior name="nested_set">
    <parameter name="left_column" value="lft" />
    <parameter name="right_column" value="rgt" />
    <parameter name="level_column" value="lvl" />
    <parameter name="use_scope" value="true" />
    <parameter name="scope_column" value="thread_id" />
  </behavior>
  <foreign-key foreignTable="thread" onDelete="cascade">
    <reference local="thread_id" foreign="id" />
  </foreign-key>
</table>

Whatever names you give your columns, the nested_set behavior always adds the following proxy methods, mapped to the correct column:

$post->getLeftValue();  // returns $post->lft
$post->setLeftValue($left);
$post->getRightValue(); // returns $post->rgt
$post->setRightValue($right);
$post->getLevel();      // returns $post->lvl
$post->setLevel($level);
$post->getScopeValue(); // returns $post->thread_id
$post->setScopeValue($scope);

Complete API

Methods added by the behavior to the model objects:

// storage columns accessors
int   getLeftValue()
$node setLeftValue(int $left)
int   getRightValue()
$node setRightValue(int $right)
int   getLevel()
$node setLevel(int $level)
// only for behavior with use_scope
int   getScopeValue()
$node setScopeValue(int $scope)

// root maker (requires calling save() afterwards)
$node makeRoot()

// inspection methods
bool  isInTree()
bool  isRoot()
bool  isLeaf()
bool  isDescendantOf()
bool  isAncestorOf()
bool  hasParent()
bool  hasPrevSibling()
bool  hasNextSibling()
bool  hasChildren()
int   countChildren()
int   countDescendants()

// tree traversal methods
$node setParent($node)
$node getParent()
$node getPrevSibling()
$node getNextSibling()
PropulsionObjectCollection getChildren()
?$node getFirstChild()
?$node getLastChild()
PropulsionObjectCollection getSiblings($includeCurrent = false, Criteria $c = null)
PropulsionObjectCollection getDescendants(Criteria $c = null)
PropulsionObjectCollection getBranch(Criteria $c = null)
PropulsionObjectCollection getAncestors(Criteria $c = null)

// node insertion methods (require calling save() afterwards)
$node addChild($node)
$node insertAsFirstChildOf($node)
$node insertAsLastChildOf($node)
$node insertAsPrevSiblingOf($node)
$node insertAsNextSiblingOf($node)

// node move methods (immediate, no need to save() afterwards)
$node moveToFirstChildOf($node)
$node moveToLastChildOf($node)
$node moveToPrevSiblingOf($node)
$node moveToNextSiblingOf($node)

// deletion methods
$node deleteDescendants()

Note

getChildren(), getSiblings(), getDescendants(), getBranch(), and getAncestors() return an empty PropulsionObjectCollection — never array() — when there’s nothing to return. getFirstChild()/getLastChild() return null rather than array() for a node with none. Code written against the old array-returning shape needs to check for an empty collection / null instead — see Upgrading from 2.x to 3.0.

Methods added to the query classes:

// tree filter methods
query descendantsOf($node)
query branchOf($node)
query childrenOf($node)
query siblingsOf($node)
query ancestorsOf($node)
query rootsOf($node)
// only for behavior with use_scope
query treeRoots()
query inTree($scope = null)
coll  findRoots()
// order methods
query orderByBranch($reverse = false)
query orderByLevel($reverse = false)
// termination methods
$node findRoot($scope = null)
coll findTree($scope = null)

A few more static methods added to the peer classes (e.g. SectionPeer::retrieveRoot()), not the query classes:

$node retrieveRoot($scope = null)
array retrieveTree($scope = null)
int   deleteTree($scope = null)
// only for behavior with use_scope
array retrieveRoots(Criteria $c = null)