Materialisierter Pfad in PostgreSQL

PostgreSQL, MaterializedPath

In relationalen Datenbanken ist das Speichern von Informationen in Form von Baumstrukturen eine Aufgabe mit zusätzlichen Overhead-Kosten. Solche zusätzlichen Kosten können sowohl eine Zunahme der Anzahl von Anfragen als auch eine Zunahme der Informationsmenge sein, die der Organisation der Datenstruktur dient.

Gängige Ansätze zum Organisieren von Baumstrukturen sind:

Die Betrachtung dieser Datenstrukturen wurde durch die Notwendigkeit veranlasst, Kommentarunterstützung für Artikel auf der Site zu implementieren.

Adjazenzliste schien mir eine etwas umständliche Lösung für die Organisation von Kommentaren zu sein, da es Probleme beim Auffinden von übergeordneten Objekten und beim Erstellen einer Baumstruktur geben kann, obwohl Sie mit dem Ansatz selbst Elemente ziemlich schnell löschen und hinzufügen können.

Nested Set ist eine ziemlich umständliche Methode, um Kommentare auf einer kleinen Site zu organisieren, und selbst wenn Sie nach großen Ressourcen wie Habr suchen, gibt es nicht so oft 5000 Kommentare unter den Artikeln. Verwirrt hat mich auch die Tatsache, dass es notwendig sein wird, ein verstecktes Wurzelelement hinzuzufügen, den sogenannten ersten leeren Kommentar im Artikel, aus dem der gesamte Baum aufgebaut wird. Warum unnötige Entitäten produzieren? - Obwohl ich mich irren kann. Nun, das letzte Argument "dagegen" war die Notwendigkeit, die Schlüssel beim Hinzufügen neuer Kommentare neu zu berechnen. Im Allgemeinen wird diese Art der Speicherung von Kommentaren trotz der Vorteile dieser Struktur im Rahmen dieser Site und ihres aktuellen Zustands zu Spatzen, die aus einer Kanone feuern.

Aber Materialized Path schien genau das zu sein, was Sie brauchen. Jeder Kommentar enthält den vollständigen Pfad. Und gleichzeitig können unter dem Artikel mehrere Kommentarbäume organisiert werden. Das heißt, jeder Kommentar, der sich auf der ersten Ebene befindet, wird automatisch als Wurzel für seinen Baum betrachtet. Und wenn Sie einen neuen Kommentar hinzufügen, müssen Sie den vollständigen Pfad des zukünftigen übergeordneten Elements übernehmen und ihm nur die ID des neuen Kommentars hinzufügen. Darüber hinaus kann in Bezug auf eine bestimmte Datenbank, und wir sprechen hier von PostgreSQL , der Pfadspeicher als Array von ganzzahligen Werten dargestellt werden, da PostgreSQL Arrays unterstützt (Je mehr ich übrigens Lesen Sie mehr über die Arbeit mit PostgreSQL im Gegensatz zu MySQL , je mehr ich es mag). Und auch beim Abrufen von Kommentarbäumen können Sie nach diesen Arrays sortieren, wodurch Sie automatisch alle Kommentare in chronologischer Reihenfolge unter Beibehaltung der Baumstruktur und dann in der [Django]-Vorlage (https://evileg.com/ru /knowledge/django/ ) bilden die Seite in einer regelmäßigen Schleife ohne Rekursionen, da alle Kommentare bereits durch die Datenbank richtig sortiert werden.

Verwendung in PostgreSQL

Stellen wir uns nun vor, wir haben eine bestimmte abstrakte Seite, die mehrere Kommentare mit der folgenden Struktur enthält:

id | name
-------------------
1  | comment_1
2  |   comment_1_1
3  |     comment_1_1_1
4  |   comment_1_2
5  | comment_2
6  |     comment_2_1
7  |     comment_2_2
8  | comment_3

Als Ergebnis wird die Struktur des Kommentars durch die folgende Anfrage gebildet:

CREATE TABLE comments (
  id serial primary key,
  path integer[] not null,
  content varchar(200) not null
);

Diese Struktur verfügt über eine eindeutige autoinkrementierende Kennung, die auch als eine Art chronologische Kennung angesehen werden kann, da theoretisch ein Kommentar mit einer späteren Zeit nicht vor einem Kommentar mit einer niedrigeren ID in der Datenbank erscheinen kann.

Lassen Sie uns die Datenbank mit Kommentaren füllen:

INSERT INTO comments (path, content) VALUES 
  ('{1}', 'comment_1'),
  ('{1,2}', 'comment_1_1'),
  ('{1,2,3}', 'comment_1_1_1'),
  ('{1,4}', 'comment_1_2'),
  ('{5}', 'comment_2'),
  ('{5,6}', 'comment_2_1'),
  ('{5,7}', 'comment_2_2'),
  ('{8}', 'comment_3');

Als Ergebnis erhalten wir folgende Tabelle:

id | path    | content       
-------------------------
1  | {1}     | comment_1    
2  | {1,2}   | comment_1_1  
3  | {1,2,3} | comment_1_1_1
4  | {1,4}   | comment_1_2
5  | {5}     | comment_2  
6  | {5,6}   | comment_2_1
7  | {5,7}   | comment_2_2
8  | {8}     | comment_3  

Kinder finden

Um untergeordnete Elemente zu finden, müssen Sie den Array-Überlappungsoperator && verwenden. Mit diesem Operator finden wir Elemente, die die ID des übergeordneten Elements in ihrem Pfad enthalten. Wählen wir alle Kinder für das Element mit der ID = 1 aus.

Darüber hinaus können wir alle Elemente in aufsteigender Reihenfolge der Verschachtelung, dh der Pfadlänge, sortieren.

In der Abfrage unten : id = 1 .

SELECT * FROM comments
WHERE path && ARRAY[:id]
ORDER BY array_length(path, 1);

Die Ausgabe wird die folgende Ausgabe sein:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  4 | {1,4}   | comment_1_2
  3 | {1,2,3} | comment_1_1_1
(4 rows)

Übergeordnete Elemente finden

Um eine Liste aller übergeordneten Elemente zu erhalten, wählen Sie alle Elemente aus, die Teil des Pfads des aktuellen Elements sind. Zum Beispiel erhalten wir eine Liste der übergeordneten Elemente eines Kommentars mit ID = 3 , d. h. Kommentar \ _1 \ _1 \ _1.

In der Abfrage unten : id = 3.

SELECT * FROM comments
WHERE id != :id 
AND array[id] && (
  SELECT path 
  FROM comments 
  WHERE id = :id
)
ORDER BY path;

Als Ergebnis erhalten wir folgende Ausgabe:

 id | path  |   content   
----+-------+-------------
  1 | {1}   | comment_1
  2 | {1,2} | comment_1_1
(2 rows)

Elemente hinzufügen

Beim Erstellen eines neuen Datensatzes müssen wir einen Pfad entlang des aktuellen Pfads des übergeordneten Elements bilden, dem die ID des neuen Elements hinzugefügt wird. Fügen wir einen neuen Datensatz mit der ID des übergeordneten Elements gleich 4 hinzu.

In der folgenden Abfrage unten : id = 4.

INSERT INTO comments (content, path)
values (
  'comment_1_2_3', 
  (SELECT path FROM comments WHERE id = :id) || (select currval('comments_id_seq')::integer)
);

Der Operator || verkettet den Pfad des Elternelements mit der ID des neuen Elements. Gleichzeitig müssen wir einen neuen ID-Wert aus der Sequenz comments \ _id \ _seq abrufen, die beim Erstellen der Tabelle automatisch erstellt wird, da der Pfad ein Array vom Typ Integer [ ] und currval geben den Typ biginteger zurück.

Wir erhalten folgende Tabelle:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  5 | {5}     | comment_2
  6 | {5,6}   | comment_2_1
  7 | {5,7}   | comment_2_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(9 rows)

Ein Element löschen

Wir löschen ein Element mit dem Löschen aller untergeordneten Elemente, was auch durch die Überschneidung von Arrays implementiert wird.

Entfernen wir beispielsweise das Element mit der ID gleich 5. ( : id = 5 )

DELETE FROM comments
WHERE path && ARRAY[:id];

Als Ergebnis sieht die Tabelle so aus:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(6 rows)

Element verschieben

Zum Schluss verschieben wir eines der Elemente zusammen mit den Nachkommen in ein anderes Element. Da es nicht viel Auswahl gibt, verschieben wir das Element mit der ID = 2 in das Element mit der ID gleich 8.

Um ein Element in ein anderes zu verschieben, ist es im Allgemeinen erforderlich, den Teil des Pfads, der dem aktuellen Elternteil des gegebenen Elements und allen seinen Kindern entspricht, durch den Pfad zu ersetzen, der dem neuen Elternteil entspricht.

Der einzige knifflige Teil ist, dass das Abrufen der Elementebene das Schreiben einer gespeicherten Prozedur erfordert, die uns hilft, den Umzug in einer einzigen Anforderung durchzuführen. Nennen wir es level und übergeben die ID des Elements, das dorthin verschoben werden soll.

CREATE OR REPLACE FUNCTION level(element_id integer) RETURNS integer AS
$$
DECLARE result integer;
BEGIN
SELECT array_length(path, 1) FROM comments WHERE comments.id = element_id INTO result;
RETURN result;
END
$$ LANGUAGE plpgsql;

Nach Registrierung der gespeicherten Prozedur verwenden wir diese bei der Datenübermittlungsanfrage.

Diese Anfrage enthält:

• : new \ _parent \ _id ist die eindeutige Kennung des zukünftigen Elternteils (Gleich 8);
• : mobile \ _id ist die eindeutige Kennung des beweglichen Gegenstands (Gleich 2).

UPDATE comments
SET path = (
  SELECT path
  FROM comments
  WHERE id = :new_parent_id
) || path[(SELECT level(:movable_id)) : array_length(path, 1)]
WHERE path && ARRAY[:movable_id];

Als Ergebnis erhalten wir eine Tabelle der folgenden Form:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
  2 | {8,2}   | comment_1_1
  3 | {8,2,3} | comment_1_1_1
(6 rows)