Model Tree Structures with Nested Sets

Overview

This document describes a data model that describes a tree likestructure that optimizes discovering subtrees at the expense of treemutability.

Pattern

The Nested Sets pattern identifies each node in the tree as stops ina round-trip traversal of the tree. The application visits each nodein the tree twice; first during the initial trip, and second duringthe return trip. The Nested Sets pattern stores each tree node in adocument; in addition to the tree node, document stores the id ofnode’s parent, the node’s initial stop in the left field, and itsreturn stop in the right field.

Consider the following hierarchy of categories:

Example of a hierarchical data. The numbers identify the stops at nodes during a roundtrip traversal of a tree.

The following example models the tree using Nested Sets:

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

You can query to retrieve the descendants of a node:

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

The Nested Sets pattern provides a fast and efficient solution forfinding subtrees but is inefficient for modifying the tree structure.As such, this pattern is best for static trees that do not change.