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.因此，这种模式最适合于不变的静态树。