Kommen wir nun zum zweiten Teil unserer NestedSets-Serie. In diesem Teil möchte ich Euch zeigen, wie Ihr Zeilen und Bäume sowie Unterbäume sortieren und auslesen könnte. Außerdem werde ich anhand von einigen Beispielen Elemente und ganze Bäume löschen.
Datenbankstruktur
Fangen wir zunächst wieder mit unserer Datenbank an. Nachdem wir diese erstellt haben und auch schon einige Elemente hinzugefügt worden sind, könnte diese wie folgt aussehen:
-- MySQL Administrator dump 1.4 -- -- ------------------------------------------------------ -- Server version 5.1.41-3ubuntu12.6 /*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */; /*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */; /*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */; /*!40101 SET NAMES utf8 */; /*!40014 SET @OLD_UNIQUE_CHECKS=@@UNIQUE_CHECKS, UNIQUE_CHECKS=0 */; /*!40014 SET @OLD_FOREIGN_KEY_CHECKS=@@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0 */; /*!40101 SET @OLD_SQL_MODE=@@SQL_MODE, SQL_MODE='NO_AUTO_VALUE_ON_ZERO' */; -- -- Create schema test -- CREATE DATABASE IF NOT EXISTS test; USE test; -- -- Definition of table `test`.`test` -- DROP TABLE IF EXISTS `test`.`test`; CREATE TABLE `test`.`test` ( `test_id` int(5) unsigned NOT NULL AUTO_INCREMENT, `test_name` varchar(200) NOT NULL, `test_left` int(5) unsigned NOT NULL, `test_right` int(5) unsigned NOT NULL, PRIMARY KEY (`test_id`) ) ENGINE=InnoDB AUTO_INCREMENT=36 DEFAULT CHARSET=utf8 PACK_KEYS=1 COMMENT='This is just a NestedSets test table.'; -- -- Dumping data for table `test`.`test` -- INSERT INTO `test`.`test` (`test_id`,`test_name`,`test_left`,`test_right`) VALUES (1,'Tierreich',1,50), (2,'Insekten',2,17), (3,'Fische',18,29), (4,'Vögel',40,49), (5,'Reptilien',30,39), (6,'Küchenschabe',15,16), (7,'Biene',13,14), (8,'Mücke',11,12), (9,'Staublaus',9,10), (10,'Zikade',7,8), (11,'Marienkäfer',5,6), (12,'Floh',3,4), (13,'Schlange',37,38), (14,'Schildkröte',35,36), (15,'Krokodil',33,34), (16,'Brückenechse',31,32), (17,'Hai',27,28), (18,'Karpfen',25,26), (19,'Rochen',23,24), (20,'Sardine',21,22), (21,'Stör',19,20), (22,'Amsel',47,48), (23,'Drossel',45,46), (24,'Fink',43,44), (25,'Möve',41,42); /*!40101 SET SQL_MODE=@OLD_SQL_MODE */; /*!40014 SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS */; /*!40014 SET UNIQUE_CHECKS=@OLD_UNIQUE_CHECKS */; /*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */; /*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */; /*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */; /*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */;
Holen von Bäumen, Unterbäumen und Blättern.
Beginnen wir also mit dem sortieren und auslesen der gewünschten Zeilen. Ich möchte an dieser Stelle erwähnen, dass ich bewusst nicht den Query-Builder von Zend_Db_Table nutze um etwas an Performance heraus zu kitzeln. Wie groß der Vorteil der von mir gezeigten Variante ist, müsste anhand eines Benchmark-Tests festgestellt werden, was jedoch nicht Teil dieser NestedSets-Serie sein wird.
Zunächst holen wir uns einfachheitshalber den kompletten Baum mit Wurzelelement aus der Datenbank. Das geschieht mit der Funktion getTree() der NestedSets-Klasse:
public function getTree()
{
$res = $this->getAdapter()
->query("SELECT COUNT(`parent`.`{$this->_primary}`) - 1 AS `depth`, `node`.*
FROM `{$this->_name}` AS `node`, `{$this->_name}` AS `parent`
WHERE `node`.`{$this->_leftColumn}`
BETWEEN `parent`.`{$this->_leftColumn}`
AND `parent`.`{$this->_rightColumn}`
GROUP BY `node`.`{$this->_primary}`
ORDER BY `node`.`{$this->_leftColumn}`");
return $res->fetchAll();
}
Was machen wir hier? Wir holen uns alle Zeilen der test-Tabelle und fügen vorne die Tiefe des aktuellen NestedSets-Elements an. Besonders wichtig ist hier – genauso wie in den anderen SELECT-Anweisungen der NestedSets – die aufsteigende Sortierung der linken Spalte.
Als Ergebnis dieser Abfrage erhalten wir dieses Array:
array
0 =>
array
'depth' => string '0' (length=1)
'test_id' => string '1' (length=1)
'test_name' => string 'Tierreich' (length=9)
'test_left' => string '1' (length=1)
'test_right' => string '50' (length=2)
1 =>
array
'depth' => string '1' (length=1)
'test_id' => string '2' (length=1)
'test_name' => string 'Insekten' (length=8)
'test_left' => string '2' (length=1)
'test_right' => string '17' (length=2)
2 =>
array
'depth' => string '2' (length=1)
'test_id' => string '12' (length=2)
'test_name' => string 'Floh' (length=4)
'test_left' => string '3' (length=1)
'test_right' => string '4' (length=1)
3 =>
array
'depth' => string '2' (length=1)
'test_id' => string '11' (length=2)
'test_name' => string 'Marienkäfer' (length=12)
'test_left' => string '5' (length=1)
'test_right' => string '6' (length=1)
4 =>
...
Nun können wir bereits deutlich erkennen, dass Tierreich unser Wurzelelement mit der Tiefe 0 ist. Insekten ist unser erstes Kind des Wurzelelementes und die weiteren Zeilen entsprechen den Kindern der Insekten-Zeile. Wir sprechen hier insgesamt von einem Baum. Diesen Baum können wir uns genau so vorstellen: Wir haben die Wurzel (das Stammelement) des Baumes sowie die Äste (Insekten wäre z.B. ein Ast). Die Blätter dieses Baumes sind dann die Elemente eines Astes. Hier also Floh und Marienkäfer etc. Natürlich könnten wir noch weiter gehen und untergeordnete Äste von bereits bestehenden Ästen erstellen. (Wir unterteilen also die verschiedenen Insekten in weitere Bereiche).
Damit uns nicht langweilig wird, holen wir nun (etwas komplizierter) einen bestimmten Ast/Unterast und dessen Blätter. In unserem Fall möchten wir Insekten und dessen Kinder (Floh, Marienkäfer, Zikade, Staublaus, Mücke, Biene, Küchenschabe) haben. Dazu habe ich die Methode getSubTree() geschrieben, welche als ersten Parameter die ID des zu holenden Unterbaumes entgegen nimmt.
public function getSubTree($id)
{
$res = $this->getAdapter()->query("
SELECT (COUNT(`parent`.`{$this->_primary}`) - (`sub_tree`.`depth` + 1)) AS `depth`, `node`.*
FROM
`{$this->_name}` AS `node`,
`{$this->_name}` AS `parent`,
`{$this->_name}` AS `sub_parent`,
(
SELECT `node`.`{$this->_primary}`, (COUNT(`parent`.`{$this->_primary}`) - 1) AS `depth`
FROM `{$this->_name}` AS `node`, `{$this->_name}` AS `parent`
WHERE `node`.`{$this->_leftColumn}` BETWEEN `parent`.`{$this->_leftColumn}` AND `parent`.`{$this->_rightColumn}`
AND `node`.`{$this->_primary}` = $id
GROUP BY `node`.`{$this->_primary}`
ORDER BY `node`.`{$this->_leftColumn}`
) AS `sub_tree`
WHERE `node`.`{$this->_leftColumn}` BETWEEN `parent`.`{$this->_leftColumn}` AND `parent`.`{$this->_rightColumn}`
AND `node`.`{$this->_leftColumn}` BETWEEN `sub_parent`.`{$this->_leftColumn}` AND `sub_parent`.`{$this->_rightColumn}`
AND `sub_parent`.`{$this->_primary}` = `sub_tree`.`{$this->_primary}`
GROUP BY `node`.`{$this->_primary}`
ORDER BY `node`.`{$this->_leftColumn}`");
return $res->fetchAll();
}
Auch hier fügen wir vorne die Tiefe des jeweils aktuellen Elementes an um eine leichtere Darstellung auf der Seite zu ermöglichen . Übergeben wir nun an diese Methode den Wert 2, so erhalten wir den entsprechenden Baum:
array
0 =>
array
'depth' => string '0' (length=1)
'test_id' => string '2' (length=1)
'test_name' => string 'Insekten' (length=8)
'test_left' => string '2' (length=1)
'test_right' => string '17' (length=2)
1 =>
array
'depth' => string '1' (length=1)
'test_id' => string '12' (length=2)
'test_name' => string 'Floh' (length=4)
'test_left' => string '3' (length=1)
'test_right' => string '4' (length=1)
2 =>
array
'depth' => string '1' (length=1)
'test_id' => string '11' (length=2)
'test_name' => string 'Marienkäfer' (length=12)
'test_left' => string '5' (length=1)
'test_right' => string '6' (length=1)
3 =>
array
'depth' => string '1' (length=1)
'test_id' => string '10' (length=2)
'test_name' => string 'Zikade' (length=6)
'test_left' => string '7' (length=1)
'test_right' => string '8' (length=1)
4 =>
array
'depth' => string '1' (length=1)
'test_id' => string '9' (length=1)
'test_name' => string 'Staublaus' (length=9)
'test_left' => string '9' (length=1)
'test_right' => string '10' (length=2)
5 =>
array
'depth' => string '1' (length=1)
'test_id' => string '8' (length=1)
'test_name' => string 'Mücke' (length=6)
'test_left' => string '11' (length=2)
'test_right' => string '12' (length=2)
6 =>
array
'depth' => string '1' (length=1)
'test_id' => string '7' (length=1)
'test_name' => string 'Biene' (length=5)
'test_left' => string '13' (length=2)
'test_right' => string '14' (length=2)
7 =>
array
'depth' => string '1' (length=1)
'test_id' => string '6' (length=1)
'test_name' => string 'Küchenschabe' (length=13)
'test_left' => string '15' (length=2)
'test_right' => string '16' (length=2)
War das nicht einfach? Was ist jedoch, wenn wir zum Beispiel das Elternelement eines Blattes (z.B. von Karpfen = Fische) herausfinden möchten? Das wäre wie folgt lösbar:
public function getParentElement($id)
{
$res = $this->getAdapter()
->query("SELECT `node`.* FROM `{$this->_name}` AS `parent`
INNER JOIN `{$this->_name}` AS `node`
WHERE (`parent`.`{$this->_leftColumn}` BETWEEN `node`.`{$this->_leftColumn}` AND `node`.`{$this->_rightColumn}`)
AND (`parent`.`{$this->_primary}` = {$id})
ORDER BY `node`.`{$this->_leftColumn}` DESC LIMIT 1,1");
$ret = $res->fetchAll();
switch (count($ret))
{
case 1:
return $ret[0];
default:
return null;
}
}
Wir möchten nur die Blätter, also die tiefsten Elemente des kompletten Baumes haben? Nichts einfacher als dass:
public function fetchLeafNodes()
{
$res = $this->getAdapter()
->query("SELECT * FROM `{$this->_name}`
WHERE `{$this->_rightColumn}`=`{$this->_leftColumn}`+1
ORDER BY `{$this->_leftColumn}`;");
return $res->fetchAll();
}
Nun gut. Kommen wir nun zum löschen von Blättern, Ästen und ganzen Unterbäumen. Weitere fetch/get Methoden werden mit der Zeit der fertigen Klasse hinzugefügt.
Wie – ihr habt noch nicht genug?
Ok, dann noch ein Anwendungsbeispiel. Wir haben ein Menü in der Datenbank gespeichert (rekursives Menü) und möchten den Pfad (Breadcrumbs) zur aktuellen Seite anzeigen lassen. Das könnten wir nun so machen:
public function fetchPathToElement($id)
{
$res = $this->getAdapter()
->query("SELECT `parent`.*
FROM `{$this->_name}` AS `node`,
`{$this->_name}` AS `parent`
WHERE `node`.`{$this->_leftColumn}` BETWEEN `parent`.`{$this->_leftColumn}` AND `parent`.`{$this->_rightColumn}`
AND `node`.`{$this->_primary}`={$id}
ORDER BY `node`.`{$this->_leftColumn}`;");
return $res->fetchAll();
}
Als Beispiel $id = 25 (Für Möve) würden wir das nächste Array erhalten:
array
0 =>
array
'test_id' => string '1' (length=1)
'test_name' => string 'Tierreich' (length=9)
'test_left' => string '1' (length=1)
'test_right' => string '50' (length=2)
1 =>
array
'test_id' => string '4' (length=1)
'test_name' => string 'Vögel' (length=6)
'test_left' => string '40' (length=2)
'test_right' => string '49' (length=2)
2 =>
array
'test_id' => string '25' (length=2)
'test_name' => string 'Möve' (length=5)
'test_left' => string '41' (length=2)
'test_right' => string '42' (length=2)
Löschen von Elementen
Da wir nicht immer alle Elemente brauchen, müssen wir natürlich auch die Möglichkeit haben eben solche unbenötigten Zeilen wieder löschen zu können. Doch wie stellen wir das an, ohne die vorhandene NestedSets-Struktur zu zerstören? Schließlich müssen wir die left- und right-Spalten auch beim löschen anpassen. Der einfachste Anwendungsfall ist das rekursive löschen eines angegebenen Elementes und dessen Kinder (falls vorhanden).
Jetzt fehlt uns nur noch die Methode selber zum löschen des angegeben Elementes und seiner Kinder:
public function deleteNodeWithChildren($id)
{
$row = $this->fetchRow(array($this->_primary . ' = ?' => $id));
if ($row) {
$left = (int) $row->{$this->_leftColumn};
$right = (int) $row->{$this->_rightColumn};
$width = $right - $left + 1;
$res = $this->getAdapter()->query("DELETE FROM `{$this->_name}` WHERE `{$this->_leftColumn}` BETWEEN `{$left}` AND `{$right}`;");
$this->getAdapter()->query("UPDATE `{$this->_name}` SET `{$this->_rightColumn}` = `{$this->_rightColumn}` - {$width} WHERE `{$this->_rightColumn}` > {$right};");
$this->getAdapter()->query("UPDATE `{$this->_name}` SET `{$this->_leftColumn}` = `{$this->_leftColumn}` - {$width} WHERE `{$this->_leftColumn}` > {$right};");
return $res->rowCount();
}
return 0;
}
Ja, ihr schaut richtig. Zum löschen eines Elementes (Bzw. auch inkl. zugehöriger Kinder) benötigen wir ganze 3 SQL Abfragen. Das gehört leider zu den negativen Eigenschaften der NestedSets, die uns im Frontend unserer Website jedoch nicht stören sollten.
Es lassen sich mehrere Variation der delete-Methode ableiten. So zum Beispiel das löschen von Elementen, dessen Attribute entsprechende Werte haben.
Im nächsten teil der NestedSets-Reihe werde ich euch zeigen, wie ihr Blätter, Äste und sogar ganze Bäume verschieben könnt.