Salut, je m'appelle Anton et je suis développeur. Fils j'ai donné naissance, la maison
Que sont les ensembles imbriqués
Tout le monde sait comment un arbre pousse dans un jardin, et dans le cas des ensembles imbriqués, l'arbre grandit comme ceci: pour chaque nœud, deux champs Gauche et Droite sont stockés, ce sont des entiers. La logique ici est que Left est inférieur à Right, et si un nœud a des enfants, toutes les valeurs Left et Right des nœuds enfants doivent être comprises entre les valeurs correspondantes du parent.
Comment ils grandissent avec nous
Nous avons dédié un microservice séparé pour le stockage des hiérarchies. Fronted doit souvent dessiner un arbre complet ainsi que des sous-arbres d'éléments dans la vue de détail, tandis que l'insertion et le déplacement d'éléments sont relativement rares. Pour un tel cas, les ensembles imbriqués sont parfaits. Stocké dans une table comme celle-ci:
Id est l'identifiant de l'entité correspondante, en l'utilisant, vous pouvez obtenir des informations complètes à partir du microservice approprié. TreeId est l'identifiant de l'élément racine. Les arbres du projet sont pour la plupart petits, mais ils sont nombreux. EntityFramework est utilisé pour lire à partir de la base de données, la classe one-to-one correspond à la structure de la table.
Comment lire
Avec cette méthode de stockage, obtenir les éléments du sous-arbre est simple - nous demandons tous les nœuds dont la gauche est supérieure à la gauche du parent et la droite, respectivement, est inférieure. Nous vérifions également que tous les nœuds appartiennent au même arbre - par la colonne TreeId. Il s'agit de l'opération la plus fréquemment nécessaire et elle est effectuée rapidement. Par exemple, comme ceci:
dataContext.Nodes.Where(_ =>
_.Left > node.Left &&
_.Right < node.Right &&
_.TreeId == node.TreeId);
Une autre opération fréquemment effectuée consiste à trouver tous les nœuds parents d'un objet. Ici aussi, ce n'est pas difficile - nous demandons des nœuds d'arbre dont la gauche est inférieure à la gauche de l'élément parent et la droite, respectivement, est plus grande. Par exemple, de cette manière:
dataContext.Nodes.Where(_ =>
_.Left < node.Left &&
_.Right > node.Right &&
_.TreeId == node.TreeId);
Comment faire pousser de nouvelles branches
Passons à la partie difficile - la transplantation, c'est-à-dire ajouter des nœuds ou passer d'un sous-arbre à un autre. Voyons comment effectuer un transfert, car cette opération comprend essentiellement tout ce dont vous avez besoin pour ajouter un élément enfant.
La première chose à faire pour une insertion réussie est de n'autoriser qu'une seule opération d'insertion ou de mise à jour. Pour ce faire, nous utiliserons le blocage. Cela n'a aucun sens de verrouiller la table entière, car les nœuds ne peuvent naviguer que dans un arbre, il suffit donc de verrouiller uniquement cet arbre. Pour ce faire, exécutez la requête SQL suivante:
select * from "Nodes" where "TreeId" = <TreeId> for update; Cela nous permettra de lire les éléments de l'arbre immédiatement, mais si nous devons ajouter ou modifier un nœud dans l'arbre où une telle opération a déjà commencé, nous devrons attendre que la précédente se termine.
La prochaine étape consiste à préparer l'endroit pour la transplantation - créer un espace entre la gauche et la droite. Calculons l'espace nécessaire - c'est la différence entre la droite et la gauche de l'élément racine du sous-arbre déplacé. Ajoutons cette différence à tous les enfants du nœud qui deviendront le nouveau parent. Nous pouvons attraper Exception ici, et voici pourquoi. Pour accélérer la recherche et la lecture dans la table, deux index B-Tree ont été ajoutés, sur les champs Gauche et Droite, et si vous modifiez les valeurs de ces champs en même temps, EntityFramework peut donner une erreur de dépendance circulaire, car deux indices peuvent être recalculés simultanément sur une ligne. L'erreur sera de type InvalidOperationException avec le message suivant:
Impossible d'enregistrer les modifications car une dépendance circulaire a été détectée dans les données à enregistrer: 'Node [Modified] <- Index {' Right ',' TreeId '} Node [Modified] <- Index {' Left ',' TreeId '} Nœud [Modifié] '.
Pour se déplacer, nous allons simplement faire deux boucles distinctes - dans l'une, nous changerons à gauche, dans l'autre à droite, et, bien sûr, nous enregistrerons les modifications après chacune d'elles.
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();
En outre, la greffe elle-même - la distance de transfert sera égale à la différence entre la gauche du nouveau parent et la gauche de la racine du sous-arbre. Ajoutez cette valeur à gauche et à droite de tous les nœuds du sous-arbre que nous déplaçons.
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;
Et la dernière chose à faire est de fermer l'espace où le sous-arbre a été déplacé. Demandons tous les nœuds à droite de ce sous-arbre - ce seront des éléments dont la droite est supérieure ou égale à la gauche de la racine du sous-arbre, et déplacez-les vers l'espace vide. Pour ce faire, soustrayez à gauche et à droite de tous ces nœuds la différence entre la droite et la gauche de la racine. Ici aussi, vous devez faire deux boucles distinctes:
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();
Conclusion
Voyons ce qui a grandi. Nous avons un arbre avec la capacité de lire rapidement les enfants et les parents. Si votre projet a besoin de lire fréquemment des données et de récupérer des sous-arbres, les ensembles imbriqués sont un excellent choix. Nous devons être préparés au fait qu'il peut y avoir des problèmes avec les opérations d'insertion et de mise à jour, mais ils sont tout à fait résolubles. Si vous devez ajouter et transférer fréquemment, il est préférable de penser à utiliser un autre algorithme ou d'envisager des options hybrides. Par exemple, croisez les ensembles imbriqués et la liste d'adjacence. Pour ce faire, dans chaque nœud, en plus de Left et Right, vous devez ajouter un lien direct vers l'identifiant de l'élément parent. Cela vous permettra de naviguer rapidement dans la hiérarchie et de trouver des nœuds parents et enfants et, de plus, augmentera la fiabilité de l'algorithme.