[thelist] [DB Design] Recursive Directory Structure

Mike Migurski mike at saturn5.com
Sat Feb 1 19:47:00 CST 2003


>I want to emulate a directory structure in a database. I don't want to
>have to traverse the filesystem on the server as I'm already making calls
>to the database (prefrences, config, etc). The structure is something
>like this:

<snip>

>If it was a 2-level thing, I could do it with no problem. But I do have
>a problem -- this needs to be n-levels deep. I have no clue how many
>levels this could eventually end up as.

You can do this quite easliy if you approach it as a recursive data
structure. You need to have a way to point one row at another in the same
table (child to parent) and to determine when you've reached home.

You can do both with a table that has two columns, id and parent_id. Id is
the unique identifier of this row, and parent_id is a pointer to another
row's unique identifier.

You need to have a way to determine where to start the hierarchy from, as
well (it's best to do this top-down). You can do that in two ways: have a
particular row's id designate it as the root (call it 'root', or 0, or
'home', or something else you know won't be used elsewhere). Or, you can
have a particular parent_id designate it as an orphan.

The other piece of the puzzle is an accessor function. If you are familiar
with the idea of recursion, this should be cakewalk. If not, here's what
it might look like in pseudocode:

function get_descendent(parent_id)
{
	get children of parent_id
	for each child of parent_id:
		child's descendents = get_descendents(child id)
	return child with descendents
}

If you called it with 'none' or whatever you've determined the base
condition to be, it should give you a beautifully nested array.

If course, the drawback of this is that you can't do it in a single query
- it's an O(log n) operation, and it generates a lot of queries even for a
fairly simple tree.

Your example could be represented in the DB like this:

+------------+------------+
| id         | parent_id  |
+------------+------------+
| beef       | none       |
| hamburger  | beef       |
| steak      | beef       |
| sirloin    | steak      |
| strip      | steak      |
| ribeye     | steak      |
| chicken    | none       |
| sandwiches | chicken    |
| rotisserie | chicken    |
| grilled    | chicken    |
| pork       | none       |
| bacon      | pork       |
| ribs       | pork       |
| chops      | pork       |
+------------+------------+

I'm hungry.

---------------------------------------------------------------------
michal migurski- contact info and pgp key:
                 http://www.saturn5.com/mike/contact.html

                "Freedom! Horrible, horrible freedom!"






More information about the thelist mailing list