Generate breadcrumbs of categories stored in MySQL

Question

In MySQL, I store categories this way:

categories: - category_id - category_name - parent_category_id

What would be the most efficient way to generate the trail / breadcrumb for a given category_id?

For example breadcrumbs(category_id): General > Sub 1 > Sub 2

There could be in theories unlimited levels. I'm using php.

UPDATE: I saw this article (http://dev.mysql.com/tech-resources/articles/hierarchical-data.html) about the Nested Set Model. It looks interesting, but how would you ago about dynamically managing categories? It looks easier on paper, like when you know ahead of times the categories, but not when the user can create/delete/edit categories on the fly ... What do you think?

Answer 1

Generate it (however you like) from a traditional parent model and cache it. It's too expensive to be generating it on the fly and the changes to the hierarchy are usually several orders of magnitude less frequent than other changes ever are. I wouldn't bother with the nested sets model since the hierarchy will be changing and then you have to go fooling around with the lefts and rights. (Note that the article only included recipes for adding and deleting - not re-parenting - which is very simple in the parent model).

Answer 2

I like to use the Materialized Path method, since it essentially contains your breadcrumb trail, and makes it easy to do things like select all descendants of a node without using recursive queries.

Answer 3

The beauty of nested sets is that you can easily add/remove nodes from the graph with just a few simple SQL statements. It's really not all that expensive, and can be coded pretty quickly.

If you happen to be using PHP (or even if you don't), you can look at this code to see a fairly straight-forward implementation of adding nodes to a nested set model. Removing (or even moving) is similarly straightforward.