1

几年前，我有机会使用 Ruby “nested_set” gem。通过我所在的首席技术专家的一些有用的解释，我能够通过它的专栏了解它是如何工作的：

  • 父母
  • 剩下
  • 正确的

在过去的几年里，我没有机会重新考虑它，但是因为我不经常使用 Rails，但现在我想自己在另一个平台上实现它，将一些数据结构化为树。因此，我正在寻求对其工作原理的有力解释，无论是链接或链接，还是充实的答案。

提前致谢

4

1 回答 1

1

嵌套集类似于邻接列表，但提供了额外的操作，如果父母和孩子只知道他们通过父列的直接连接，则这些操作不容易执行。

例如，如果我们得到以下数据模型：

  Graph                 Table

     A                  node, parent
    / \                  A,
   B   E                 B,   A
  / \                    C,   B
 C   D                   D,   B
                         E,   A

我们可以轻松地检索节点 A 的直接子节点，但棘手的地方是我们是否要确定节点 C 是否在节点 A 的层次结构中，或者我们是否要检索节点 A 的整个树而不仅仅是它的直接子节点。这很棘手，因为节点 C 不是节点 A 的直接子节点，并且不知道树的深度，或者递归查询（对于某些数据库来说不是一个选项），或者某种 SQL 巫术，我们几乎是运气不好。另一个可能会出现问题的例子是，如果我们想要销毁或更新节点 A 树中的每条记录。

除了我们的初始父属性之外，嵌套集还引入了“左”和“右”属性。现在，当插入或修改记录时，节点通过树遍历被访问的时间相对于它们进行了两次编号。将前面的示例与嵌套集一起使用将如下所示：

  +---------------------------+          id, text, lft, rgt
  |             A             |           1, A,    1,   10
  |                           |           2, B,    2,   7
  | +----------------+ +----+ |           3, C,    3,   4
  | |       B        | | E  | |           4, D,    5,   6
  | |                | |    | |           5, E,    8,   9
  | | +----+  +----+ | +----+ |
  | | | C  |  | D  | |        |
  | | |    |  |    | |        |
  | | +----+  +----+ |        |
  | +----------------+        |
  +---------------------------+
  1 2 3    4  5    6 7 8   9  10

通过上面的示例，我们可以确定节点 A 的左右深度分别为 1 和 10，因此其层次结构中的任何内容都将具有介于这两个值之间的左右深度。话虽如此，查询节点 A 的整个树现在变得微不足道：

SELECT c.id, c.text, c.lft, c.rgt FROM nodes c, nodes p WHERE p.lft < c.lft AND p.rgt > c.rgt AND p.id = 1;

给我们：

  id, text, lft, rgt
   2, B,    2,   7
   3, C,    3,   4
   4, D,    5,   6
   5, E,    8,   9

有关源代码，请参阅带有 rails的递归数据结构。正如问题评论中所讨论的，根据您的要求，可能会有更好/更有效的解决方案 - 链接的文章更详细地介绍了这一点。

于 2013-06-05T00:03:31.310 回答