Estruturas de árvore modelo com conjuntos aninhados
Nesta página
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.