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.嵌套集模式为查找子树提供了一种快速有效的解决方案，但对于修改树结构效率低下。因此，这种模式最适合不变的静态树。