Navigation mit Nested Sets

[S2B]

Hallo zusammen.

Ich versuche gerade, eine Navigationslösung für eine Website zu basteln, und das mit Nested Sets. Im Moment habe ich folgenden Baum:

Code:

[b]Item 1[/b]
  [b]Item 2[/b]
    [b]Item 3[/b]
      [b]Item 4[/b]
      [b]Item 5[/b]
    [b]Item 6[/b]
      Item 7
      Item 8
    [b]Item 9[/b]
  [b]Item 10[/b]
  [b]Item 11[/b]
[b]Item 12[/b]

Das ganze befindet sich in dieser Tabelle:

SQL-Code:

CREATE TABLE IF NOT EXISTS `s2b_navigation_items` (
  `item_id` mediumint(8) unsigned NOT NULL auto_increment,
  `nav_id` smallint(5) unsigned NOT NULL,
  `left_id` mediumint(8) unsigned NOT NULL,
  `right_id` mediumint(8) unsigned NOT NULL,
  `item_title` varchar(100) collate utf8_unicode_ci NOT NULL,
  `item_url` varchar(255) collate utf8_unicode_ci default NULL,
  `content_id` mediumint(8) unsigned default NULL,
  PRIMARY KEY  (`item_id`),
  KEY `content_id` (`content_id`),
  KEY `item_left_id` (`left_id`,`right_id`),
  KEY `item_root_id` (`nav_id`)
)

Nun zu meinem Problem: Diesen Baum würde ich nun gerne so anzeigen, wie das für Navigationen üblich ist, sprich nur einen Teil des Baums. Wenn Item 12 aktiv ist, sollen also lediglich Item 1 und Item 12 angezeigt werden; wenn hingegen Item 3 (oder Item 5) aktiv ist, sollen die Items 1, 2, 3, 4, 5, 6, 9, 10, 11 und 12 (siehe oben in fett) angezeigt werden. Allgemein bedeutet das:

1. Die oberste Navigationsebene
2. Den Pfad zum aktiven Eintrag sowie alle Nachbarknoten auf diesem Pfad
3. Die direkten Nachkommen des aktiven Eintrags, sofern vorhanden

Die Frage ist nun, wie ich das ganze am geschicktesten auslese. Ich habe bereits einiges an Zeit in SQL-Abfragen gesteckt, genauso viel Zeit in die Verarbeitung des kompletten Baums per PHP - leider bisher ohne Erfolg. Zwar habe ich mithilfe von Google ein Query ("Find the Immediate Subordinates of a Node") gefunden, das angeblich die Lösung zu meinem Problem sein soll (wenn ich die englische Beschreibung richtig verstanden habe), jedoch bekam ich ein anderes Ergebnis...

Mein Query zum Auslesen des kompletten Baums sieht so aus:

SQL-Code:

SELECT n.item_title, n.item_url, n.content_id, c.content_path,
   (COUNT(p.item_id) - 1) AS level, ROUND((n.right_id - n.left_id - 1) / 2) AS offspring
FROM s2b_navigation_items n
INNER JOIN s2b_navigation_items p
   ON n.left_id BETWEEN p.left_id AND p.right_id
LEFT JOIN s2b_content c
   ON c.content_id = n.content_id
WHERE n.nav_id = 1
GROUP BY n.item_id
ORDER BY n.left_id

Hat jemand einen Tipp für mich, wie ich da weiter vorgehen könnte? Irgendwie wundert es mich, dass es für mein Problem nicht schon hunderte Codeschnipsel gibt, denn eigentlich ist das doch ein naheliegender Anwendungsfall für Nested Sets...

[omata]

Vielleicht hilft dir das hier weiter.

[S2B]

Das hatte ich mir auch schon angeschaut, allerdings soll die Navigation später auch auf Servern laufen, die keine Stored Procedures/Temporary Tables können/dürfen...

[S2B]

Ich habe mich nun entschieden, das Problem auf PHP-Seite anzupacken. Nach ein paar Stunden Gefrickel hatte ich eine funktionierende Version:
Dieses Query liest den kompletten Navigationsbaum aus:

SQL-Code:

SELECT n.item_id, n.left_id, n.item_title, n.item_url, n.content_id, c.content_path,
   (COUNT(p.item_id) - 1) AS level
FROM s2b_navigation_items n
INNER JOIN s2b_navigation_items p
   ON n.left_id BETWEEN p.left_id AND p.right_id
LEFT JOIN s2b_content c
   ON c.content_id = n.content_id
WHERE n.nav_id = 1
GROUP BY n.item_id
ORDER BY n.left_id

Das Ergebnis packe ich in ein Array $tree, wobei die item_ids als Schlüssel verwendet werden.

Das zweite Query liefert den Pfad zur aktuell ausgewählten Seite (in diesem Fall #2):

SQL-Code:

SELECT p.item_id, p.left_id, p.right_id, p.content_id
FROM s2b_navigation_items p
INNER JOIN s2b_navigation_items n
   ON n.left_id BETWEEN p.left_id AND p.right_id
WHERE n.nav_id = 1
   AND n.content_id = 2
ORDER BY p.left_id

Das Ergebnis speichere ich analog zu oben in ein Array $path, zusätzlich werden die direkten Übereinstimmungen (= aktuell ausgewählte Seite) in ein separates Array $selected gespeichert.

Anschließend generiere ich das Array $items, also die fertige Navigation, folgendermaßen:

Code:

$items = array();
foreach ($tree as $item_id => $item_data)
{
   $item_level = $item_data['level'];
   $item_left_id = $item_data['left_id'];

   // Root-Ebene immer anzeigen
   if ($item_level == 0)
   {
      $items[$item_id] = $item_data;
      continue;
   }

   // Direkte Nachkommen der aktuellen Seite anzeigen (unterstützt mehrere Navigationspunkte für eine Seite)
   foreach ($selected as $selected_id)
   {
      if ($item_left_id > $path[$selected_id]['left_id'] && $item_left_id < $path[$selected_id]['right_id'] && $item_level == $tree[$selected_id]['level'] + 1)
      {
         $items[$item_id] = $item_data;
         continue 2;
      }
   }

   // Nachbarelemente auf dem Pfad anzeigen
   $last_id = null;
   foreach ($path as $path_id => $path_data)
   {
      if (isset($last_id) && isset($tree[$path_id]))
      {
         if ($item_left_id > $path[$last_id]['left_id'] && $item_left_id < $path[$last_id]['right_id'] && $item_level == $tree[$path_id]['level'])
         {
            $items[$item_id] = $item_data;
            continue 2;
         }
      }

      $last_id = $path_id;
   }
}

Zum Schluss wird das ganze über die Template-Engine ausgegeben - es funktioniert tadellos.