Depth of Nested Set

Question

I have a large mysql table with parent-child relationships stored in the nested set model (Left and right values).

It makes it EASY to find all the children of a given item.

Now, how do I find the DEPTH of a certain item.

Example of the row:

Parent_ID, Taxon_ID, Taxon_Name, lft, rgt

for somerow(taxon_id) I want to know how far it is from the root node.

NOW it may be important here to note that in the way I have the data structured is that each terminal node (a node with no children of its own) lft = rgt. I know many of the examples posted online have rgt = lft +1, but we decided not to do that just for sake of ease.

Summary: Nested set model, need to find the depth (number of nodes to get to the root) of a given node.

Answer 1

I figured it out.

Essentially you have to query all the nodes that contain the node you are looking for inside. So for example, I was looking at one node that has lft=rgt=7330 and I wanted the depth of it. I just needed to

Select count(*) 
 from table 
 where lft<7330 
 AND   rgt>7330

You may want to add 1 to the result before you use it because its really telling you the number of generations preceding rather than the actual level. But it works and its fast!

Answer 2

MySQL does not support recursive queries. I believe PostgreSQL offers limited support, but it would be inefficient and messy. There is no reason, however, why you couldn't execute queries in a recursive fashion (i.e., programatically) to arrive at the desired result.

If "how deep is this node?" is a question you need answered often, you might consider adjusting the schema of your table so that each node stores and maintains its depth. Then you can just read that value instead of calculating it with awkward recursion. (Maintenance of the depth values may become tedious if you're shuffling the table, but assuming you are doing far fewer writes than reads, this is a more efficient approach.)