
Olá, meu nome é Anton e sou desenvolvedor. Filho eu dei à luz, a casa
O que são conjuntos aninhados
Todo mundo sabe como uma árvore cresce em um jardim, e no caso de conjuntos aninhados, a árvore cresce assim: para cada nó, dois campos Esquerda e Direita são armazenados, eles são inteiros. A lógica aqui é que Left é menor que Right e, se um nó tiver filhos, todos os valores de Left e Right dos nós filhos devem estar entre os valores correspondentes do pai.

Como eles crescem conosco
Dedicamos um microsserviço separado para armazenar hierarquias. Fronted frequentemente tem que desenhar uma árvore completa, bem como subárvores de elementos na vista de detalhes, enquanto inserir e mover elementos é relativamente raro. Nesse caso, os conjuntos aninhados são perfeitos. Armazenado em uma tabela como esta:

Id é o identificador da entidade correspondente, usando-o você pode obter informações completas do microsserviço apropriado. TreeId é o identificador do elemento raiz. As árvores do projeto são, em sua maioria, pequenas, mas existem muitas. EntityFramework é usado para ler o banco de dados, a classe um-para-um corresponde à estrutura da tabela.
Como ler
Com esse método de armazenamento, obter os elementos da subárvore é simples - solicitamos todos os nós cuja esquerda seja maior que a esquerda do pai e a direita, respectivamente, seja menor. Também verificamos se todos os nós pertencem à mesma árvore - pela coluna TreeId. Esta é a operação necessária com mais frequência e é executada rapidamente. Por exemplo, assim:
dataContext.Nodes.Where(_ =>
_.Left > node.Left &&
_.Right < node.Right &&
_.TreeId == node.TreeId);
Outra operação realizada com frequência é localizar todos os nós pais de um objeto. Aqui também não é difícil - solicitamos nós da árvore cuja esquerda seja menor que a esquerda do elemento pai e a direita, respectivamente, seja maior. Por exemplo, desta forma:
dataContext.Nodes.Where(_ =>
_.Left < node.Left &&
_.Right > node.Right &&
_.TreeId == node.TreeId);
Como fazer crescer novos ramos
Vamos passar para a parte difícil - transplante, ou seja, adicionar nós ou mover de uma subárvore para outra. Vamos descobrir como fazer uma transferência, porque esta operação inclui essencialmente tudo que você precisa para adicionar um elemento filho.
A primeira coisa a fazer para uma inserção bem-sucedida é permitir apenas uma operação de inserção ou atualização. Para fazer isso, usaremos o bloqueio. Não faz sentido travar a tabela inteira, já que os nós só podem navegar dentro de uma árvore, então é suficiente travar apenas esta árvore. Para fazer isso, execute a seguinte consulta SQL:
select * from "Nodes" where "TreeId" = <TreeId> for update;
Isso nos permitirá ler os elementos da árvore imediatamente, mas se precisarmos adicionar ou alterar um nó na árvore onde tal operação já começou, teremos que esperar que o anterior termine.
O próximo passo é preparar o local para o transplante - criar uma lacuna entre a esquerda e a direita. Vamos calcular quanto espaço é necessário - esta é a diferença entre a direita e a esquerda do elemento raiz da subárvore que está sendo movida. Vamos adicionar essa diferença a todos os filhos do nó que se tornará o novo pai. Podemos capturar a exceção aqui e aqui está o porquê. Para agilizar a busca e leitura na tabela, foram adicionados dois índices B-Tree, nos campos Esquerdo e Direito, e se você alterar os valores desses campos ao mesmo tempo, EntityFramework pode gerar um erro de dependência circular, pois dois índices podem ser recalculados simultaneamente em uma linha. O erro será do tipo InvalidOperationException com a seguinte mensagem:
Não foi possível salvar as alterações porque uma dependência circular foi detectada nos dados a serem salvos: 'Node [Modified] <- Index {' Right ',' TreeId '} Node [Modified] <- Index {' Left ',' TreeId '} Nó [Modificado] '.
Para contornar, vamos apenas fazer dois loops separados - em um vamos mudar para a esquerda, no outro para a direita e, claro, vamos salvar as alterações após cada um deles.
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();
Além disso, o próprio transplante - a distância de transferência será igual à diferença entre a esquerda do novo pai e a esquerda da raiz da subárvore. Adicione este valor à esquerda e à direita de todos os nós na subárvore que estamos movendo.
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;
E a última coisa a fazer é fechar a lacuna onde a subárvore foi movida. Vamos solicitar todos os nós à direita desta subárvore - estes serão os elementos cujo Direito é maior ou igual à Esquerda da raiz da subárvore e movê-los para o espaço livre. Para fazer isso, subtraia da esquerda e da direita de todos esses nós a diferença entre a direita e a esquerda da raiz. Aqui, também, você deve fazer dois loops 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();
Conclusão
Vamos ver o que cresceu. Conseguimos uma árvore com a capacidade de ler rapidamente as crianças e os pais. Se o seu projeto precisa ler dados com frequência e recuperar subárvores, os conjuntos aninhados são uma ótima escolha. Devemos estar preparados para o fato de que pode haver problemas com as operações de inserção e atualização, mas são bastante solucionáveis. Se você precisa adicionar e transferir com frequência, é melhor pensar em usar algum outro algoritmo ou considerar algumas opções híbridas. Por exemplo, conjuntos aninhados cruzados e lista de adjacências. Para fazer isso, em cada nó, além de Esquerdo e Direito, você precisa adicionar um link direto ao identificador do elemento pai. Isso permitirá que você navegue rapidamente na hierarquia e encontre os nós pai e filho e, além disso, aumentará a confiabilidade do algoritmo.