Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 10 of 10
  1. #1
    Senior Coder Nightfire's Avatar
    Join Date
    Jun 2002
    Posts
    4,265
    Thanks
    6
    Thanked 48 Times in 48 Posts

    Which model to base database structure on for a directory

    Hi, I've been reading for a while on different types of database structures, such as adajacency, nested sets, etc and not sure which is the best or ideal to go for.

    The directory I'll be making will be huge, loads of categories and subcategories and subsubcategories, so wanting to keep as much resources free as possible. I read that recursion isn't good for PHP as it keeps it all in the memory (or something like that). Last thing I want is a dead slow site while all the processing is going on.

    What structure would you suggest would be ideal?

  • #2
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    26,561
    Thanks
    80
    Thanked 4,496 Times in 4,460 Posts
    My person favorite is one that I call the "path" method.

    Where, basically, you actually *do* store the full "directory path" for a record in each and every record.

    Except, of course, you do it by ID.

    Example:
    Code:
    id   : parent : name                : path
     1   :      0 : main            : 0001-
     2   :      1 : sub1            : 0001-0002-
     3   :      1 : sub2            : 0001-0003-
     4   :      2 : sub1-ss1        : 0001-0002-0004-
     5   :      2 : sub1-ss2        : 0001-0002-0005-
     6   :      4 : sub1-ss2-sss1   : 0001-0002-0004-0006-
    And now you can do most anything you want using the "path".

    Just for example, you can get all records in usual nested tree order via simply
    Code:
    SELECT * FROM table ORDER BY path
     1   :      0 : main            : 0001-
     2   :      1 : sub1            : 0001-0002-
     4   :      2 : sub1-ss1        : 0001-0002-0004-
     6   :      4 : sub1-ss2-sss1   : 0001-0002-0004-0006-
     5   :      2 : sub1-ss2        : 0001-0002-0005-
     3   :      1 : sub2            : 0001-0003-
    But you can also find all children of *ANY* node/record via something like this:
    Code:
    SELECT t2.* 
    FROM table AS t1, table AS t2
    WHERE t1.id = ###
    AND t2.path LIKE CONCAT( t1.path, '%' )
    ORDER BY t2.path
    If, for example, you substitute in 2 for the ### there, you would get this:
    Code:
     2   :      1 : sub1            : 0001-0002-
     4   :      2 : sub1-ss1        : 0001-0002-0004-
     6   :      4 : sub1-ss2-sss1   : 0001-0002-0004-0006-
     5   :      2 : sub1-ss2        : 0001-0002-0005-
    (To exclude 2, itself, you simply add AND t1.id <> t2.id to the WHERE)

    And you can similarly easily find all parents of any child.

    And so on.

    The trick, I'm sure you can see, is to pad the ID's with zeros (or spaces) all to a constant length when building the PATH. The delimiters (I used dash there) are optional but make it easier for humans to follow. And of course you don't have to just use numbers for the id's and/or you could easily compress the path values. (Though neither is worth it unless you are talking HUGE "trees" and even then...)

    Now...

    The big disadvantage: The system is not good for dynamic trees. Oh, it can be adapted if the tree isn't too dynamic, but it's best for something like a threaded message forum, where messages are added but never removed.

  • #3
    Banned
    Join Date
    Feb 2011
    Posts
    2,699
    Thanks
    13
    Thanked 395 Times in 395 Posts
    I used to use the adjacency list model , which has its disadvantages, for storing hierarchical data in databases but after I read up on and played with the nested set model life became so much easier and I have been using it ever since when required (mainly e-commerce databases)

    Once you get your head around the fact that the left and right values are used to simply store the location of the item in the hierarchy and if you are reasonably skilled in sql then the nested set model is fairly straight forward.

    Deleting nodes and their children becomes very straight forward and moving a node and its children to another location in the hierarchy requires just resetting the left and right values. Adding new nodes wherever you like in the hierarchy is straight forward by just simply adding a record to the table and setting appropriate left and right values to the new node and adjusting the left and right values of the "downstream" nodes accordingly.
    Last edited by bullant; 08-05-2011 at 03:35 AM.

  • #4
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    26,561
    Thanks
    80
    Thanked 4,496 Times in 4,460 Posts
    Yep. If you have a highly dynamic structure, clearly nested set is superior to my "path". But you can't beat "path" for efficiency of queries *IF* you have static data. I do recognize that's a huge "IF".

  • #5
    Banned
    Join Date
    Feb 2011
    Posts
    2,699
    Thanks
    13
    Thanked 395 Times in 395 Posts
    Quote Originally Posted by Old Pedant View Post
    Yep. If you have a highly dynamic structure, clearly nested set is superior to my "path". But you can't beat "path" for efficiency of queries *IF* you have static data. I do recognize that's a huge "IF".
    yep, that's a very big IF.

    Off the top of my head I can't think of a real world situation where a hierarchical data set would always be static and never change.

  • #6
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    26,561
    Thanks
    80
    Thanked 4,496 Times in 4,460 Posts
    Threaded message forums. I first "invented" the technique first time I created a forum. (Of course, I then found out that it had been discussed on SQLTeam.com not more than six months before. Oh, well. Embarrassing.)

    A fully threaded forum is what you typically used to see. I don't know why they aren't popular any more. I grew up on USENET, not surprisingly, which is of course fully threaded; and I really much prefer it to "flat" forums like this one. But maybe there are so many flat forums just because the coders couldn't figure out a good way to write threaded ones. Or maybe most people find threaded forums confusing? Whatever. (See, on a fully threaded forum, people uninterested in this sub-topic would skip the sub-thread. This thing requires people to read every message in a thread.)

    (And there are other situations. Massive Bill-of-Materials kept only for historical purposes. I remember when BOMPs could chew up half the time on old systems with only a few MB of memory. But I'll grant you that static hierarchies are not as common as dynamic, by a long shot.)

  • #7
    Senior Coder Nightfire's Avatar
    Join Date
    Jun 2002
    Posts
    4,265
    Thanks
    6
    Thanked 48 Times in 48 Posts
    Thanks for that

    I looked into the nested set, I think I got my head around it. Just looks a PITA when it comes to adding a new subcategory by having to renumber everything after that again.

    I'll try some experimenting between the ones suggested and see what I find best. Thanks again

  • #8
    Banned
    Join Date
    Feb 2011
    Posts
    2,699
    Thanks
    13
    Thanked 395 Times in 395 Posts
    Quote Originally Posted by Nightfire View Post
    I looked into the nested set, I think I got my head around it. Just looks a PITA when it comes to adding a new subcategory by having to renumber everything after that again.
    Maybe use this quick and simple demo to insert a node as a guide.

    This demo inserts a sub category called "Plastic Plates" below an existing category called "Plates".

    Code:
    SELECT @myRight := fldRgt FROM tblcategory
    WHERE fldCatName = 'Plates';
    
    UPDATE tblcategory SET fldRgt = fldRgt + 2 WHERE fldRgt >= @myRight;
    UPDATE tblcategory SET fldLft = fldLft + 2 WHERE fldLft >= @myRight;
    
    INSERT INTO tblcategory(fldCatName, fldLft, fldRgt) 
    VALUES ('Plastic Plates', @myRight, @myRight + 1);

  • #9
    Senior Coder Nightfire's Avatar
    Join Date
    Jun 2002
    Posts
    4,265
    Thanks
    6
    Thanked 48 Times in 48 Posts
    Oh nice, that made it look much simpler than I thought it would be. Thanks for that

  • #10
    Banned
    Join Date
    Feb 2011
    Posts
    2,699
    Thanks
    13
    Thanked 395 Times in 395 Posts
    you're welcome


  •  

    Posting Permissions

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