Help with writing a SQL query for Nested Sets

Question

I'm storing a tree in a DB using nested sets. The table's fields are id, lft, rgt, and name.

Given a node ID, I need to find all of its direct children(not grandchildren) that are themselves leaf nodes.

Herv

Answer 1

The article Managing Hierarchical Data in MySQL gives a great example of how to use Nested Sets, and gives examples of many common queries, including this one.

here's how to find the immediate children of a node:

SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
FROM nested_category AS node,
    nested_category AS parent,
    nested_category AS sub_parent,
    (
        SELECT node.name, (COUNT(parent.name) - 1) AS depth
        FROM nested_category AS node,
        nested_category AS parent
        WHERE node.lft BETWEEN parent.lft AND parent.rgt
        AND node.name = '**[[MY NODE]]**'
        GROUP BY node.name
        ORDER BY node.lft
    )AS sub_tree
WHERE node.lft BETWEEN parent.lft AND parent.rgt
    AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
    AND sub_parent.name = sub_tree.name
GROUP BY node.name
HAVING depth = 1
ORDER BY node.lft;

and then combine that with the fact that a leaf node will have rgt equal to lft + 1, and you're set. _{pardon the pun.}

Ozonosphere

The wayback machine has a copy of the article nickf links to. – Impermanent

@Impermanent The article is now on its author's site, I corrected the link in the answer. – Bonis

This requires (or rather assumes) that all nodes have unique names, which they often do not in practice – Cangue

this is also a good nested set article: evanpetersen.com/item/nested-sets.html – Budwig

@Cangue Where is the problem? Just use another field that is unique e.g. the id. – Messalina

Answer 2

We do a lot of development with nested sets in our database. The left and right values of a parent node will always set the boundaries of values for it's children.

To find children of any node using lft and rgt values:

select 
    child.id, 
    child.lft, 
    child.rgt 
from 
    nodes child, 
    nodes parent 
where 
    child.lft between parent.lft and parent.rgt 
    and parent.id != child.id
    and parent.id = [ID];

What we've done here is created an alias to the same table for child and parent, then find the children that fit between the given parent node. the parent.id != child.id gets rid of the redundant entry in the output.

Dagley

This doesn't meet op's requirement: I need to find all of its direct children(not grandchildren) – Cangue

Answer 3

In order to specify and differentiate leaf nodes, keep them with left=right. This changes two things:

1. Leaves are easily identifiable.
2. When doing an insertion, you will add only one to the values (left where > new leaf, right where >= leaf).

Raynell

I don't see how left=right is any better than left=right-1, at least not enough of an improvement to break a principle of nested set design. – Cangue