what is the purpose of the 'right' value in a nested tree?

Question

If I'm looking for nested nodes of a parent, I'd query for children like this:

parent.left < child.left

This is always true though:

child.right < parent.right

So why do all examples I've found run a between query?

thanks, Matt

Answer 1

I believe it is only always true for Binary Search Trees (BST), not necessarily all Binary Trees.

Answer 2

If you are talking about the Nested Set Model, then you are incorrect: parent.left < child.left and child.right < parent.right.

So, you can get all of a node's children by querying for node IDs between its left and right IDs.

See Celko's second query in this link:

SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P2.emp = :myemployee;

Answer 3

In a nested set, the hierarchy is described by specifying the left and right boundaries of each node, and all descendant nodes fall within those boundaries. Let's say your hierarchy looks like

A
 - B
 - C
    - D
    - E
 - F
 - G
H
I
 - J

When each row is added to your nested set, you'd end up with a table that looks like:

+----+--------+-----+-----+-----------+
| id | value  | lft | rgt | parent_id |
+----+--------+-----+-----+-----------+
|  1 | A      |   1 |  14 |      NULL |
|  2 | B      |   2 |   3 |         1 |
|  3 | C      |   4 |   9 |         1 |
|  4 | D      |   5 |   6 |         3 |
|  5 | E      |   7 |   8 |         3 |
|  6 | F      |  10 |  11 |         1 |
|  7 | G      |  12 |  13 |         1 |
|  8 | H      |  15 |  16 |      NULL |
|  9 | I      |  17 |  20 |      NULL |
| 10 | J      |  18 |  19 |         9 |
+----+--------+-----+-----+-----------+

Or to look at it another way:

        -D- -E-
  -B- -----C----- --F-- --G--             --J--
---------------A---------------- --H-- -----I-----
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

When you want to query for all descendants of a node (let's say A), you'd query like so:

SELECT *
FROM table AS node
JOIN table AS parent
  ON parent.id = 1
WHERE node.lft BETWEEN parent.lft AND parent.rgt -- BETWEEN 1 AND 14
ORDER BY lft

Since every node's left boundary has to be less than its right boundary, you don't need to check the node's right boundary, but just search for nodes that fall within the parent's boundaries (therefore the right boundary is only needed to determine where the end of the set is). If, for example, you were trying to get the descendants of node C, and only checked against C's left boundary, the query would return nodes that are siblings (F and G), and unrelated (H, I and J) to C.