nested-set.txt

+++ Introduction

Nested Set is a solution for storing hierarchical data that provides very fast read access. However, updating nested set trees is more costly. Therefore this solution is best suited for hierarchies that are much more frequently read than written to. And because of the nature of the web, this is the case for most web applications.

For more detailed information on the Nested Set, read here:

* [http://www.sitepoint.com/article/hierarchical-data-database/2 http://www.sitepoint.com/article/hierarchical-data-database/2]
* [http://dev.mysql.com/tech-resources/articles/hierarchical-data.html http://dev.mysql.com/tech-resources/articles/hierarchical-data.html]


+++ Setting up

To set up your model as Nested Set, you must add the following code to your model's table definition.

<code type="php">
...
    public function setTableDefinition() {
        ...

        $this->actAs('NestedSet');       

       ...
    }
...
</code>

"actAs" is a convenience method that loads templates that are shipped with Doctrine(Doctrine_Template_* classes). The more general alternative would look like this:

<code type="php">
...
    public function setTableDefinition() {
        ...

        $this->loadTemplate('Doctrine_Template_NestedSet');       

       ...
    }
...
</code>

Detailed information on Doctrine's templating model can be found in chapter [doc class-templates :index :name]. These templates add some functionality to your model. In the example of the nested set, your model gets 3 additional fields: "lft", "rgt", "level". You never need to care about "lft" and "rgt". These are used internally to manage the tree structure. The "level" field however, is of interest for you because it's an integer value that represents the depth of a node within it's tree. A level of 0 means it's a root node. 1 means it's a direct child of a root node and so on. By reading the "level" field from your nodes you can easily display your tree with proper indendation. 

**You must never assign values to lft, rgt, level. These are managed transparently by the nested set implementation.**

+++ More than 1 tree in a single table

The nested set implementation can be configured to allow your table to have multiple root nodes, and therefore multiple trees within the same table.

The example below shows how to setup and use multiple roots based upon the set up above:

<code type="php">
...
    public function setTableDefinition() {
        ...
        $options = array('hasManyRoots' => true,  // enable many roots
                 'rootColumnName' => 'root_id');  // set root column name, defaults to 'root_id'
        $this->actAs('NestedSet', $options);       

       ...
    }
...
</code>

The rootColumnName is the column that is used to differentiate between trees. When you create a new node to insert it into an existing tree you dont need to care about this field. This is done by the nested set implementation. However, when you want to create a new root node you have the option to set the "root_id" manually. The nested set implementation will recognize that. In the same way you can move nodes between different trees without caring about the "root_id". All of this is handled for you.

+++ Working with the tree(s)

After you successfully set up your model as a nested set you can start working with it. Working with Doctrine's nested set implementation is all about 2 classes: Doctrine_Tree_NestedSet and Doctrine_Node_NestedSet. These are nested set implementations of the interfaces Doctrine_Tree_Interface and Doctrine_Node_Interface. Tree objects are bound to your table objects and node objects are bound to your record objects. This looks as follows:
<code type="php">
  // Assuming $conn is an instance of some Doctrine_Connection
  $treeObject = $conn->getTable('MyNestedSetModel')->getTree();
  // ... the full tree interface is available on $treeObject

  // Assuming $entity is an instance of MyNestedSetModel
  $nodeObject = $entity->getNode();
  // ... the full node interface is available on $nodeObject
</code>  

In the following sub-chapters you'll see code snippets that demonstrate the most frequently used operations with the node and tree classes.

++++ Creating a root node

<code type="php">
...
$root = new MyNestedSetModel();
$root->name = 'root';
$treeObject = $conn->getTable('MyNestedSetModel')->getTree();
$treeObject->createRoot($root); // calls $root->save() internally
...
</code>

++++ Inserting a node

<code type="php">
...
// Assuming $someOtherRecord is an instance of MyNestedSetModel
$record = new MyNestedSetModel();
$record->name = 'somenode';
$record->getNode()->insertAsLastChildOf($someOtherRecord); // calls $record->save() internally
...
</code>

++++ Deleting a node

<code type="php">
...
// Assuming $record is an instance of MyNestedSetModel
$record->getNode()->delete(); // calls $record->delete() internally. It's important to delete on the node and not on the record. Otherwise you may corrupt the tree.
...
</code>

Deleting a node will also delete all descendants of that node. So make sure you move them elsewhere before you delete the node if you dont want to delete them.

++++ Moving a node

<code type="php">
...
// Assuming $record and $someOtherRecord are both instances of MyNestedSetModel
$record->getNode()->moveAsLastChildOf($someOtherRecord);
...
</code>

There are 4 move methods: moveAsLastChildOf($other), moveAsFirstChildOf($other), moveAsPrevSiblingOf($other) and moveAsNextSiblingOf($other). The method names are self-explanatory.

++++ Examining a node

<code type="php">
...
// Assuming $record is an instance of MyNestedSetModel
$isLeaf = $record->getNode()->isLeaf(); // true/false
$isRoot = $record->getNode()->isRoot(); // true/false
...
</code>

++++ Examining and retrieving siblings

<code type="php">
...
// Assuming $record is an instance of MyNestedSetModel
$hasNextSib = $record->getNode()->hasNextSibling(); // true/false
$haPrevSib = $record->getNode()->hasPrevSibling(); // true/false

$nextSib = $record->getNode()->getNextSibling(); // returns false if there is no next sibling, otherwise returns the sibling
$prevSib = $record->getNode()->getPrevSibling(); // returns false if there is no previous sibling, otherwise returns the sibling

$siblings = $record->getNode()->getSiblings(); // an array of all siblings
...
</code>

++++ Examining and retrieving children / parents / descendants / ancestors

<code type="php">
...
// Assuming $record is an instance of MyNestedSetModel
$hasChildren = $record->getNode()->hasChildren(); // true/false
$hasParent = $record->getNode()->hasParent(); // true/false

$firstChild = $record->getNode()->getFirstChild(); // returns false if there is no first child, otherwise returns the child
$lastChild = $record->getNode()->getLastChild(); // returns false if there is no lase child, otherwise returns the child
$parent = $record->getNode()->getParent(); // returns false if there is no parent, otherwise returns the parent

$children = $record->getNode()->getChildren(); // returns false if there are no children, otherwise returns the children
// !!! IMPORATNT: getChildren() returns only the direct descendants. If you want all descendants, use getDescendants() !!!

$descendants = $record->getNode()->getDescendants(); // returns false if there are no descendants, otherwise returns the descendants
$ancestors = $record->getNode()->getAncestors(); // returns false if there are no ancestors, otherwise returns the ancestors

$numChildren = $record->getNode()->getNumberChildren(); // returns the number of children
$numDescendants = $record->getNode()->getNumberDescendants(); // returns the number of descendants

...
</code>

getDescendants() and getAncestors() both accept a parameter that you can use to specify the "depth" of the resulting branch. For example getDescendants(1) retrieves only the direct descendants (the descendants that are 1 level below, that's the same as getChildren()). In the same fashion getAncestors(1) would only retrieve the direct ancestor (the parent), etc. getAncestors() can be very useful to efficiently determine the path of this node up to the root node or up to some specific ancestor (i.e. to construct a breadcrumb navigation).

++++ Simple Example: Displaying a tree

<code type="php">
...
$treeObject = $conn->getTable('MyNestedSetModel')->getTree();
$tree = $treeObject->fetchTree();
foreach ($tree as $node) {
    echo str_repeat('&nbsp;&nbsp;', $node['level']) . $node['name'] . '<br />';
}
...
</code>

+++ Advanced usage

The previous sections have explained the basic usage of Doctrine's nested set implementation. This section will go one step further.

++++ Fetching a tree with relations

If you're a demanding software developer this question may already have come into your mind: "How do I fetch a tree/branch with related data?". Simple example: You want to display a tree of categories, but you also want to display some related data of each category, let's say some details of the hottest product in that category. Fetching the tree as seen in the previous sections and simply accessing the relations while iterating over the tree is possible but produces a lot of unnecessary database queries. Luckily, Doctrine_Query and some flexibility in the nested set implementation have come to your rescue. The nested set implementation uses Doctrine_Query objects for all it's database work. By giving you access to the base query object of the nested set implementation you can unleash the full power of Doctrine_Query while using your nested set. Take a look at the following code snippet:

<code type="php">
$query = new Doctrine_Query();
$query->select("cat.name, hp.name, m.name")->from("Category cat")
        ->leftJoin("cat.hottestProduct hp")
        ->leftJoin("hp.manufacturer m");
$treeObject = $conn->getTable('Category')->getTree();
$treeObject->setBaseQuery($query);
$tree = $treeObject->fetchTree();
$treeObject->resetBaseQuery();
</code>

There it is, the tree with all the related data you need, all in one query.

You can take it even further. As mentioned in the chapter "Improving Performance" you should only fetch objects when you need them. So, if we need the tree only for display purposes (read-only) we can do:

<code type="php">
$query = new Doctrine_Query();
$query->select("base.name, hp.name, m.name")->from("Category base")
        ->leftJoin("base.hottestProduct hp")
        ->leftJoin("hp.manufacturer m")
        ->setHydrationMode(Doctrine::HYDRATE_ARRAY);
$treeObject = $conn->getTable('Category')->getTree();
$treeObject->setBaseQuery($query);
$tree = $treeObject->fetchTree();
$treeObject->resetBaseQuery();
</code>

Now you got a nicely structured array in $tree and if you use array access on your records anyway, such a change will not even effect any other part of your code. This method of modifying the query can be used for all node and tree methods (getAncestors(), getDescendants(), getChildren(), getParent(), ...). Simply create your query, set it as the base query on the tree object and then invoke the appropriate method.