SELECT an arbitrarily deep tree that is represented by the adjacency list model in mysql?

Question

In mysql, I have a tree that is represented using the adjacency list model.

MYTREE
   id
   parent_id
   title

I am wondering:

Given the id of a node, is there any way to SELECT the entire tree beneathe that node, complete with depth information? The tree is arbitrarily deep, so I cannot say how many levels there may be. But the resultset might look something like this:

ID      TITLE     DEPTH
4       title1    1
8       title2    2
16      title8    3
9       title3    2
15      title4    3

I know that it is possible to do this using the nested sets model. But there are things about nested sets that are not ideal, and I'm hoping not to have to switch over.

Thanks for the advice!

Answer 1

Short answer: no.

The only way to traverse a tree represented with parent pointers is to follow one set of parent IDs after the next. That's possible if you can limit the depth, by simply joining that many times across the table, but with an unlimited depth an application-side loop is generally the way to go.

Answer 2

EDIT: I didn't notice the arbitrarily deep clause in the title:

You could write a Stored Procedure to recurse over the rows.

But what's not ideal about Nested Sets (at least that couldn't be taken care of by a before insert trigger or a stored procedure)?

Answer 3

Here is a blog post I wrote about one way to approach this problem:

http://nathansnoggin.blogspot.com/2009/10/storing-tree-structure-in-database.html