Building breadcrumbs for unlimited category depth - PHP + SQL

I'd like to be able to build the breadcrumbs for a content page, however the categories a piece of content is in can have unlimited depth, so i'm not sure how to go about it without getti开发者_如何学JAVAng each category one by one and then getting its parent etc. It seems like it could be a simpler way but I can't figure it out.

I have an articles table

article_id
article_name
article_cat_id

I also have a categories table

cat_id
cat_name
cat_parent

Cat parent is the id of another category of which a category is a child.

Imagine an article which is 5 categories deep, as far as I can tell i'd have to build the breadcrumbs something like this (example code obviously inputs should be escaped etc)

<?php
$breadcrumbs = array(
    'Category 5',
    'Content Item'
);
$cat_parent = 4;

while($cat_parent != 0) {
    $query = mysql_query('SELECT * FROM categories WHERE cat_id = '.$cat_parent);
    $result = mysql_fetch_array($query, MYSQL_ASSOC);
    array_unshift($breadcrumbs, $result['cat_name']);
    $cat_parent = $result['cat_parent'];
}
?>

This would then give me

array(
'Category 1',
'Category 2',
'Category 3',
'Category 4',
'Category 5',
'Content Item'
)

Which I can use for my breadcrumbs, however its taken me 5 queries to do it, which isn't really preferable.

Can anyone suggest any better solutions?

---

Here are some easy options in order of simplicity:

1. Stick with the design you have, use the recursive/iterative approach and enjoy the benefits of having simple code. Really, this will take you pretty far. As a bonus, it is easier to move from here to something more performant, than from a more complicated setup.

2. If the nr of categories isn't very large, you can select all of them and build the hierarchy in PHP. Due to pagesize the amount of work required to fetch 1 rows vs a whole bunch of them (say a few hundred) is pretty much the same. This minimizes the nr of queries/network trips, but increases the amount of data transported over the cable. Measure!

3. Cache the hierarchy and reload it entirely every X unit of time or whenever categories are added/modified/deleted. In it's simplest form, the cache could be a PHP file with a nested variable structure containing the entire category hierarchy, along with a simple index for the nodes.

4. Create an additional table in which you have flattened the hierarchy in some way, either using nested sets, path enumeration, closure table etc. The table will be maintained using triggers on the category table.

I would go for (1) unless you are fairly certain that you will have a sustained load of several users per second in the near future. (1 user per second makes 2,5 million visits a month).

There is nothing wrong with simple code. Complicating code for a speedup that isn't noticable is wrong.

---

There are two commonly used methods of handling hierarchal data in relational databases: the adjacency list model and nested set model. Your schema here is currently following the adjacency list model. Check out this page for some example queries. See also this question here on SO with a lot of good information.