“权利”的目的是什么？嵌套树中的值？

Question

如果我正在寻找父节点的嵌套节点，我会像这样查询子节点：

parent.left < child.left

这始终是正确的：

child.right < parent.right

那么为什么我发现的所有示例都运行 Between 查询？

谢谢， 马特

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

我相信这只适用于二叉搜索树（BST），不一定适用于所有二叉树。

Answer 3

如果您正在谈论嵌套集模型，那么您是错误的：parent。左< child.left 和 child.right <父.right。

因此，您可以通过查询左右 ID 之间的节点 ID 来获取该节点的所有子节点。

请参阅 此链接中的 Celko 的第二个查询：

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