Stephan Romhart über Technik, Kultur und Philosophie

Philosophie · Technik

Nested Sets und Alias-Pfade – Performante Bäume für Websites mit MySQL

Stephan 0

Ich verwende das Nested-Set-Modell für Websites, nicht für Foren- oder Kommentarsoftware. Es gibt genug Artikel, die zeigen, wie aufwändig Nested-Sets im Forenumfeld sind. Da Websites in der Regel mehr lesende als schreibende Zugriffe auf die Datenbank haben, ist das hier kein Thema.

Ausgangslage

Ausgangslage

Um das Prinzip zu erklären, nehme ich eine Struktur einer ganz kleinen Website: "Projekt" ist die Wurzel, "Start", "Unternehmen", "Kontakt" sind die Äste in Tiefe 1. "Unternehmen" hat noch Unteräste "Leistungen" und "Management".

Die Idee

Bei Nested Sets hat jeder Ast eines Baums zwei Werte: "left" und "right". Die Wurzel hat immer die 1 als left-Wert. Beispielsweise kann anhand des left-Werts die Sortierung abgelesen werden.

1 Projekt
2 Start
4 Unternehmen
5 Leistungen
7 Management
10 Kontakt

Die Anzahl der Unteräste eines Asts kann über folgende Formel ("right" - "left" - 1) / 2 errechnet werden.
Am Beispiel vom Ast "Unternehmen":

(9 - 4 - 1) = 2

Weitere Beispiele für das Anlegen, Bearbeiten und Löschen von Ästen findet man zuhauf im Netz. Ich habe dem Artikel unten ein paar Links zum Thema angehängt.

Sprechende URLS performant mit MySQL auslesen

Beispieltabelle in phpmyadmin

Ich habe das obenstehende Beispiel in MySQL aufgebaut. Die Tabelle "pages" hat folgende Spalten:
"id", "title", "alias", "lft", "rgt"

Über das Feld "alias" kann nun über ein Sub-Select der Pfad der jeweiligen Seite ausgelesen werden:

SELECT
	pages.*,
	(SELECT CONCAT(GROUP_CONCAT(alias.alias ORDER BY alias.lft SEPARATOR '/'))
		FROM pages AS alias
		LEFT JOIN pages AS child
			ON (alias.lft <= child.lft AND alias.rgt >= child.rgt)
		WHERE child.id = pages.id
	)
	AS path
FROM pages
ORDER BY pages.lft
Ergebnis der SQL-Abfrage mit Subselect für die Pfade

Ast-Tiefen mit Sub-Select auslesen

Mit einem weiteren Sub-Select lässt sich auch die Tiefe der Äste wie folgt auslesen:

SELECT
	pages.*,
	(SELECT count(*)
		FROM pages AS c, pages AS c2
		WHERE c.id = pages.id
		AND c.lft BETWEEN c2.lft AND c2.rgt
		GROUP BY c.lft)
	AS depth
FROM pages
ORDER BY pages.lft

Die komplette MySQL-Abfrage mit Alias-Pfaden und Ast-Tiefen

Wenn man nun beides kombiniert, bekommt man alle Werte, die man benötigt, um eine Websitestruktur aufzubauen. Die Tabelle kann einfach über eine Spalte "language" erweitert werden, um eine Mehrsprachigkeit der Website zu erreichen. Für jede Sprache wir eine eigene Wurzel-Seite benötigt.

SELECT
	pages.*,
	(SELECT CONCAT(GROUP_CONCAT(alias.alias ORDER BY alias.lft SEPARATOR '/'))
		FROM pages AS alias
		LEFT JOIN pages AS child
			ON (alias.lft <= child.lft AND alias.rgt >= child.rgt)
		WHERE child.id = pages.id
	)
	AS path,
	(SELECT count(*)
		FROM pages AS c, pages AS c2
		WHERE c.id = pages.id
		AND c.lft BETWEEN c2.lft AND c2.rgt
		GROUP BY c.lft)
	AS depth
FROM pages
ORDER BY pages.lft

Praktisch: Mit einer kurzen ergänzenden Where-Klausel am Ende der Anfrage kann dem Ergebnis die Wurzel-Seite entfernt werden:

...
FROM pages
WHERE pages.lft!=1
...

Mit dieser Methode bin ich die letzten Jahre sehr gut gefahren und habe diverse Projekte mit mehreren Sprachen und > 50 Seiten umgesetzt. Die Performance war bisher auch auf kleinen Webspaces sehr gut. Wenn es bessere und vor Allem performantere Wege gibt, Website-Bäume mit Mysql darzustellen, gebt mir bitte Bescheid! Ich freue mich über Eure Rückmeldungen zum Thema!

Weiterführende Links