Hola, mi nombre es Anton y soy desarrollador. Hijo di a luz, la casa
¿Qué son los conjuntos anidados?
Todo el mundo sabe cómo crece un árbol en un jardín, y en el caso de los conjuntos anidados, el árbol crece así: para cada nodo, se almacenan dos campos Izquierda y Derecha, que son números enteros. La lógica aquí es que Izquierda es menor que Derecha, y si un nodo tiene hijos, entonces todos los valores Izquierda y Derecha de los nodos secundarios deben estar entre los valores correspondientes del padre.
Como crecen con nosotros
Hemos dedicado un microservicio separado para almacenar jerarquías. Fronted a menudo tiene que dibujar un árbol completo, así como subárboles de elementos en la vista de detalle, mientras que insertar y mover elementos es relativamente raro. Para tal caso, los conjuntos anidados son perfectos. Almacenado en una tabla como esta:
Id es el identificador de la entidad correspondiente, usándolo puede obtener información completa del microservicio apropiado. TreeId es el identificador del elemento raíz. Los árboles del proyecto son en su mayoría pequeños, pero hay muchos. EntityFramework se usa para leer de la base de datos, la clase corresponde uno a uno a la estructura de la tabla.
Cómo leer
Con este método de almacenamiento, obtener los elementos del subárbol es simple: solicitamos todos los nodos cuya Izquierda sea mayor que la Izquierda del padre y la Derecha, respectivamente, sea menor. También verificamos que todos los nodos pertenezcan al mismo árbol, mediante la columna TreeId. Esta es la operación que se necesita con más frecuencia y se realiza rápidamente. Por ejemplo, así:
dataContext.Nodes.Where(_ =>
_.Left > node.Left &&
_.Right < node.Right &&
_.TreeId == node.TreeId);
Otra operación que se realiza con frecuencia es encontrar todos los nodos principales de un objeto. Aquí tampoco es difícil: solicitamos nodos de árbol cuya Izquierda sea menor que la Izquierda del elemento principal y la Derecha, respectivamente, sea más grande. Por ejemplo, de esta manera:
dataContext.Nodes.Where(_ =>
_.Left < node.Left &&
_.Right > node.Right &&
_.TreeId == node.TreeId);
Cómo cultivar nuevas ramas
Pasemos a la parte difícil: el trasplante, es decir. agregando nodos o moviéndose de un subárbol a otro. Averigüemos cómo hacer una transferencia, porque esta operación esencialmente incluye todo lo que necesita para agregar un elemento hijo.
Lo primero que debe hacer para una inserción exitosa es permitir solo una operación de inserción o actualización. Para hacer esto, usaremos el bloqueo. No tiene sentido bloquear toda la tabla, ya que los nodos solo pueden navegar dentro de un árbol, por lo que es suficiente bloquear solo este árbol. Para hacer esto, ejecute la siguiente consulta SQL:
select * from "Nodes" where "TreeId" = <TreeId> for update; Esto nos permitirá leer los elementos del árbol de una vez, pero si necesitamos agregar o cambiar un nodo en el árbol, donde tal operación ya ha comenzado, tendremos que esperar a que se complete la anterior.
El siguiente paso es preparar el lugar para el trasplante: cree un espacio entre la izquierda y la derecha. Calculemos cuánto espacio se necesita: esta es la diferencia entre la derecha y la izquierda del elemento raíz del subárbol que se mueve. Agregue esta diferencia a todos los hijos del nodo que se convertirán en el nuevo padre. Podemos detectar Exception aquí, y aquí está el motivo. Para acelerar la búsqueda y lectura en la tabla, se han agregado dos índices B-Tree, en los campos izquierdo y derecho, y si cambia los valores de estos campos al mismo tiempo, EntityFramework puede dar un error de dependencia circular, ya que se pueden volver a calcular dos índices simultáneamente en una línea. El error será de tipo InvalidOperationException con el siguiente mensaje:
No se pueden guardar los cambios porque se detectó una dependencia circular en los datos que se guardarán: 'Nodo [Modificado] <- Índice {' Derecha ',' TreeId '} Nodo [Modificado] <- Índice {' Izquierdo ',' TreeId '} Nodo [Modificado] '.
Para moverse, solo haremos dos bucles separados: en uno cambiaremos a la izquierda, en el otro a la derecha y, por supuesto, guardaremos los cambios después de cada uno de ellos.
var nodesToMove = await dataContext.Nodes
.Where(n =>
n.Right >= parentNodeRight &&
n.TreeId == parentNode.TreeId)
.OrderByDescending(n => n.Right)
.ToListAsync();
foreach (var n in nodesToMove)
{
n.Left += distance;
}
await dataContext.SaveChangesAsync();
foreach (var n in nodesToMove)
{
n.Right += distance;
}
await dataContext.SaveChangesAsync();
Además, el trasplante en sí: la distancia de transferencia será igual a la diferencia entre la izquierda del nuevo padre y la izquierda de la raíz del subárbol. Agregue este valor a la izquierda y derecha de todos los nodos del subárbol que estamos moviendo.
var nodes = await dataContext.Nodes
.Where(n =>
n.Left >= node.Left &&
n.Right <= node.Right &&
n.TreeId == node.TreeId)
.ToListAsync();
foreach (var n in nodes)
{
n.Left += distance;
n.Right += distance;
Y lo último que debe hacer es cerrar la brecha donde se movió el subárbol. Solicitemos todos los nodos a la derecha de este subárbol; estos serán elementos cuyo Derecho sea mayor o igual que el Izquierdo de la raíz del subárbol, y muévalos al espacio libre. Para hacer esto, reste de la izquierda y la derecha de todos estos nodos la diferencia entre la derecha y la izquierda de la raíz. Aquí también tienes que hacer dos bucles separados:
var nodesToMove = await dataContext.Nodes
.Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId)
.ToListAsync();
nodesToMove = nodesToMove
.Where(n => n.Right >= gap.Right)
.OrderBy(n => n.Right)
.ToList();
foreach (var n in nodesToMove)
{
if (n.Left >= gap.Right)
{
n.Left -= distance;
}
}
await dataContext.SaveChangesAsync();
foreach (var n in nodesToMove)
{
n.Right -= distance;
}
await dataContext.SaveChangesAsync();
Conclusión
Veamos qué ha crecido. Conseguimos un árbol con la capacidad de leer rápidamente a niños y padres. Si su proyecto necesita leer datos con frecuencia y recuperar subárboles, los conjuntos anidados son una excelente opción. Debemos estar preparados para el hecho de que puede haber problemas con las operaciones de inserción y actualización, pero son bastante solucionables. Si tiene que agregar y transferir con frecuencia, es mejor pensar en usar algún otro algoritmo o considerar algunas opciones híbridas. Por ejemplo, conjuntos anidados cruzados y Lista de adyacencia. Para hacer esto, en cada nodo, además de Izquierda y Derecha, debe agregar un enlace directo al identificador del elemento principal. Esto le permitirá navegar rápidamente por la jerarquía y encontrar nodos principales y secundarios y, además, aumentará la confiabilidad del algoritmo.