[Catalyst]

Tonight while working on a store I had to find the IDs of all the categories under a main category in the store. A store is a pretty normal place to find a data tree, the category/subcategory/sub-subcategory scenario. This is usually done with a table where you've got something like:

categoryid, categoryname, otherstuff, parentid

which is how it's laid out in Zen Cart.

My usual approach would be to use a stored procedure in SQL server to do a recursive function, or maybe do the recursive function in my server side code if necessary. So when I hit this then first thing I did was to Google 'recurse mysql' since I've never done this with the mysql database.

Among the results I found a link to a Sitepoint article on "Modified Preorder Tree Traversal". This uses a different database structure and results in a much easier SQL search and also much better performance than recursion. Check out the article to see how it works:

Storing Hierarchical Data in a Database: Modified Preorder Tree Traversal

Sadly, I can't go changing the Zen Cart database around so it wasn't an option for me, but next time I have to custom build a tree-like database i think I'll give this other method a shot.

[Ben Abrams]

Its an amazing concept, and much more elegant then massive recursive functions.

Once i got over the whole left/right relationship issues in-between the nodes, it became clear how powerful this can be. Clever how you can use a little maths to calculate descendants too, in miniscule coding and resources.

Looking forward to having a play with this concept, i may post the files up for people to see if i get round to it =)

[Catalyst]

Just a quick note on part of how this works faster. Every time you add data to your tree you have to rebuild the left/right indexes, so updating/inserting take a bit of a performance hit - that's where the "preorder" part comes in. But that pays off in a big way when the data is read. Kind of like how compiling is a slow process but results in faster code execution.

[Ben Abrams]

Catalyst, on Nov 16 2007, 04:56 AM, said:

Just a quick note on part of how this works faster. Every time you add data to your tree you have to rebuild the left/right indexes, so updating/inserting take a bit of a performance hit - that's where the "preorder" part comes in. But that pays off in a big way when the data is read. Kind of like how compiling is a slow process but results in faster code execution.

Yeah, so its best to think of it this way:

If your going to use the "levels" more then you will be adding to it (like in say a forum) then use the data tree example, otherwise your best sticking to normal recursion, or some kind of cache.