Speichermethode für Baumdatenstrukturen (Abfrage)

Adjazenzlistenmodell

In der täglichen Geschäftsentwicklung stoßen wir häufig auf baumartige Daten mit einer hierarchischen Struktur. Bei der Speicherung in einer relationalen Datenbank wird diese Datenstruktur oft in einem Modell namens Adjazenzliste gespeichert, etwa so:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `pid` int(11) DEFAULT 0,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

Dieses Modell stellt dar. Das Bild zeigt:

Ich glaube, dass viele Menschen bereits mit diesem Datenmodell vertraut sind, daher werde ich hier nicht zu sehr ins Detail gehen. Konzentrieren wir uns auf das folgende Datenmodell

Nested Set Model

Eine andere Möglichkeit, einen Baum darzustellen, besteht darin, ihn als Menge zu speichern. Wir definieren die folgende Tabellenstruktur neu:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `lft` int(11) NOT NULL UNIQUE CHECK (lft> 0),
  `rgt` int(11) NOT NULL UNIQUE CHECK (rgt> 1),
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

Und das Diagramm dieses Modells sieht wie folgt aus:

lft und rgt werden als Grenze der Menge verwendet. Je größer der Unterschied zwischen den beiden ist, desto größer ist die Menge und desto mehr Elemente enthält sie.

Suchen Sie entsprechend der Teilmenge die Kategorie des übergeordneten Elements.

SELECT c2.* 
  FROM categories as c1, categories as c2
  WHERE c1.lft BETWEEN c2.lft and c2.rgt 
      AND c1.title = '华为';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  5 | Harmony OS  |  10 |  13 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

Suchen Sie entsprechend dem übergeordneten Element alle darunter liegenden Teilmengen.

SELECT c1.*
   FROM categories AS c1, categories AS c2
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
    AND c2.title = 'Smartphones';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  3 | Android     |   2 |   5 |
|  4 | iOS         |   6 |   9 |
|  5 | Harmony OS  |  10 |  13 |
|  6 | 小米        |   3 |   4 |
|  7 | iPhone      |   7 |   8 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

Sehen Sie sich die Ebene jeder Kategorie an.

 SELECT COUNT(c2.id) AS indentation, c1.title
  FROM categories AS c1, categories AS c2下周三we'fv
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
  GROUP BY c1.title
  ORDER BY c1.lft;
+-------------+-------------+
| indentation | title       |
+-------------+-------------+
|           1 | Smartphones |
|           2 | Android     |
|           3 | 小米        |
|           2 | iOS         |
|           3 | iPhone      |
|           2 | Harmony OS  |
|           3 | 华为        |
+-------------+-------------+

Vor- und Nachteile

Adjazenzlistenmodell

Das Adjazenzlistenmodell ist leicht zu verstehen, und der Code, den wir benötigen, ist es auch ganz einfach.

Aber in den meisten Programmiersprachen ist es langsam und ineffizient. Dies wird hauptsächlich durch Rekursion verursacht. Wir müssen für jeden Knoten im Baum eine Datenbankabfrage durchführen.

Dies kann die Funktion bei der Verarbeitung großer Bäume sehr langsam machen, da jede Abfrage einige Zeit in Anspruch nimmt. Denn für jede Funktion ist ein rekursiver Algorithmus erforderlich, um die Zahl zu erhalten.

Wenn Sie eine rekursivfreundliche Sprache wie List verwenden, können Sie die Mängel dieses Datenmodells natürlich ignorieren. Bei PHP wird die gesamte Verarbeitung dieses Datenmodells jedoch extrem langsam.

Nested-Set-Modell

Im Vergleich zum Adjazenzlistenmodell ist dieses Datenmodell offensichtlich nicht so einfach zu verstehen. Und das Hinzufügen von Daten kann nicht so einfach sein. Beim Hinzufügen müssen die Werte auf der linken und rechten Seite berechnet und die nachfolgenden Werte verschoben werden, was den Druck beim Hinzufügen von Daten erhöht.

Der Vorteil besteht auch darin, dass Sie eine Baumabfrage mit einer einfachen Abfrage abschließen können und anhand der beiden Parameter lft und rgt berechnen können, wie viele Unterelemente sie enthält.

Zusammenfassung

Beide Modelle haben ihre eigenen Vor- und Nachteile, eines ist besser als Einfügen und das andere ist besser als Abfrage. Obwohl ich das Nested-Set-Modell bevorzuge, muss es dennoch basierend auf dem jeweiligen Unternehmen ausgewählt werden.

Das obige ist der detaillierte Inhalt vonSpeichermethode für Baumdatenstrukturen (Abfrage). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!