Model Tree Structures with Nested Sets¶

Overview概述¶

This document describes a data model that describes a tree like structure that optimizes discovering subtrees at the expense of tree mutability.本文档描述了一个数据模型，该模型描述了一个树状结构，该结构以树的可变性为代价优化发现子树。

Pattern图案¶

The Nested Sets pattern identifies each node in the tree as stops in a round-trip traversal of the tree. 嵌套集模式将树中的每个节点标识为树的往返遍历中的停止点。The application visits each node in the tree twice; first during the initial trip, and second during the return trip. 应用程序访问树中的每个节点两次；第一次是在最初的行程中，第二次是在回程中。The Nested Sets pattern stores each tree node in a document; in addition to the tree node, document stores the id of node’s parent, the node’s initial stop in the left field, and its return stop in the right field.嵌套集模式将每个树节点存储在文档中；除了树节点外，文档还将节点父节点的id、节点的初始停止位置存储在left字段中，其返回停止位置存储在right字段中。

Consider the following hierarchy of categories:考虑以下类别的层次结构：

The following example models the tree using Nested Sets:以下示例使用嵌套集对树进行建模：

db.categories.insertMany( [
   { _id: "Books", parent: 0, left: 1, right: 12 },
   { _id: "Programming", parent: "Books", left: 2, right: 11 },
   { _id: "Languages", parent: "Programming", left: 3, right: 4 },
   { _id: "Databases", parent: "Programming", left: 5, right: 10 },
   { _id: "MongoDB", parent: "Databases", left: 6, right: 7 },
   { _id: "dbm", parent: "Databases", left: 8, right: 9 }
] )

You can query to retrieve the descendants of a node:可以通过查询检索节点的子代：

var databaseCategory = db.categories.findOne( { _id: "Databases" } );
db.categories.find( { left: { $gt: databaseCategory.left }, right: { $lt: databaseCategory.right } } );

The Nested Sets pattern provides a fast and efficient solution for finding subtrees but is inefficient for modifying the tree structure. 嵌套集模式为查找子树提供了快速有效的解决方案，但在修改树结构方面效率低下。As such, this pattern is best for static trees that do not change.因此，这种模式最适合于不变的静态树。