问题标签 [nested-sets]

当我提到嵌套集模型时，我指的是这里描述的内容。

我需要构建一个新系统，用于在用户定义的层次结构中存储“类别”（我想不出更好的词来形容它）。由于嵌套集模型针对读取而不是写入进行了优化，因此我决定使用它。不幸的是，在我对嵌套集的研究和测试过程中，我遇到了如何显示带有排序节点的层次树的问题。例如，如果我有层次结构：

我希望对其进行排序，使其显示为：

请注意，制造出现在研究之前。

无论如何，经过长时间的搜索，我看到了诸如“将树存储在多维数组中并对其进行排序”和“将树重新排序并序列化回您的嵌套集合模型”之类的答案（我在解释......）。无论哪种方式，第一个解决方案都是对 RAM 和 CPU 的可怕浪费，它们都是非常有限的资源……第二个解决方案看起来像是很多痛苦的代码。

无论如何，我能够弄清楚如何（使用嵌套集模型）：

1. 在 SQL 中启动新树
2. 插入一个节点作为树中另一个节点的子节点
3. 在树中的兄弟节点之后插入一个节点
4. 从 SQL 中拉出具有层次结构的整个树
5. 从层次结构中的特定节点（包括根节点）拉取子树，有或没有深度限制
6. 查找树中任何节点的父节点

所以我想#5 和#6 可以用来做我想要的排序，它也可以用来按排序顺序重建树。

然而，现在我已经查看了所有这些我学会做的事情，我发现#3、#5 和#6 可以一起使用来执行排序插入。如果我做了排序插入，它总是被排序。但是，如果我改变了排序标准或者我想要一个不同的排序顺序，我就会回到原点。

这可能只是嵌套集模型的限制吗？它的使用是否会抑制输出的查询排序？

我正在寻找具有所有需要功能的 PHP（使用 MYSQL）嵌套集类。例如：

createLeftNode、createRightNode、createRootNode、createSubNode、deleteNode 和moveTree。不仅是一左一右，一上一下，而且是另一棵树中的一棵树的一部分。

谢谢！

我正在使用嵌套集将树存储在数据库中。该表的字段是 id、lft、rgt 和 name。

给定一个节点 ID，我需要找到它所有的直接子节点（不是孙子节点），它们本身就是叶节点。

我有一个层次结构中的项目列表，我正在尝试将此列表解析为实际的对象层次结构。我正在使用修改后的预排序树遍历来存储/遍历这个列表，所以我拥有的是树的一个子集，包括所有子节点，按它们的“左”值排序。

例如，给定树：

• 项目 A
  • A.1 项
  • A.2 项
    • 项目 A.2.2
• B项
  • B.1 项
• 项目 C

我得到清单：

• 项目 A、项目 A.1、项目 A.2、项目 A.2.2、项目 B、项目 B.1、项目 C

（这是按照修改后的预购树设置中的“左”值的顺序）。

我想要做的是将其解析为包含树的实际结构的对象，例如：

平面列表作为 TreeObject 列表返回 - 每个 TreeObject 都有 ID、ParentID、Left 和 Right 属性。我正在寻找的是一个功能：

它接受平面列表，并返回一个嵌套列表。

换句话说：

我不知道如何做到这一点 - 跟踪父母，并能够处理更大的跳跃（例如，项目 A.2.2 -> 项目 B）。

编辑：我在这里寻找一个非暴力解决方案（例如，不循环多次，将项目移动到子节点，直到只剩下顶级父母）。我猜有一种优雅的方法可以循环一次，然后根据需要放置项目。

请记住，它们总是按层次顺序排列（因为我使用的是 MPTT），因此给定的项目将始终是前一个项目的子项或兄弟姐妹，或者至少与前一个项目共享一个父项。它永远不会出现在树的其他地方。

Joe Celko 的嵌套集（修改的前序遍历）的已知限制之一是随着树增长到较大的大小，性能会显着下降。

Vadim Tropashko 提出了嵌套区间，并在本文中提供了示例和理论解释：http: //arxiv.org/html/cs.DB/0401014

这是一个可行的解决方案吗，是否有任何可行的示例（以任何语言）从本地 DB 层抽象出来？

我正在为我的一个网站构建一个线程评论系统，我遇到了一个问题......

