Modified Pre-order Tree Transversal

[eluser]adamp1[/eluser]
I just want to ask has anyone used this method for a database tree? Also how do you get around the problem of having to have a root node? What I mean by this is you can only store a single tree in a database table. This means the root node is pointless.

Here's an example, if I want to store category information for a product database. Using MPTT I would have to have a tree like so:

Code:

Categories
  Fruit
  Chocolate
    Black
    White
  Sweets
    Red
    Yellow

As you can see the root node is totally pointless? So does anyone use this method for storing trees?

[eluser]esra[/eluser]
Using Thunder UK's nested sets contribution on the wiki, the table itself represents the root node, and all node id sets in the hierarchy emanate from the root. To support multiple trees (root nodes) in the same table, try introducing a second table via a foreign key called something like 'trees' (containing just an id and name column). Then your nodes table can support multiple trees by using the trees table id as a foreign key in your queries.

[eluser]Colin Williams[/eluser]
Maybe I'm missing something, but can't you have one 'term' table with term_id | parent_id | name | description? Then, any terms with a parent_id of 0 is a root/vocabulary?

[eluser]esra[/eluser]
[quote author="Colin Williams" date="1202001040"]Maybe I'm missing something, but can't you have one 'term' table with term_id | parent_id | name | description? Then, any terms with a parent_id of 0 is a root/vocabulary?[/quote]

You're referring to the 'adjacency list' model rather than 'modified preorder tree traversal' (mptt) model, also called nested sets. Both are models for allowing a relational database to handle hierarchies.

There are cases where mptt performs better than adjacency list and vice versa. Data retrieval is much faster using mptt but table reconstruction is slower because an entire tree needs to be rebuilt when a tree branch is removed or added. Data retrieval with adjacency list model is slower than mptt, but major changes to the database are faster to update because the changes only affect part of the tree.

Thunder UK's nested sets model class on the wiki should include a link to the original forum thread which contains several pages discussing the merits of using both approaches to handle heirarchies.