On 1/3/07, Dr. Tarique Sani <[EMAIL PROTECTED]> wrote:
On 1/2/07, Langdon Stevenson <[EMAIL PROTECTED]> wrote: > What we seem to be talking about is creating an entirely new method of > defining and retrieving our security information hierarchy, something > different to modified preorder tree traversal. MPTT can't be and should not be abandoned - we have to find a way to apply the results in a better way
This discussion has peaked my interest in MPTT implementations. I am working on an object system for a CMS based on CakePHP and the object tree is implemented using MPTT. I did a "textbook" implementation of the thing, which means using a recursive algorithm to reorder the tree traversal data (lft and rgt) for each tree node in for inserts and deletes. I looked into the MPTT implementation in the ACL code and it looks like it cleverly avoids having to do recursive traversal in updating the lft and rgt fields during an update. But I think the optimizations used will only work in very simple trees that support the basic CRUD operations. My object tree needs to support reordering of nodes within a subtree as well as moving a node from one subtree to another. Because of this, an extra field is used and needs to be updated when the tree traversal data is updated. The simplest and most maintainable solution I found was through a recursive algorithm. The scenario presented by Dr. Tarique, very large tree of ACO's with very large tree of ARO's is a very real problem with my object system. MPTT provides for minimal amount of memory and SQL queries during reads. But when it comes to writes and updates, the thing uses up a lot of memory and requires a lot of SQL queries when updating a very large tree (this is using my current recursive implementation). I have not found the time to write a good benchmark yet, but from initial tests (20-100 nodes) the results do not look very good. I have tried using a stack-based algorithm instead of recursion, but surprisingly(?!?) it eats up more memory than the recursive version. Probably because I'm storing objects (which is needed) into the stack. I'm interested in hearing about others' experience with MPTT implementations using both the stack-based and recursive approach. Recently, I dug up an article on the ASPN Python Cookbook which implements DOM tree traversal without recursion or node tracking (using stack): http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/461776
From the looks of things, it seems to be much simpler than MPTT and
can be optimized in a number of ways depending on the application specifics. But it also seems to require some changes to the database tables to add support for pointers to a node's parent, first child, and next sibling. -- _nimrod_a_abing_ [?] http://abing.gotdns.com --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Cake PHP" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/cake-php?hl=en -~----------~----~----~----~------~----~------~--~---
