The Doctrine library comes with a feature called nested set, which makes saving trees in a database easy. However, it’s quite easy to accidentally cause a lot of extra unneeded queries if not being careful.
Here are some pointers to keep in mind while working with the nested set, and some example queries to make understanding it easier.
The general idea
Doctrine’s way of doing nested sets may at first seem confusing – what are the lft, rgt and level values and how do they relate to each other? Understanding the way lft, rgt and level works will allow you to understand how the tree actually works.
Fetching child rows
Typically, you might write something along the lines of..
<?php foreach($row->getChildren() as $child): ?> <b><?= $child->name; ?> <?php foreach($child->getChildren() as $childChild): ?> <?= $childChild->id; ?> <?php endforeach; ?> </b> <?php endforeach; ?> |
That’s very bad! getChildren method always hits the database, so the above could generate many unneeded queries.
Doctrine’s tree nodes do contain a method called getDescedants, which can be used to fetch all descedants up to a specific depth. Always use this instead of getChildren if you need more than a single level of children fetched.
What if you wanted to find all the child rows of two (or more) rows?
Finding all child rows of a specific row is simple:
All rows, which have a higher lft, a lower rgt and a higher level value are children of the row in question.
For example, if we have a row with lft = 10, rgt = 20 and level = 1, the following query would fetch the next two levels of children of the row:
SELECT * FROM example WHERE lft > 10 AND rgt < 20 AND level > 1 AND level < 4 |
Finding children of two rows would be similarily simple, just modify the where clause to (lft > 10 AND rgt < 20) OR (lft > 40 AND rgt < 50). If the two rows are actually siblings, you can simply do lft > 10 AND rgt < 50.
Fetching parent rows
Just like with getChildren, getParent will only fetch one parent, and will always query the DB. Use getAncestors instead if you need more than one level.
Seeing how child rows have higher lft and lower rgt, parent rows have the opposite: lower lft and higher rgt
Fetching all parents of a row with lft = 10, rgt = 20 and level = 4:
SELECT * FROM example WHERE lft < 10 AND rgt > 20 AND level < 4 |
For fetching multiple row’s parents can be done in a similar fashion as multiple row’s children.
Pros and cons
getDescedants and getAncestors have a small problem: Their results won’t appear in a “proper” tree structure – if you loop over them, you will have to manually look at level and other values to check if the rows are on different levels. This could be simplified by writing a class which forms a proper tree out of the Doctrine_Collection object.
The SQL queries also have similar problems. You will have to manually confirm the correct order and level of the rows returned. Whether or not these are things you can live with would depend on your application, but understanding how things work behind the scenes is always useful.