As title says: How do I calculate a node's depth in a parent-child model? I'll need the depth to, among other things, create the indent in my list (coded with PHP).
Thank you in advance.
A:
That depends on the actual implementation of your hierarchy in the database. If you are using nested sets model (http://dev.mysql.com/tech-resources/articles/hierarchical-data.html) you can retrieve the full parent-to-child path via a single select.
Update: Ok, since you're going with adjacency list model I suggest to store node level in the table. Not only will it give you the node depth in one query, but it will also allow you to retrieve the entire path to that node in one query (albeit that query would have to be dynamically generated):
SELECT n1.name AS lvl1, n2.name as lvl2, n3.name as lvl3, ..., nN.name as lvlN
FROM nodes AS n1
JOIN nodes AS n2 ON n2.parent_id = n1.id
JOIN nodes AS n3 ON n3.parent_id = n2.id
...
JOIN nodes AS nN ON nN.parent_id = n(N-1).id
WHERE nN.id = myChildNode;
Since you know that your node is on level N there's no need for left joins and, given appropriate indexes on id / parent_id this should be reasonably fast.
The downside to this approach is that you'll have to keep node level updated during node moves, but that should be reasonably straightforward and fast as you would only do it for the node itself and its children - not for the majority of the table as you would do with nested sets.
ChssPly76
2009-07-28 18:33:46
Yeah, I've worked with nested sets and knows how to calculate the depth there, but now I need the depth from a parent-child model (obviously with just the columns id and parent), not nested set.
Ivarska
2009-07-28 18:37:51
By the way, it's the depth I'm interested of (an integer), not the path.
Ivarska
2009-07-28 18:42:07
You're talking about adjacency list model then. It's far from ideal, unfortunately - you will need N selects in order to fund out the depth of node on the Nth level.
ChssPly76
2009-07-28 18:43:29
Okay, so you'd suggest me to add another column to the table named depth? But I can't see you use it in your example. And in this case, would it be safe? I'd prefer a fast system that doesn't change multiple rows if possible. :)
Ivarska
2009-07-28 20:47:34
In my example, the depth is N and you're generating a single query with N joins. Without knowing depth in advance you will have to execute N queries to do the same thing. If you happen to know maximum possible depth of your entire hierarchy (e.g. it can't have more than X levels), another possible compromise is to rewrite the above query using X outer joins. It won't perform that well, but you won't have to keep node level for each node.
ChssPly76
2009-07-28 21:03:50