8

我有一个任意的树结构。

示例数据结构：

root
  |--node1
  |     |--node2
  |     |     |--leaf1
  |     |
  |     |--leaf2
  |
  |--node3
        |--leaf3

每个节点和叶子都有 2 个属性：id和name。

重要查询：

1.:给出了一个叶子 ID。查询应返回从根到该叶的整个路径，以及所有节点id和name属性。

如果返回值是节点的排序数组，或者它是节点嵌套的对象，这并不重要。

示例：如果给出idof leaf2，则查询应返回：root(id, name), node1(id, name), leaf2(id, name)。

2.:给定任何节点id：获取整个（子）树。在这里检索每个节点都有一个children数组的单个对象会很好。

想法、试验和错误：

1.:首先，我尝试将树简单地建模为单个 JSON 文档，但随后查询将变得不可能：无法找出叶子的嵌套级别。如果我知道ids 从根到叶的整个路径，我就不得不使用具有多个位置运算符的投影，而目前 MongoDB 不支持。此外，无法索引叶子ids，因为嵌套可以是无限的。

2.:下一个想法是使用平面数据设计，其中每个节点都有一个包含节点祖先的数组ids：

{
  id: ...,
  name: ...,
  ancestors: [ rootId, node1Id, ... ]
}

这样，我必须进行 2 次查询，以获取从根到某个节点或叶的整个路径，这非常好。

问题：

如果我选择数据模型2.：如何获得整个树或子树？

获取所有后代很容易：find({ancestors:"myStartingNodeId"}). 但是这些当然不会被排序或嵌套。

有没有办法使用聚合框架或完全不同的数据模型来解决这个问题？

谢谢！

4

3 回答 3

4

MongoDB不是图数据库，不提供图遍历操作，所以没有直接的解决方案。

您可以使用第 2 点中描述的数据模型。（具有祖先列表的节点）、查询find({ancestors:"myStartingNodeId"})和排序/嵌套应用程序代码中的结果。

另一种可能性是使用数据模型，其中_id（或其他一些字段）表示完整路径，例如'root.node1.node2'。然后图形查询可以转换为子字符串查询，并且可以通过排序来实现正确的排序（我希望） this _id。

更新：顺便说一句。MongoDB 文档中描述了一些树结构模式：Model Tree Structures in MongoDB

于 2015-07-25T22:51:56.633 回答
4

这是我最终想出的数据结构。它针对读取查询进行了优化。一些写查询（如移动子树）可能很痛苦。

{
  id: "...",
  ancestors: ["parent_node_id", ..., "root_node_id"], // order is important!
  children: ["child1_id", "child2_id", ...]
}

好处：

  • 轻松获取子树的所有文档

  • 轻松将所有文档从某个节点获取到根

  • 易于检查某个文档是否是某个节点的父/子/祖先/后代

  • 孩子们被分类。可以通过更改children数组顺序轻松移动

如何使用它：

  • 通过 ID 获取：findOne({ id: "..." })

  • 获取家长：findOne({ children: "..." })

  • 获取所有祖先：首先通过 ID 获取，然后获取祖先数组并查找与给定 ID 列表匹配的所有文档

  • 获取所有孩子：find({ 'ancestors.0': "..." })

  • 获取所有后代：find({ ancestors: "..." })

  • 获取最多x代的所有后代：find({ $and: [ {ancestors: "..."}, {ancestors: {$size: x}} ] })

缺点：

  • 应用程序代码必须注意正确的顺序。

  • 应用程序代码必须构建嵌套对象（也许这可以使用 MongoDB 聚合框架）。

  • 每个都insert必须使用 2 个查询来完成。

  • 在节点之间移动整个子树必须更新大量文档。

于 2016-12-14T19:15:55.487 回答
2

您可以使用graphLookup

文档： https ://docs.mongodb.com/manual/reference/operator/aggregation/graphLookup/

于 2019-10-01T15:20:03.673 回答