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 una parada en un recorrido de ida y vuelta. La aplicación visita cada nodo dos veces: la primera durante el recorrido inicial y la segunda durante el de regreso. El patrón Conjuntos Anidados almacena cada nodo del árbol en un documento; además del nodo del árbol, el documento almacena el ID del padre del nodo y su parada inicial en el... left campo, y su retorno se detiene en el campo right.

Considere la siguiente jerarquía de categorías:

Ejemplo de datos jerárquicos. Los números identifican las paradas en los nodos durante un recorrido 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 realizar consultas 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 ofrece 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 ideal para árboles estáticos que no cambian.

Volver

Caminos materializados

Ejemplos de modelos de aplicación