Modelar estructuras de árbol con conjuntos anidados

Overview

Este documento describe un modelo de datos que describe una estructura similar a un árbol que optimiza el descubrimiento de subárboles a expensas de la mutabilidad del árbol.

Patrón

El patrón Conjuntos anidados identifica cada nodo del árbol como paradas en un recorrido de ida y vuelta del árbol. La aplicación recorre cada nodo en el árbol dos veces; primero durante el viaje inicial y luego durante el viaje de regreso. El patrón de Conjuntos Anidados almacena cada nodo del árbol en un documento; además del nodo del árbol, el documento almacena la ID del padre del nodo, la parada inicial del nodo en el left campo, y su retorno se detiene en el campo right.

Considera la siguiente jerarquía de categorías:

Ejemplo de datos jerárquicos. Los números identifican las paradas en los nodos durante una travesía de ida y vuelta de un árbol.

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.

Volver

Caminos Materializados

Ejemplos de modelos de aplicación