Finde die Knotenebene in einem tree

Ich habe einen tree (verschachtelte Kategorien) wie folgt gespeichert:

CREATE TABLE `category` ( `category_id` int(10) unsigned NOT NULL AUTO_INCREMENT, `category_name` varchar(100) NOT NULL, `parent_id` int(10) unsigned DEFAULT NULL, PRIMARY KEY (`category_id`), UNIQUE KEY `category_name_UNIQUE` (`category_name`,`parent_id`), KEY `fk_category_category1` (`parent_id`,`category_id`), CONSTRAINT `fk_category_category1` FOREIGN KEY (`parent_id`) REFERENCES `category` (`category_id`) ON DELETE SET NULL ON UPDATE CASCADE ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_spanish_ci 

Ich muss meine clientseitige Sprache (PHP) mit Knoteninformationen (Kind + Eltern) füttern, damit sie den tree im memory erstellen können. Ich kann meinen PHP-Code optimieren, aber ich denke, die Operation wäre viel einfacher, wenn ich die Zeilen einfach in einer Reihenfolge abrufen könnte, in der alle Eltern vor ihren Kindern stehen. Ich könnte das tun, wenn ich das Level für jeden Knoten kenne:

 SELECT category_id, category_name, parent_id FROM category ORDER BY level -- No `level` column so far :( 

Können Sie sich einen path vorstellen (view, gespeicherte Routine oder was auch immer …), um die Knotenebene zu berechnen? Ich denke, es ist in Ordnung, wenn es nicht in Echtzeit ist und ich es bei Knotenmodifikation neu berechnen muss.

Erste Aktualisierung: Bisherige Fortschritte

Ich habe diese Auslöser basierend auf Feedback von Amarghosh geschrieben:

 DROP TRIGGER IF EXISTS `category_before_insert`; DELIMITER // CREATE TRIGGER `category_before_insert` BEFORE INSERT ON `category` FOR EACH ROW BEGIN IF NEW.parent_id IS NULL THEN SET @parent_level = 0; ELSE SELECT level INTO @parent_level FROM category WHERE category_id = NEW.parent_id; END IF; SET NEW.level = @parent_level+1; END// DELIMITER ; DROP TRIGGER IF EXISTS `category_before_update`; DELIMITER // CREATE TRIGGER `category_before_update` BEFORE UPDATE ON `category` FOR EACH ROW BEGIN IF NEW.parent_id IS NULL THEN SET @parent_level = 0; ELSE SELECT level INTO @parent_level FROM category WHERE category_id = NEW.parent_id; END IF; SET NEW.level = @parent_level+1; END// DELIMITER ; 

Es scheint für Insertionen und Modifikationen gut zu funktionieren. Es funktioniert jedoch nicht für Löschungen: MySQL server startet keine Trigger, wenn die Zeilen von ON UPDATE CASCADE Fremdschlüsseln aktualisiert werden.

Die erste naheliegende Idee ist, einen neuen Auslöser zum Löschen zu schreiben; Ein Trigger für Tabellenkategorien darf jedoch keine anderen Zeilen in derselben Tabelle ändern:

 DROP TRIGGER IF EXISTS `category_after_delete`; DELIMITER // CREATE TRIGGER `category_after_delete` AFTER DELETE ON `category` FOR EACH ROW BEGIN /* * Raises an error, see below */ UPDATE category SET parent_id=NULL WHERE parent_id = OLD.category_id; END// DELIMITER ; 

Error:

Fehler beim Bearbeiten des Rasters: SQL Error (1442): Tabelle 'category' in gespeicherter function / Trigger kann nicht aktualisiert werden, da sie bereits von einer statement verwendet wird, die diese gespeicherte function / diesen Trigger aufgerufen hat.

Zweites Update: Arbeitslösung (sofern nicht falsch bewiesen)

Mein erster Versuch war ziemlich vernünftig, aber ich fand ein Problem, das ich nicht lösen konnte: Wenn Sie eine Reihe von Operationen von einem Trigger starten, wird es MySQL nicht erlauben, andere Zeilen aus der gleichen Tabelle zu ändern. Da Knotenlöschungen das Niveau aller Nachkommen anpassen müssen, habe ich eine Wand getroffen.

Am Ende änderte ich den Ansatz mit Code von hier : anstatt einzelne Ebenen zu korrigieren, wenn sich ein Knoten ändert, habe ich Code, um alle Ebenen zu berechnen, und ich trigge ihn bei jeder Änderung an. Da es eine langsame Berechnung ist und das Abrufen von data eine sehr komplexe Abfrage erfordert, cache ich sie in einer Tabelle. In meinem Fall ist es eine akzeptable Lösung, da Editionen selten sein sollten.

1. Neue Tabelle für Cache-Ebenen:

 CREATE TABLE `category_level` ( `category_id` int(10) NOT NULL, `parent_id` int(10) DEFAULT NULL, -- Not really necesary `level` int(10) NOT NULL, PRIMARY KEY (`category_id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_spanish_ci 

2. Helper-function zum Berechnen von Ebenen

Wenn ich wirklich verstanden habe, wie es funktioniert, gibt es nichts wirklich nützliches zurück. Stattdessen speichert es Dinge in sessionsvariablen.

 CREATE FUNCTION `category_connect_by_parent_eq_prior_id`(`value` INT) RETURNS int(10) READS SQL DATA BEGIN DECLARE _id INT; DECLARE _parent INT; DECLARE _next INT; DECLARE CONTINUE HANDLER FOR NOT FOUND SET @category_id = NULL; SET _parent = @category_id; SET _id = -1; IF @category_id IS NULL THEN RETURN NULL; END IF; LOOP SELECT MIN(category_id) INTO @category_id FROM category WHERE COALESCE(parent_id, 0) = _parent AND category_id > _id; IF @category_id IS NOT NULL OR _parent = @start_with THEN SET @level = @level + 1; RETURN @category_id; END IF; SET @level := @level - 1; SELECT category_id, COALESCE(parent_id, 0) INTO _id, _parent FROM category WHERE category_id = _parent; END LOOP; END 

3. Prozedur zum Starten des Neuberechnungsprozesses

Es kapselt im Wesentlichen die komplexe Abfrage ein, die die von der Hilfsfunktion unterstützten Ebenen abruft.

 CREATE PROCEDURE `update_category_level`() SQL SECURITY INVOKER BEGIN DELETE FROM category_level; INSERT INTO category_level (category_id, parent_id, level) SELECT hi.category_id, parent_id, level FROM ( SELECT category_connect_by_parent_eq_prior_id(category_id) AS category_id, @level AS level FROM ( SELECT @start_with := 0, @category_id := @start_with, @level := 0 ) vars, category WHERE @category_id IS NOT NULL ) ho JOIN category hi ON hi.category_id = ho.category_id; END 

4. Löst aus, die Cache-Tabelle auf dem neuesten Stand zu halten

 CREATE TRIGGER `category_after_insert` AFTER INSERT ON `category` FOR EACH ROW BEGIN call update_category_level(); END CREATE TRIGGER `category_after_update` AFTER UPDATE ON `category` FOR EACH ROW BEGIN call update_category_level(); END CREATE TRIGGER `category_after_delete` AFTER DELETE ON `category` FOR EACH ROW BEGIN call update_category_level(); END 

5. Bekannte Probleme

  • Es ist ziemlich suboptimal, wenn Knoten häufig geändert werden.
  • MySQL erlaubt keine transactions oder Sperren von Tabellen in Triggern und Prozeduren. Sie müssen sich um diese Details kümmern, wenn Sie Knoten bearbeiten.

Solutions Collecting From Web of "Finde die Knotenebene in einem tree"

Hier gibt es eine exzellente Reihe von Artikeln über hierarchische Abfragen in MySQL , die die Identifizierung von Ebenen, Blattknoten, loops in der Hierarchie usw. umfassen.

Wenn es keine Zyklen gibt (wenn es immer ein tree und kein Diagramm wäre), können Sie standardmäßig ein level Feld haben, das auf Null gesetzt ist (oberste) und eine gespeicherte Prozedur, die den Level aktualisiert ( parent_id + 1), wenn Sie die parent_id aktualisieren.

 CREATE TRIGGER setLevelBeforeInsert BEFORE INSERT ON category FOR EACH ROW BEGIN IF NEW.parent_id IS NOT NULL THEN SELECT level INTO @pLevel FROM category WHERE id = NEW.parent_id; SET NEW.level = @pLevel + 1; ELSE SET NEW.level = 0; END IF; END; 

Keine level Spalte bisher 🙁

Hmm * Achselzucken *
Ich habe dieses Level-Feld gerade manuell erstellt.
Sagen wir, wie Materialized Path, mit nur einem Update nach dem Einfügen und ohne all diese ausgefallenen Trigger.
Ein Feld, das zum Beispiel wie 000000100000210000022 für die 3. Ebene sein wird

so kann es den tree im Gedächtnis aufbuild.

Wenn Sie ganze Tabelle in PHP bekommen, sehe ich hier kein Problem. Eine kleine rekursive function kann Ihnen Ihre verschachtelte Array-Struktur geben.

Ich kann meinen PHP-Code optimieren, aber ich denke, die Operation wäre viel einfacher

gut gut.
Der Code, den du bisher hast, scheint mir nicht "einfach" zu sein 🙂