我有一个从具有 ID 字段和父 ID 字段的数据库中提取的列表。父 ID 字段可以为空，但 ID 字段永远不会为空。

由于这将是一个线程评论系统，我将列表组织到 ID 位于顶部的位置，但如果存在父 ID，则它将插入到 ID 下。然后这也可以无限进行。所以第二级现在也有一个 ID，我想在它下面插入任何具有该 ID 的父 ID 的项目。

例如：

---1。废话

--------2。Blah Blah -> ParentID=1

------------ 3。Blah Blah -> parentID=2

-------------- 4. Blah Blah ->parentID=3

----------- 3.Blah Blah -> parentID=2

--------2。Blah Blah -> parentID=1

我认为你说对了。

所以这就是我到目前为止所拥有的......

它似乎对它进行了一半排序，但不是真正的...... ThreadID 当然是它被种植到右边的距离。

我在层次结构中有一组对象。有一个顶部的“根”节点，它具有子节点，子节点又具有子节点等。我正在尝试使用嵌套集模型将此结构保存到数据库中，其中每个节点的每个“边”都被编号以定义层次结构，如在 MySQL 中管理分层数据：

_{（来源：mysql.com）}

我的问题是计算左右值。我通常使用 RecursiveIteratorIterator 来遍历层次结构，但是如果不求助于通过引用解析索引变量的递归函数，我无法弄清楚如何计算数字。

有任何想法吗？

这可能没用，但这是我目前拥有的（不正确的）代码：

如您所见，这将给出如下结果：

左右值：

当他们应该是：

我看过在 MySQL 中管理分层数据，但它实际上只处理在嵌套集模型中添加和删除节点。

我需要能够移动带有和不带有子节点的节点。

我该怎么做？

我希望在我即将进行的一个项目中使用这个概念。

更多信息：在 MySQL 中管理分层数据。

请用例子分享你的经验好坏。

我正在添加更多信息以使其更广泛：

我有可以有多个父项的子项（例如：一个用户可以属于城市，也可以属于一个名为 UserDefinedRegion 的组），典型的分层模型不支持，无论是邻接列表还是嵌套集。

为了清楚起见，我在此处粘贴用例：

背景：目前系统有一个固定的层次结构，即州->县->市->用户

1. 销售经理登录系统并创建一个新组，该组可以与市或县处于同一级别。

2. 销售经理登录系统并创建一个新组，该组可以位于州和县或县和市之间。

3. 一旦销售经理创建了组，他应该能够在第二天在他的仪表板中查看所有必要的报告。

正如你所看到的，第二点可以很容易地通过嵌套集合来完成，但不是第一点，它将为同一个子节点引入新的父节点。

到目前为止，stackOverflow 用户提出了以下解决方案：

1. 网络数据库支持的网络节点结构。
2. 有向无环图。

我肯定在寻找 RDBMS 解决方案。在现实生活中，似乎没有多少人在分层数据模型中遇到多个父节点。

我正在使用嵌套集（又名修改的预排序树遍历）来存储组列表，并且我试图找到一种快速的方法来为所有组生成面包屑（作为字符串，而不是表格）一次。我的数据也使用邻接列表模型存储（有触发器使两者保持同步）。

例如：

代表树：

• 节点 A
  • 节点 B
    • 节点 C
  • 节点 D
    • 节点 E
    • 节点 F

我希望能够有一个返回表的用户定义函数：

为了使这稍微复杂一些（尽管它有点超出了问题的范围），我还有需要遵守的用户限制。例如，如果我只能访问 id=3，当我运行查询时，我应该得到：

我确实有一个用户定义的函数，它以用户 ID 作为参数，并返回一个表，其中包含所有有效组的 ID，只要在查询中的某个位置

它会起作用的。

我有一个现有的标量函数可以做到这一点，但它不适用于任何合理数量的组（2000 个组需要 >10 秒）。它以 groupid 和 userid 作为参数，并返回一个 nvarchar。它找到给定的组父母（1个查询来获取左/右值，另一个查询来查找父母），将列表限制为用户有权访问的组（使用与上面相同的 WHERE 子句，因此还有另一个查询），然后使用游标遍历每个组并将其附加到字符串，最后返回该值。

我需要一种可以快速运行的方法（例如<= 1s），即时运行。

这是在 SQL Server 2005 上。