Overview
Este documento describe un modelo de datos que describe una estructura de árbol que optimiza el descubrimiento de subárboles a expensas de la mutabilidad del árbol.
Patrón
El patrón de Conjuntos Anidados identifica cada nodo en el árbol como paradas en un recorrido de ida y vuelta del árbol. La aplicación visita cada nodo en el árbol dos veces; primero durante el viaje inicial, y segundo durante el viaje de regreso. El patrón de Conjuntos Anidados almacena cada nodo de árbol en un documento; además del nodo de árbol, el documento almacena la ID del padre del nodo, la parada inicial del nodo en el campo left, y su parada de retorno en el campo right.
Considera la siguiente jerarquía de categorías:
El siguiente ejemplo modela el árbol utilizando Conjuntos anidados:
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 } ] )
Puedes query para recuperar los descendientes de un nodo:
var databaseCategory = db.categories.findOne( { _id: "Databases" } ); db.categories.find( { left: { $gt: databaseCategory.left }, right: { $lt: databaseCategory.right } } );
El patrón conjuntos anidados proporciona una solución rápida y eficiente para encontrar subárboles, pero es ineficiente para modificar la estructura del árbol. Por lo tanto, este patrón es el mejor para árboles estáticos que no cambian.