Joe Celko covers it in his book SQL for Smarties (along with lots of other useful things). There is also an Intelligent Enterprise article where he discusses it.

The second part of the article actually talks about maintaining the tables as far as deleting sub-trees. And the third part of the article gets into inserting sub-trees. It gets more involved and complex as it goes, but if you are reading more than you are writing, this method seems pretty cool.

if you are reading more than you are writing, this method seems pretty cool.

Actually, most writing functions are easier too ;-) Update operations on subtrees and leaf nodes can usually be implemented in a single SQL statement.

Insertion is really the only vaguely complex/expensive operation - and that's still just three SQL statements in a basic implementation.

The only downside is that inserts can be expensive compared to just storing the parent ID. With the implementation Celko outlined in the article inserting a node is O(N).

Still the average case isn't that bad. You can also make inserts less expensive on average by using increments larger than 1 and inserting in the "gaps" until a global renumbering becomes necessary - but since this makes the selects more complex, and most systems read/update a lot more than they insert, it's rarely worthwhile.

Hrm, that looks interesting, the sql is certainly nice and simple enough, but I have to wonder, how do you maintain it? What happens if, after you've got all your nice lft and rgt columns set up, you want to insert a new node someplace?

It's not hard. There previously mentioned Intelligent Enterprise article covers one possible method. It's worth a read. You can do lots of useful things (aggregate reports, deleting subtrees, etc.) very quickly over in SQL land without having to bring stuff out of the database and munge it into a hierarchy on the Perl side.

After thinking about it for a bit, I think the biggest win is just to store 2 ids, an "ultimate parent" and a "sub parent", then I can just get all my nodes in one query and munge them in to a tree in perl.

This, of course, depends on your definition of "biggest win" ;-)

This way you have to have an id for every level of subtree that you want to refer to which means a change to the DB schema if you change the hierarchy.

Well, the accessing sql is refreshingly simple, but the updating code

BEGIN
DECLARE right_most_sibling INTEGER;

SET right_most_sibling
    = (SELECT rgt
         FROM Personnel
        WHERE emp = :your_boss);

UPDATE Personnel
   SET lft = CASE WHEN lft > right_most_sibling
                  THEN lft + 2
                  ELSE lft END,
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + 2
                  ELSE rgt END
 WHERE rgt >= right_most_sibling;

INSERT INTO Personnel (emp, lft, rgt)
VALUES ('New Guy', right_most_sibling,
                  (right_most_sibling + 1))
END;
[download]

Is rather scary and I'm not even sure my database (mysql) supports those.