Model Tree Structures with an Array of Ancestors

Overview

This page describes a data model that describes a tree-likestructure in MongoDB documents using references to parent nodes and an array that storesall ancestors.

Pattern

The Array of Ancestors pattern stores each tree node in a document;in addition to the tree node, document stores in an array the id(s) ofthe node’s ancestors or path.

Consider the following hierarchy of categories:

The following example models the tree using Array of Ancestors. Inaddition to the ancestors field, these documents also store thereference to the immediate parent category in the parent field:

db.categories.insert( { _id: "MongoDB", ancestors: [ "Books", "Programming", "Databases" ], parent: "Databases" } )
db.categories.insert( { _id: "dbm", ancestors: [ "Books", "Programming", "Databases" ], parent: "Databases" } )
db.categories.insert( { _id: "Databases", ancestors: [ "Books", "Programming" ], parent: "Programming" } )
db.categories.insert( { _id: "Languages", ancestors: [ "Books", "Programming" ], parent: "Programming" } )
db.categories.insert( { _id: "Programming", ancestors: [ "Books" ], parent: "Books" } )
db.categories.insert( { _id: "Books", ancestors: [ ], parent: null } )

• The query to retrieve the ancestors or path of a node is fast andstraightforward:

db.categories.findOne( { _id: "MongoDB" } ).ancestors

• You can create an index on the field ancestors to enable fastsearch by the ancestors nodes:

db.categories.createIndex( { ancestors: 1 } )

• You can query by the field ancestors to find all its descendants:

db.categories.find( { ancestors: "Programming" } )

The Array of Ancestors pattern provides a fast and efficient solutionto find the descendants and the ancestors of a node by creating anindex on the elements of the ancestors field. This makes Array ofAncestors a good choice for working with subtrees.

The Array of Ancestors pattern is slightly slower than theMaterialized Paths pattern butis more straightforward to use.