Working with Tree data (MPTT)

26 March, 2007

In the past week, a lot happened to this site, and not all of it was good :). Where to begin... the development machine died (hopefully get it back today); I moved all the code from a backup onto my aging laptop, my previous host account expired; I changed hosts to Dreamhost, the update from my laptop to the live version included some code that doesn't work/isn't finished; I upgraded my cake version only to discover some of my code was incompatible; I decided to take advantage of having php5 as an option and discovered some of my code was not php5 compatible etc. etc. But anyway, enough about that, hopefully things are on the up :).

One of the things that unintentionally became visible during all this was a demo I've been working on to demonstrate and test the use of the new MPTT tree behavior. It has a few quirks for which I have written a patch and the demo also serves to test how well, or not, this patch functions. At the time of writing this post the code available for download won't work, but the demo itself at least is fully functional.

What are behaviors

A word on behaviors before continuing: Behaviors are like components or helpers for models, they allow you to transparently modify how a model acts and/or provide extra methods that you can call as if they were declared in the model class itself. It's probably best to look at an example of a behavior to know how to write one.

The trouble with 'traditional' trees

Before moving on to explain a little about the demo and the tree behavior, perhaps it is worthwhile to point out what problem it addresses or what benefit it gives.

If you want to store hierarchal data, it would be logical to store each row in the database and also have a parent field to store the id of that rows parent. When looking at small or relatively flat trees this is both easy to do and manage. The problem with such data is, for example, if have many levels in your hierarchy, and you want to find all children and sub children that are under a grand-parent node. In this case the (recursive) logic necessary to generate a tree representing the node and it's children is to find the node; find each node that has the 'parent' field set to be the id of the parent node; then for each returned child search for each node that has the 'parent' field set to be it's id etc. ad infinitum. It should be apparent that even with a tree of relatively trivial size this can add up to a large quantity of db and php work. There are of course similar recursive logic requirements for pretty much any action you might want to do to your tree of data, the only thing that is really simple is how to add a child to a parent.

Tree behavior and demo

MPTT logic makes it possible to simplify everything except adding a child or moving a nodes location, but that isn't so important because the tree behavior will handle all of that for you. The tree behavior requires 3 fields to be present in your table, you can name them what you like but their meaning is 'parent', 'left' and 'right'. The left and right fields would only be referred to directly in an applications code when searching; updating these fields is never done by applications code, and is managed transparently by the behavior itself - i.e. if you add a new node, move something around (either by explicitly calling $this->ModelName->setParent($newParentId); or simply $this->ModelName->saveField('parent',$newParentId);), or delete something, the left and right fields are kept up to date without the application code itself doing or calling anything.

The tree demo allows for the testing of most (all?) display and management functions that one might want to do with a tree stored in a database. All the options are listed in the side menu. Here's a brief overview of the functionality:

View a tree

The view method generates it's information for display with a single query, sorting the data by the left field. It involves no recursive logic at all, as such it is possible to display trees in this way which otherwise (using a recursive 'find by parent id' logic routine) would take much longer or run out of resources. Some fluff has been added to the view (the red lines) to aide knowing which node is the child of which, but this code is in principle very, very simple.

Verify

Will perform a series of tests to check if the current tree is valid. Not infallible, but will usually highlight errors.

Delete/Remove a node

Delete a node (and it's children). Remove a node from the tree and all of the (node to be removed)'s children will re-parented to their grandparent, and then the (node to be removed) will be moved to the end of the tree as an orphan (a top level node). Optionally this node may be deleted in the same action.

Deparent a node

The selected node becomes a new orphan, the structure of its children is maintained.

Move up/move down

Exactly what it says on the tin. Won't let you move something when it isn't possible.

Initialize

A recursive function for testing purposes, which generates a tree with the dimensions specified in the parameters. The size of tree which can be generated is limited with the online demo.

Create Under

Creates a new node under the node specified in the parameters.

Move

Will change the parent of a node, taking care of its children. Will not allow a node to be moved to an illogical position (under itself).

TGFT (Thank God For That) Tests/Functions

Flatten

Will make every node an orphan (useful for testing what happens with multiple top level nodes).

Corrupt MPTT data

Will delete all left and right field values, leaving the parent field values intact. This would simulate the situation of a none-mptt table having new left and right fields added.

Corrupt parent data

Will delete all parent field values, leaving the left and right field values intact. This would simulate a partial disaster.

Recover

Based upon either the parent, or left/right data, the other source of info will be repopulated.

Wrapping Up

The demo still isn't perfect and can manages to generate invalid trees in some circumstances, when that's ironed out I'll be submitting another patch to the cake team. Until then the demo is available for your experimenting pleasure, and don't forget: If you see a message in red saying you managed to create an invalid tree, you can always recover from that ;).

Bake On!