Какова цель правильного значения во вложенном дереве?

Question

Если я ищу вложенные узлы родителя, я бы запросил детей следующим образом:

parent.left

Это всегда так:

child.right

Так почему все примеры, которые я нашел, выполняют запрос между?

спасибо, Matt

Answer 1

Во вложенном наборе иерархия описывается путем указания левой и правой границ каждого узла, и все узлы-потомки попадают в эти границы. Допустим, ваша иерархия выглядит как

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

Когда каждая строка добавляется в ваш вложенный набор, вы получите таблицу, которая выглядит следующим образом:

+----+--------+-----+-----+-----------+
| 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 |
+----+--------+-----+-----+-----------+

Или посмотреть на это по-другому:

        -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

Когда вы хотите запросить всех потомков узла (скажем, A), вы бы запросили так:

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

Поскольку левая граница каждого узла должна быть меньше его правой границы, вам не нужно проверять правую границу узла, а просто искать узлы, которые попадают в границы родителя (поэтому правая граница нужна только для определения где конец набора). Если, например, вы пытались получить потомков узла C и проверяли только по левой границе C, запрос вернул бы узлы, которые являются братьями и сестрами (F и G) и не связаны (H, I и J) до C.

Answer 2

Если вы говорите о Модель вложенного набора , то вы ошибаетесь: parent.left < child.left и child.right < parent.right.

Таким образом, вы можете получить все дочерние узлы, запросив идентификаторы узла между его левым и правым идентификаторами.

См. Второй запрос Celko в этой ссылке :

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

Answer 3

Я считаю, что это всегда верно только для деревьев двоичного поиска (BST), но не обязательно для всех двоичных деревьев.