layout | title |
---|---|
documentation |
NestedSet Behavior |
The nested_set
behavior allows a model to become a tree structure, and provides numerous methods to traverse the tree in an efficient way.
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. In a business organization chart, each person is a leaf of the organization tree. Nested sets are the best 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 is also known as "modified preorder tree traversal".
In the schema.xml
, use the <behavior>
tag to add the nested_set
behavior to a table:
{% highlight xml %}
Rebuild your model, insert the table creation sql again, and you're ready to go. The model now has the ability to be inserted into a tree structure, as follows:
{% highlight php %}
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 */ {% endhighlight %} You can continue to insert new nodes as children or siblings of existing nodes, using any of the `insertAsFirstChildOf()`, `insertAsLastChildOf()`, `insertAsPrevSiblingOf()`, and `insertAsNextSiblingOf()` methods. Once you have built a tree, you can traverse it using any of the numerous methods the `nested_set` behavior adds to the query and model objects. For instance: {% highlight php %} findRoot(); // $s1 $worldNode = $rootNode->getFirstChild(); // $s2 $businessNode = $worldNode->getNextSibling(); // $s4 $firstLevelSections = $rootNode->getChildren(); // array($s2, $s4) $allSections = $rootNode->getDescendants(); // array($s2, $s3, $s4) // you can also chain the methods $europeNode = $rootNode->getLastChild()->getPrevSibling()->getFirstChild(); // $s3 $path = $europeNode->getAncestors(); // array($s1, $s2) {% endhighlight %} The nodes returned by these methods are regular Propel model objects, with access to the properties and related models. The `nested_set` behavior also adds inspection methods to nodes: {% highlight php %} isRoot(); // false echo $s2->isLeaf(); // false echo $s2->getLevel(); // 1 echo $s2->hasChildren(); // true echo $s2->countChildren(); // 1 echo $s2->hasSiblings(); // true {% endhighlight %} Each of the traversal and inspection methods result in a single database query, whatever the position of the node in the tree. This is because the information about the node position in the tree is stored in three columns of the model, named `tree_left`, `tree_left`, and `tree_level`. The value given to these columns is determined by the nested set algorithm, and it makes read queries much more effective than trees using a simple `parent_id` foreign key. ## Manipulating Nodes ## You can move a node - and its subtree - across the tree using any of the `moveToFirstChildOf()`, `moveToLastChildOf()`, `moveToPrevSiblingOf()`, and `moveToLastSiblingOf()` methods. These operations are immediate and don't require that you save the model afterwards: {% highlight php %} 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" $s2->moveToFirstChildOf($s4); /* The tree is modified as follows: $s1:Home | \ $s4:Business $s3:Europe | $s2:World */ {% endhighlight %} You can delete the descendants of a node using `deleteDescendants()`: {% highlight php %} deleteDescendants($s4); /* The tree is modified as follows: $s1:Home | \ $s4:Business $s3:Europe */ {% endhighlight %} 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 `delete()` Query method instead to delete an entire tree. ## Filtering Results ## The `nested_set` behavior adds numerous methods to the generated Query object. You can use these methods to build more complex queries. For instance, to get all the children of the root node ordered by title, build a Query as follows: {% highlight php %} childrenOf($rootNode) ->orderByTitle() ->find(); {% endhighlight %} Alternatively, if you already have an existing query method, you can pass it to the model object's methods to filter the results: {% highlight php %} orderByTitle(); $children = $rootNode->getChildren($orderQuery); {% endhighlight %} ## 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 that you enable scope tree support in the behavior definition by setting the `use_scope` parameter to `true`: {% highlight xml %}