Hallo, mein Name ist Anton und ich bin Entwickler. Sohn, den ich geboren habe, das Haus
Was sind verschachtelte Mengen?
Jeder weiß, wie ein Baum in einem Garten wächst, und bei verschachtelten Mengen wächst der Baum folgendermaßen: Für jeden Knoten werden zwei Felder links und rechts gespeichert, sie sind ganze Zahlen. Die Logik hier ist, dass Links kleiner als Rechts ist. Wenn ein Knoten untergeordnete Knoten hat, müssen alle linken und rechten Werte der untergeordneten Knoten zwischen den entsprechenden Werten des übergeordneten Knotens liegen.
Wie sie mit uns wachsen
Wir haben einen separaten Microservice zum Speichern von Hierarchien eingerichtet. Eine Front muss häufig einen vollständigen Baum sowie Teilbäume von Elementen in der Detailansicht zeichnen, während das Einfügen und Verschieben von Elementen relativ selten ist. Für einen solchen Fall sind verschachtelte Mengen perfekt. In einer Tabelle wie dieser gespeichert:
ID ist die Kennung der entsprechenden Entität. Mit dieser ID können Sie vollständige Informationen vom entsprechenden Microservice abrufen. TreeId ist die Kennung des Stammelements. Die Bäume im Projekt sind größtenteils klein, aber es gibt viele von ihnen. EntityFramework wird zum Lesen aus der Datenbank verwendet, die Klasse entspricht eins zu eins der Tabellenstruktur.
Wie man liest
Mit dieser Speichermethode ist es einfach, die Elemente des Teilbaums abzurufen. Wir fordern alle Knoten an, deren Linke größer als die Linke des übergeordneten und die Rechte kleiner ist. Wir überprüfen auch, ob alle Knoten zum selben Baum gehören - anhand der TreeId-Spalte. Dies ist die am häufigsten benötigte Operation und wird schnell ausgeführt. Zum Beispiel so:
dataContext.Nodes.Where(_ =>
_.Left > node.Left &&
_.Right < node.Right &&
_.TreeId == node.TreeId);
Eine weitere häufig ausgeführte Operation besteht darin, alle übergeordneten Knoten eines Objekts zu finden. Auch hier ist es nicht schwierig - wir fordern Baumknoten an, deren Linke kleiner als die Linke des übergeordneten Elements ist und deren Rechte größer ist. Zum Beispiel auf diese Weise:
dataContext.Nodes.Where(_ =>
_.Left < node.Left &&
_.Right > node.Right &&
_.TreeId == node.TreeId);
Wie man neue Zweige wachsen lässt
Kommen wir zum schwierigen Teil - der Transplantation, d.h. Hinzufügen von Knoten oder Verschieben von einem Teilbaum zu einem anderen. Lassen Sie uns herausfinden, wie eine Übertragung durchgeführt wird, weil Diese Operation enthält im Wesentlichen alles, was Sie zum Hinzufügen eines untergeordneten Elements benötigen.
Das erste, was Sie für eine erfolgreiche Einfügung tun müssen, ist, nur eine Einfüge- oder Aktualisierungsoperation zuzulassen. Dazu verwenden wir das Blockieren. Es macht keinen Sinn, die gesamte Tabelle zu sperren, da Knoten nur innerhalb eines Baums navigieren können. Es reicht also aus, nur diesen Baum zu sperren. Führen Sie dazu die folgende SQL-Abfrage aus:
select * from "Nodes" where "TreeId" = <TreeId> for update; Auf diese Weise können wir die Elemente des Baums sofort lesen. Wenn wir jedoch einen Knoten im Baum hinzufügen oder ändern müssen, bei dem eine solche Operation bereits begonnen hat, müssen wir auf den Abschluss der vorherigen warten.
Der nächste Schritt besteht darin, den Ort für die Transplantation vorzubereiten - eine Lücke zwischen links und rechts zu schaffen. Berechnen wir, wie viel Platz benötigt wird - dies ist der Unterschied zwischen rechts und links vom Stammelement des zu verschiebenden Teilbaums. Fügen Sie diesen Unterschied allen untergeordneten Knoten des Knotens hinzu, der zum neuen übergeordneten Knoten wird. Wir können hier eine Ausnahme machen, und hier ist der Grund dafür. Um das Suchen und Lesen in der Tabelle zu beschleunigen, wurden zwei B-Tree-Indizes für das linke und das rechte Feld eingeführt. Wenn Sie die Werte dieser Felder gleichzeitig ändern, kann EntityFramework seitdem einen zirkulären Abhängigkeitsfehler generieren Zwei Indizes können gleichzeitig in einer Zeile neu berechnet werden. Der Fehler ist vom Typ InvalidOperationException mit der folgenden Meldung:
Änderungen können nicht gespeichert werden, da in den zu speichernden Daten eine zirkuläre Abhängigkeit festgestellt wurde: 'Knoten [Geändert] <- Index {' Rechts ',' Baum-ID '} Knoten [Geändert] <- Index {' Links ',' Baum-ID '} Knoten [Geändert] '.
Um herumzukommen, machen wir einfach zwei separate Schleifen - in einer ändern wir Links, in der anderen Rechts, und natürlich speichern wir die Änderungen nach jeder von ihnen.
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();
Ferner das Transplantat selbst - die Übertragungsentfernung entspricht der Differenz zwischen der Linken des neuen Elternteils und der Linken der Wurzel des Teilbaums. Fügen Sie diesen Wert links und rechts von allen Knoten in dem Teilbaum hinzu, den wir verschieben.
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;
Und das Letzte, was Sie tun müssen, ist, die Lücke zu schließen, in die der Teilbaum verschoben wurde. Fordern wir alle Knoten rechts von diesem Teilbaum an - dies sind Elemente, deren Recht größer oder gleich links von der Wurzel des Teilbaums ist, und verschieben Sie sie in den freien Bereich. Subtrahieren Sie dazu von links und rechts von all diesen Knoten den Unterschied zwischen rechts und links von der Wurzel. Auch hier müssen Sie zwei separate Schleifen ausführen:
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();
Fazit
Mal sehen, was gewachsen ist. Wir haben einen Baum mit der Fähigkeit, Kinder und Eltern schnell zu lesen. Wenn Ihr Projekt häufig Daten lesen und Teilbäume abrufen muss, sind verschachtelte Sätze eine gute Wahl. Wir müssen darauf vorbereitet sein, dass es Probleme mit Einfüge- und Aktualisierungsvorgängen geben kann, die jedoch durchaus lösbar sind. Wenn Sie häufig hinzufügen und übertragen müssen, ist es besser, über die Verwendung eines anderen Algorithmus nachzudenken oder einige Hybridoptionen in Betracht zu ziehen. Überkreuzen Sie beispielsweise verschachtelte Mengen und die Adjazenzliste. Dazu müssen Sie in jedem Knoten neben Links und Rechts einen direkten Link zur übergeordneten Elementkennung hinzufügen. Auf diese Weise können Sie schnell in der Hierarchie navigieren und übergeordnete und untergeordnete Knoten finden. Darüber hinaus wird die Zuverlässigkeit des Algorithmus erhöht.