SitePoint Sponsor

User Tag List

Results 1 to 13 of 13
  1. #1
    SitePoint Zealot
    Join Date
    Aug 2003
    Location
    Sydney
    Posts
    187
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Modified preorder tree traversal

    MPTT article

    Has anyone implemented this in their work?

    Im looking at it for a site and just wondering if its worthy? It looks decent enough, just gotto write some good methods for it I guess.

  2. #2
    One website at a time mmj's Avatar
    Join Date
    Feb 2001
    Location
    Melbourne Australia
    Posts
    6,282
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    I looked at it for using in my current project and went with something different. I like the idea of the MPTT/nested sets, but my primary reason for not choosing this was the extra overhead when updating the tree. I went with a solution which stores the path to a node.
    [mmj] My magic jigsaw
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    The Bit Depth Blog Twitter Contact me
    Neon Javascript Framework Jokes Android stuff

  3. #3
    SitePoint Zealot
    Join Date
    Aug 2003
    Location
    Sydney
    Posts
    187
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yeh, well the updates are only like before the site is launched and maybe once in a while whilst the site is up and running so its not much overhead then.

  4. #4
    SitePoint Member
    Join Date
    Mar 2004
    Location
    Russia
    Posts
    2
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    2 ausurt: if updates are quite rare, the method is fine. But if they occur often, it's an overkill. Say, You want to add an item into a 10000 product database and link it to a category. You'll need to recalculate the whole tree to achieve this.

  5. #5
    One website at a time mmj's Avatar
    Join Date
    Feb 2001
    Location
    Melbourne Australia
    Posts
    6,282
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    Getting off topic (sorry)

    The code to insert a node into a tree that uses nested sets is easy. It's the fact that it requires so many rows to be updated that is the drawback.

    For example, if I do this:

    UPDATE nodes SET node_right=node_right+2 WHERE node_right > 3000;
    INSERT INTO nodes (node_ID, node_left, node_right) VALUES (296453, 3000, 3001);

    In this case, inserting a single row in the database involves making a gap for it, then inserting it into that gap. However, making a gap for it, in this case will cause a large number of rows in the table to be updated (linearly relative to the number of rows in the table, or O(n)).

    Of course, this is only an issue with very large tables, but if we are designing for scalability we should always be thinking in terms of very large tables.
    [mmj] My magic jigsaw
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    The Bit Depth Blog Twitter Contact me
    Neon Javascript Framework Jokes Android stuff

  6. #6
    SitePoint Zealot
    Join Date
    Aug 2003
    Location
    Sydney
    Posts
    187
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yes, it does take a while for the update, but as I said this isn't a thing that happens very often.

  7. #7
    SitePoint Member
    Join Date
    Mar 2004
    Location
    MU, Spain
    Posts
    22
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Hi!
    Just a note for you to be taken as an example.
    I've got a simple forum with 96K+ messages in it.
    It is based on Nested Sets approach and uses my own dbtree-library (yeah, I know there's a couple of classes in PEAR to work with db-trees, but I don't use code from PEAR).
    Well, the forum works just perfectly and it doesn't take even a second to add a new message.

  8. #8
    SitePoint Member
    Join Date
    Mar 2004
    Location
    California
    Posts
    6
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    The next version of phpBB (2.2) will be using the MPTT system.

  9. #9
    SitePoint Zealot
    Join Date
    Aug 2003
    Location
    Sydney
    Posts
    187
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    What's the best way to delete?

  10. #10
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    PHP Code:
    mysqldrop database *nameOfDatabase

  11. #11
    SitePoint Zealot
    Join Date
    Jul 2003
    Location
    Los Angeles
    Posts
    199
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by ausurt
    MPTT article

    Has anyone implemented this in their work?

    Im looking at it for a site and just wondering if its worthy? It looks decent enough, just gotto write some good methods for it I guess.
    If you want to see actual code that implements MPTT in a real world albeit alpha stage then just download the phpbb 2.2 CVS at
    http://area51.phpbb.com/cvs/ (look for the 2.1 snapshots since they use a kernel numbering system where 2.1 is unstable, alpha code before 2.2 is ready) Finding a CVS snapshot that actually installs without errors can be challenging but even if it doesn't you can at least look at how they implement MPTT for their unlimited forum system. My cvs version is 6 weeks old and there's a few bugs with moving forums around but otherwise it works pretty well.

  12. #12
    SitePoint Zealot
    Join Date
    Aug 2003
    Location
    Sydney
    Posts
    187
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Ive looked at phpBB CVS and their implementation, it's basic like what I want to do for now.

    Widow Maker, delete one node.

    I found some examples of code when they delete a node in an MPTT situation.

    Thanks everyone.

  13. #13
    Non-Member
    Join Date
    Jan 2004
    Location
    Planet Earth
    Posts
    1,764
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Widow Maker, delete one node.
    I know Was only joking you know


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •