MySQL-Datenbanktabellendesign mit Baumstruktur

Vorwort

Ich habe vor Kurzem Baummenüs studiert und online viele Beispiele gefunden. Nachfolgend einige Informationen, die ich im Internet gefunden und dann selbst noch einmal geübt und aufgezeichnet habe, damit ich sie beim nächsten Mal nicht vergesse.

Beim Programmieren verwenden wir häufig Baumstrukturen, um die Beziehungen zwischen bestimmten Daten darzustellen, z. B. Unternehmensabteilungen, Spaltenstrukturen, Produktkategorien usw. Im Allgemeinen müssen diese Baumstrukturen mithilfe einer Datenbank persistent gespeichert werden. Allerdings zeichnen verschiedene relationale Datenbanken derzeit Dateninformationen in Form zweidimensionaler Tabellen auf und speichern sie, sodass der Baum nicht direkt im DBMS gespeichert werden kann. Das Entwerfen eines geeigneten Schemas und des entsprechenden CRUD-Algorithmus ist der Schlüssel zum Speichern von Baumstrukturen in relationalen Datenbanken.

Eine ideale Baumstruktur sollte die folgenden Eigenschaften aufweisen: geringe Datenspeicherredundanz und starke Intuition, einfacher und effizienter Abruf- und Durchlaufprozess und effiziente CRUD-Operationen (Knoten hinzufügen, löschen, ändern und abfragen). Ich habe im Internet zufällig ein sehr cleveres Design gefunden. Der Originaltext war auf Englisch. Nachdem ich ihn gelesen hatte, fand ich ihn interessant und habe ihn mir angesehen. In diesem Artikel werden zwei Schema-Entwurfsschemata mit Baumstruktur vorgestellt: Das eine ist eine intuitive und einfache Entwurfsidee und das andere ist ein verbessertes Schema basierend auf der linken und rechten Wertekodierung.

1. Basisdaten

Dieser Artikel verwendet ein Beispiel eines Lebensmittelstammbaums, um zu erklären, wie man Lebensmittel nach Kategorie, Farbe und Sorte ordnet. Die Baumstruktur ist wie folgt:

2. Vererbungsbasiertes Design

Die intuitivste Analyse der Baumstruktur ist die Vererbungsbeziehung zwischen Knoten. Durch explizite Beschreibung des übergeordneten Knotens eines Knotens kann eine zweidimensionale Beziehungstabelle erstellt werden. Die Baumtabellenstruktur dieser Lösung wird normalerweise wie folgt gestaltet: {Node_id, Parent_id}. Die obigen Daten können wie in der folgenden Abbildung dargestellt beschrieben werden:

Die Vorteile dieser Lösung liegen auf der Hand: Design und Implementierung sind natürlich, sehr intuitiv und komfortabel. Die Nachteile sind natürlich auch sehr deutlich: Da die Vererbungsbeziehung zwischen Knoten direkt aufgezeichnet wird, ist jede CRUD-Operation am Baum ineffizient. Dies liegt hauptsächlich an häufigen „rekursiven“ Operationen. Der rekursive Prozess greift ständig auf die Datenbank zu, und jede Datenbank-E/A hat einen Zeitaufwand. Natürlich ist diese Lösung nicht ohne Nutzen. Wenn die Größe des Baums relativ klein ist, können wir den Cache-Mechanismus verwenden, um ihn zu optimieren, die Bauminformationen zur Verarbeitung in den Speicher zu laden und den Leistungsaufwand direkter Datenbank-E/A-Vorgänge zu vermeiden.

3. Design basierend auf linker und rechter Wertekodierung

Bei allgemeinen datenbankbasierten Anwendungen ist der Abfragebedarf stets größer als der Lösch- und Änderungsbedarf. Um den „rekursiven“ Prozess beim Abfragen der Baumstruktur zu vermeiden, wird ein neues nicht rekursives Abfrage- und unendlich gruppiertes linkes und rechtes Wertcodierungsschema basierend auf der Vorbestellungsdurchquerung des Baums entwickelt, um die Daten des Baums zu speichern.

Ich glaube, dass den meisten Leuten beim ersten Anblick dieser Tabellenstruktur nicht klar ist, wie der linke Wert (Lft) und der rechte Wert (Rgt) berechnet werden, und dass dieser Tabellenentwurf die Vererbungsbeziehung zwischen übergeordneten und untergeordneten Knoten nicht zu bewahren scheint. Aber wenn Sie mit Ihren Fingern die Zahlen in der Tabelle von 1 bis 18 zählen, sollte Ihnen etwas auffallen. Ja, die Reihenfolge, in der Sie Ihre Finger bewegen, ist die Reihenfolge, in der Sie eine Pre-Order-Traversierung des Baums durchführen, wie in der folgenden Abbildung dargestellt. Wenn wir auf der linken Seite des Wurzelknotens „Food“ beginnen, der als 1 markiert ist, und der Richtung der Vorbestellungsdurchquerung folgen, wobei wir die Zahlen auf dem durchlaufenen Pfad nacheinander markieren, kehren wir schließlich zum Wurzelknoten „Food“ zurück und schreiben 18 auf die rechte Seite.

Basierend auf diesem Design können wir schließen, dass alle Knoten mit linken Werten größer als 2 und rechten Werten kleiner als 11 nachfolgende Knoten von Fruit sind und die Struktur des gesamten Baums durch linke und rechte Werte gespeichert wird. Dies reicht jedoch nicht aus. Unser Ziel ist es, CRUD-Operationen auf dem Baum ausführen zu können, was bedeutet, dass wir entsprechende Algorithmen konstruieren müssen.

4. Baumstruktur-CRUD-Algorithmus

(1) Holen Sie sich die Nachkommenknoten eines Knotens

Es ist nur eine SQL-Anweisung erforderlich, um die Pre-Order-Traversal-Liste der untergeordneten Knoten des Knotens zurückzugeben. Nehmen wir Fruit als Beispiel:

SELECT * FROM tree WHERE lft ZWISCHEN 2 UND 11 ORDER BY lft ASC

Die Abfrageergebnisse lauten wie folgt:

Also, wie viele untergeordnete Knoten hat ein bestimmter Knoten? Durch die linken und rechten Werte des Knotens können wir seine Nachkommenknoten einkreisen. Dann ist die Gesamtzahl der Nachkommen = (rechter Wert – linker Wert – 1)/2. Am Beispiel von Fruit beträgt die Gesamtzahl seiner Nachkommen: (11 –2 – 1)/2 = 4. Gleichzeitig müssen wir, um die Baumstruktur intuitiver darzustellen, die Ebene der Knoten im Baum kennen, was durch SQL-Abfragen der linken und rechten Werte erreicht werden kann. Nehmen wir Fruit als Beispiel: SELECTCOUNT(*) FROM tree WHERE lft <= 2 AND rgt >=11. Zur Vereinfachung der Beschreibung können wir eine Ansicht für Tree erstellen und eine hierarchische Spalte hinzufügen. Der Spaltenwert kann durch Schreiben einer benutzerdefinierten Funktion berechnet werden. Die Funktionsdefinition lautet wie folgt:

Tabelle erstellen

CREATE TABLE `Baum` (
  `id` int(11) NICHT NULL,
  `name` varchar(255) DEFAULT NULL,
  `lft` int(255) DEFAULT NULL,
  `rgt` int(11) STANDARD NULL
)ENGINE=InnoDB STANDARD-CHARSET=utf8;

INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('1', 'Essen', '1', '18');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('2', 'Fruit', '2', '11');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('3', 'Rot', '3', '6');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('4', 'Cherry', '4', '5');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('5', 'Gelb', '7', '10');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('6', 'Banane', '8', '9');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('7', 'Fleisch', '12', '17');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('8', 'Beef', '13', '14');
INSERT INTO `jpa`.`tree` (`id`, `name`, `lft`, `rgt`) VALUES ('9', 'Schweinefleisch', '15', '16');

Erstellen Sie Ansicht `treeview` AS 
WÄHLEN 
  `a`.`id` ALS `id`,
  `a`.`name` ALS `name`,
  `a`.`lft` ALS `lft`,
  `a`.`rgt` ALS `rgt`,
  `CountLayer` (`a`.`id`) AS `Schicht` 
AUS
  `Baum` `a` 

Basierend auf der Ebenenberechnungsfunktion erstellen wir eine Ansicht und fügen eine neue Reihe von Datensätzen der Knotenebenen hinzu:

> FUNKTION „CountLayer“ („node_id“ INT) ERSTELLEN, GIBT INT (11) ZURÜCK 
BEGINNEN
    DECLARE Ergebnis INT (10) DEFAULT 0;
    Erklären Sie lftid INT;
    DECLARE rgtid INT;
    Wählen Sie lft, rgt in lftid, rgtid aus dem Baum, wobei id = node_id ist.
    Wählen Sie "COUNT(*)" aus dem Ergebnis aus dem Baum aus, wobei "lft <= lftid" und "rgt >= rgtid" sind.
    RETURN (Ergebnis);
ENDE

Erstellen Sie eine gespeicherte Prozedur, um alle untergeordneten Knoten und die entsprechenden Ebenen eines bestimmten Knotens zu berechnen:

PROZEDUR `GetChildrenNodeList` erstellen (IN `node_id` INT)
BEGINNEN
Erklären Sie lftid INT;
DECLARE rgtid INT;
Wählen Sie lft,rgt in lftid,rgtid aus dem Baum, wobei id = Knoten-ID ist.
SELECT * FROM treeview WHERE lft ZWISCHEN lftid UND rgtid ORDER BY lft ASC;
ENDE 

Nun verwenden wir die oben gespeicherte Prozedur, um alle untergeordneten Knoten und entsprechenden Ebenen des Knotens Fruit zu berechnen. Die Abfrageergebnisse lauten wie folgt:

Aus der obigen Implementierung können wir erkennen, dass das Designschema mit links- und rechtsseitiger Wertecodierung beim Durchlaufen des Baums nur zwei Datenbankabfragen ausführen muss, wodurch Rekursion vermieden wird. Darüber hinaus sind die Abfragebedingungen alle numerische Vergleiche, sodass die Abfrageeffizienz extrem hoch ist. Da die Baumgröße weiter zunimmt, wird das Designschema basierend auf links- und rechtsseitiger Wertecodierung die Abfrageeffizienz viel stärker verbessern als das herkömmliche rekursive Schema. Natürlich haben wir nur einen einfachen Algorithmus zum Abrufen der Nachkommen eines Knotens angegeben. Um diesen Baum wirklich nutzen zu können, müssen wir Funktionen wie das Einfügen und Löschen von Knoten auf derselben Ebene implementieren.

(2) Den Genealogiepfad eines Knotens ermitteln

Angenommen, wir möchten den Genealogiepfad eines Knotens ermitteln, benötigen wir nur eine SQL-Anweisung, um ihn basierend auf der Analyse der linken und rechten Werte zu vervollständigen. Nehmen wir Fruit als Beispiel: SELECT* FROM tree WHERE lft < 2 AND rgt > 11 ORDER BY lft ASC . Die relativ vollständige gespeicherte Prozedur lautet:

PROZEDUR `GetParentNodePath` erstellen (IN `node_id` INT)
BEGINNEN
Erklären Sie lftid INT;
DECLARE rgtid INT;
Wählen Sie lft,rgt in lftid,rgtid aus dem Baum, wobei id = Knoten-ID ist.
SELECT * FROM Baumansicht WHERE lft < lftid AND rgt > rgtid ORDER BY lft ASC;
ENDE

(3) Fügen Sie einem Knoten untergeordnete Knoten hinzu

Angenommen, wir möchten unter dem Knoten „Rot“ einen neuen untergeordneten Knoten „Apfel“ hinzufügen. Dann sieht der Baum wie in der folgenden Abbildung aus, wobei der rote Knoten der neu hinzugefügte Knoten ist.

PROZEDUR `AddSubNode` ERSTELLEN (IN `node_id` INT, IN `node_name` VARCHAR(64))
BEGINNEN
   DECLARE rgtid INT;
   DECLARE t_error INT DEFAULT 0;  
   DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET t_error=1; – Fehlerbehandlung SELECT rgt INTO rgtid FROM tree WHERE id= node_id; 
   TRANSAKTION STARTEN;
        UPDATE-Baum SET rgt = rgt + 2 WHERE rgt >= rgtid;
        UPDATE-Baum SET lft = lft + 2, wobei lft >= rgtid;
        INSERT INTO Baum (NAME, lft, rgt) WERTE (Knotenname, rgtid, rgtid+1);    
    WENN t_error =1 DANN  
     ROLLBACK;
    ANDERS
      BEGEHEN;
    ENDE, WENN;
ENDE 

(4) Löschen eines Knotens

Wenn wir einen Knoten löschen möchten, werden alle untergeordneten Knoten des Knotens gleichzeitig gelöscht und die Anzahl dieser gelöschten Knoten beträgt: (rechter Wert des gelöschten Knotens – linker Wert des gelöschten Knotens + 1) / 2, und die linken und rechten Werte der verbleibenden Knoten werden angepasst, wenn sie größer als die linken und rechten Werte des gelöschten Knotens sind. Mal sehen, was mit dem Baum passiert. Am Beispiel von Beef ist der Löscheffekt in der folgenden Abbildung dargestellt.

Dann können wir die entsprechende gespeicherte Prozedur konstruieren:

PROZEDUR `DelNode` ERSTELLEN (IN `node_id` INT)
BEGINNEN
   Erklären Sie lftid INT;
     DECLARE rgtid INT;
   DECLARE t_error INT DEFAULT 0;  
   DECLARE CONTINUE HANDLER FOR SQLEXCEPTION SET t_error=1; – Fehlerbehandlung SELECT lft,rgt INTO lftid,rgtid FROM tree WHERE id= node_id;
   TRANSAKTION STARTEN;
       LÖSCHEN AUS Baum, WO lft >= lftid UND rgt <= rgtid;
       UPDATE-Baum SET lft = lft -(rgtid - lftid + 1) WO lft > lftid;
       UPDATE-Baum SET rgt = rgt -(rgtid - lftid + 1) WO rgt >rgtid;
    WENN t_error =1 DANN  
     ROLLBACK;
    ANDERS
      BEGEHEN;
    ENDE, WENN;

ENDE 

V. Fazit

Wir können das Schema-Designschema mit Baumstruktur zusammenfassen, das eine unbegrenzte Gruppierung durch linke und rechte Wertecodierung erreicht:

(1) Vorteile: Es erreicht eine unbegrenzte Gruppierung ohne rekursive Operationen und die Abfragebedingung basiert auf dem Vergleich von Ganzzahlen, was sehr effizient ist.

(2) Nachteile: Das Hinzufügen, Löschen und Ändern von Knoten ist kostspielig und bringt Änderungen an vielen Aspekten der Daten in der Tabelle mit sich.

Verweise

https://www.jb51.net/article/223579.htm