Estruturas de árvore modelo com conjuntos aninhados

Visão geral

Este documento descreve um modelo de dados que descreve uma estrutura semelhante a uma árvore que otimiza a descoberta de subárvores em detrimento da mutabilidade da árvore.

Padrão

O padrão Nested Sets identifica cada nó na árvore como paradas em uma travessia de ida e volta pela árvore. O aplicativo visita cada nó da árvore duas vezes: a primeira durante a volta inicial e a segunda durante o retorno. O padrão Nested Sets armazena cada nó da árvore em um documento; além do nó da árvore, o documento armazena o ID do pai do nó, a parada inicial do nó no campo left e sua parada de retorno no campo right.

Considerar a seguinte hierarquia de categorias:

O exemplo seguinte modela a árvore utilizando 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 }
] )

Você pode fazer query para recuperar os descendentes de um nó:

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

O padrão Nested Sets oferece uma solução rápida e eficiente para localizar subárvores, mas é ineficiente para modificar a estrutura da árvore. Dessa forma, esse padrão é melhor para árvores estáticas que não mudam.