NYCPHP Meetup

[Dan Cech]

Brian O'Connor wrote:
> I'm using mysql (sorry, should have posted it on that list instead of
> talk).
> 
> I looked into the NSM, however my fear is the insert / update time.  The
> site is based on flexibility of being able to change your 'events'.
> 
> I'm still weighing the pros and cons of each method.
> 
> Thanks for all the input, its greatly appreciated.
> 
> - Brian

If your tree is relatively shallow you can use the regular parent_id
structure and 'cheat' by grabbing the number of children each node has
so that you only need to recurse for nodes that actually have children.

Example:

SELECT t1.*,count(t2.id)
FROM mytable AS t1 JOIN mytable AS t2 ON t2.parent_id=t1.id
WHERE t1.parent_id=0
GROUP BY t1.id

This will give you a list of all the 'root' elements, and a count of
each elements children, to get the next level you can iterate over them
and grab the children.

I have used this structure a couple of times and you'll cut your number
of queries by the number of 'leaf' nodes in the tree vs the regular
approach of checking each node for children individually.

Of course, I've also done a fair bit of work on MPTT (Modified Preorder
Traversal Tree) models, you can find some code I cooked up a few years
ago here:

http://clew.phpwerx.net/

And also check out phpGACL:

http://phpgacl.sourceforge.net/

The nice thing about MPTT is that if you're careful you can make the
system tolerant of gaps in the left and right values, and thus the tree
need not be in an invalid state at any point.  Also, because we still
store the parent id, you can easily grab just the direct parents or
children of a given node, and also rebuild the left and right values in
a disaster recovery situation.

Dan