Wie erstelle ich eine HTML-Liste aus einem Nested-Set?

Einer der meistgelesenen Beiträge in diesem Blog ist der über Nested Sets. Es bringt natürlich nichts, wenn man damit performante Abfragen realisieren kann aber anschließend das Ergebnis nicht in entsprechenden HTML-Code umwandeln kann, um daraus eine Navigationsliste oder ähnliches zu erstellen. Da laut einiger Kommentare genau dort das Problem liegt, möchte ich in diesem Beitrag beschreiben, wie man ein Nested Set in eine Unordered List umwandeln kann.

Zuerst nochmal unser Ausgangspunkt: Wir haben eine Tabelle kategorien mit 4 Spalten: ID, name, lft, rgt
Dort sind einige Kategorien untergebracht, genau wie im Nested Set-Beitrag erklärt: Der lft-Wert einer übergeordneten Kategorie ist kleiner als alle lft-Werte Ihrer Kind-Kategorien und der rgt-Wert der übergeordneten Kategorie ist größer als alle rgt- (und auch lft-) Werte. Dadurch entstehen Umarmungen und Abfragen aller Kindelemente einer bestimmten Kategorie sind problemlos möglich.
Aber ich möchte hier nicht nochmal das gesamte Modell erklären, das steht ja ausführlich im Nested-Set-Beitrag.

Nun möchten wir sämtliche Kategorien samt Ihrer Untermenüs hierarchisch anzeigen – in einer Unordered List, die für jede hierarchisch untergeordnete Ebene weitere ULs einbaut. Das geht nur rekursiv.
Falls sich jemand fragt, was nun eigentlich gewonnen ist, wenn wir die rekursiven Abfragen, wie Sie “normalerweise” bei Baumstrukturen in MySQL gemacht werden, wiederum durch etwas Rekursives ersetzen. Nun, die Variante mit parentID erfordert sehr viele MySQL-Abfragen. Ständig muss in einer Schleife bzw. rekursiv durch PHP die DB abgefragt werden, ob diese oder jene Kategorie Kindelemente hat. Das schlaucht den DB-Server unnötig (jede Anfrage hat noch Overhead). Deshalb ist es immer ratsam SQL-Abfragen aus Schleifen rauszuholen und möglichst durch eine einzige Abfrage zu ersetzen (falls dies möglich ist).

Wenn wir nun die rekursive Funktion allein nutzen, um aus dem fertigen Ergebnis eine Liste zusammen zu bauen, bleibt alles im Rahmen von PHP – es muss kein anderes System mehr nach Informationen befragt werden und das bringt den Geschwindigkeitsschub.

Jedenfalls möchten wir nun die Liste darstellen, dazu sind mehrere Funktionen nötig – zuerst unsere Hauptfunktion, die das Result Set holt und das Array erstellt, mit dem wir fortan arbeiten:

  function getMenu() {
      $query = "SELECT lft,rgt FROM kategorien";
      $einlesen = mysql_query($query);
      $lft = array();
      $rgt = array();
      while($einzeln = mysql_fetch_assoc($einlesen)) {
        $lft[] = $einzeln['lft'];
        $rgt[] = $einzeln['rgt'];
      }
      $query = "SELECT n.ID,n.name, COUNT( * ) -1 AS level FROM kategorien AS n, kategorien AS p WHERE n.lft BETWEEN p.lft AND p.rgt AND (";
      for($i=0;$i<count($lft);$i++) {
        $query .= "(n.lft<=".$lft[$i]." AND n.rgt>=".$rgt[$i].")";
        if($i<count($lft)-1) $query .= " OR ";
      }
      $query .= ") GROUP BY n.lft";
      $einlesen = mysql_query($query);    
 
      $menu = array();
      while($einzeln = mysql_fetch_assoc($einlesen)) {
        $menu[] = array($einzeln['ID'],$einzeln['name'],$einzeln['level']);
      }
      return buildMenu($menu);
  }

Diese Funktion selektiert alle Kategorien und speichert die Datensätze im Array $menu ab. Die erste Abfrage nach allen lft- und rgt-Werten wird erst sinnvoll, wenn nur bestimmte Zweige eingelesen werden sollen. Der Einfachheit halber habe ich das hier weggelassen. Würde bedeuten einfach einen Parameter der Funktion getMenu() zu übergeben und diesen dann in diese Query einfließen zu lassen.

Der Rückgabewert der Funktion erfordert den Aufruf der Funktion, die das Result Set in HTML konvertieren soll:

  function buildMenu($subMenu) {
    $menu = "";
    $cnt_subMenu = count($subMenu);
    for($i=0;$i<$cnt_subMenu;$i++) {
      if($i<$cnt_subMenu-1 && $subMenu[$i][2]<$subMenu[$i+1][2]) {
        $menu .= "<li>".$subMenu[$i][0]." ".$subMenu[$i][1]."<ul>";
        $untilIndexUnderThisKat = getKatsUnder($subMenu,$i+1,$subMenu[$i][2]);
        $menu .= buildMenu(array_cut($subMenu,$i+1,$untilIndexUnderThisKat));
        $i = $untilIndexUnderThisKat;
        $menu .= "</ul></li>";
      } else {
        $menu .= "<li>".$subMenu[$i][0]." ".$subMenu[$i][1]."</li>";
      }
    }
    return $menu;
  }

Diese Funktion durchläuft alle Kategorien-Datensätze und schaut, ob im nachfolgenden Eintrag die Ebene (Array-Index [2]) größer ist als beim aktuellen. Wenn dem so ist, wird eine weitere Liste unter dem aktuellen LI angelegt, indem die Funktion buildMenu() rekursiv aufgerufen wird, vorher aber das Array so gesplittet wird, das nur noch die Untermenüs des aktuellen Eintrags darin enthalten sind. Dazu werden zuerst alle darunter liegenden Kategorien geholt (getKatsUnder()) und anschließend das neue Array erstellt – das übernimmt die Funktion array_cut():

  function getKatsUnder($array,$start,$ebene) {
    $cnt_array = count($array);
    for($i=$start;$i<$cnt_array;$i++) {
      if($array[$i][2]==$ebene) return $i-1;
    }
    return ($cnt_array-1);
  }
 
  function array_cut($srcArr,$start,$end) {
    $newArr = array();
    for($i=$start;$i<=$end;$i++) {
      $newArr[] = $srcArr[$i];
    }
    return $newArr;
  }

Ob die Sache noch performanter zu machen ist, kann ich im Augenblick nicht sagen, weil ich diesen Weg alle Einträge auf einmal zu laden selbst nicht mehr anwende und deshalb auch nicht weiter über die Performance nachgedacht habe. Es ist einfach der Weg, wie ich es mir damals ausgedacht habe. Ghostgambler hatte noch was mit current() und next() vorgeschlagen, eventuell gehts in die gleiche Richtung wie meine Lösung – wenn nicht, wäre es schön, wenn Du noch etwas mehr dazu sagen könntest.

Ich hoffe das hilft denjenigen, die immer wieder nach einem Weg gefragt haben… und wie gesagt: Die Lösung erhebt keinen Anspruch die schönste oder beste zu sein – auf jeden Fall funktioniert sie.
Und damit ihr nicht mühsam die Sachen rauskopieren müsst, hänge ich sogar das Script an: Nested Set zu HTML umwandeln

Jan hat 152 Beiträge geschrieben

10 Kommentare zu “Wie erstelle ich eine HTML-Liste aus einem Nested-Set?

  1. hpoe sagt:

    Wenn man im SELECT die Tiefe (Level) der Baumelemente ermittelt, braucht man keine Recursion mehr.
    Man kann aufgrund des Levels resp. dem Vergleich mit dem Level des Vorgängerknotens feststellen, ob weiter eingerückt, oder auf dem gleichen Level nur Blöcke ausgegeben werden sollen. Dies ergibt eine ziemlich einfache Logik.
    Annahme: die gesamte Hierarchie ist in einem Array $hierarchy mit den Elementen Payload, Level, id, lft, rgt), der Level der Root sei 0;

    $level = -1;
    $html = "";
    foreach ($hierarchy as $row) {
      if($row['level'] ", $diff);
      }
      if($row['level'] &gt; $level){ $html .= ""; }
      $html .= "".$row['payload']."";
    }
    if ($level &gt; 0) $html .= str_repeat("", $level);
  2. Jan sagt:

    Leider ist nicht alles komplett angekommen. Kannst Du es mir nochmal per Mail schicken, dann stelle ich eine korrigierte Version Deines Kommentars online. WordPress macht leider oft Code in den Kommentaren kaputt.

  3. Jan sagt:

    Hier nochmal hpoe’s Beitrag komplett:
    Die Query muss folgendermassen lauten:

    select a.id, a.name, count(*) - 1 as level FROM kategorien as a join kategorien as b on a.lft between b.lft  and b.rgt and     a.rgt between b.lft and b.rgt group by a.id, a.name order by a.lft, a.id

    Das Resultset in Array umwandeln.

    dann nur noch die paar Zeilen PHP mit etwas Kommentar

    /**   Ausgangs Situation:   resultset als Array $hierarchy mit den Feldern level, name   root level = 0 (weil count(*) - 1 gesetzt wird */ $level = -1; // kleiner als root level initialisieren $html = ""; foreach ($hierarchy as $row) {   // gelesenes Level kleiner als das letzte:   // differenz an Leveln ermitteln und soviele </ul> ausgeben   if($row['level'] < $level) {     $diff = $level - $row['level'];     $html .= str_repeat("</ul>", $diff)   }   // gelesener Level  grösser als Vergleichslevel: neue Stufe beginnen   if($row['level'] > $level){ $html .= "<ul>"; }   // immer das <li> ...</li> ausgeben   $html .= "<li>".$row['name']."</li>";   // Vergleichswert festhalten   $level = $row['level']; } // falls Vergleichslevel >= 0, muss bis auf Level 0 abgetragen werdne if ($level >= 0) $html .= str_repeat("</ul>", ($level + 1));

  4. Markus Winkelmann sagt:

    @jan: danke für deine tollen beiträge über nested sets! die haben mir u.a. sehr geholfen beim einstieg in die thematik.

    @hpoe: dir auch einen riesen dank für deine nicht rekursive version zur herstellung einer “html ul nested set liste”, allerdings erzeugt diese so in der form keinen validen quellcode. das ul-element darf nicht im ul-element stehen, sondern muss im li eingebaut sein.

    Hier mein Code:

    /**
          Ausgangs Situation:
          resultset als Array $hierarchy mit den Feldern level, title
          root level = 0 (weil count(*) - 1 gesetzt wird
        */
        $level = -1; // kleiner als root level initialisieren
        $html = "";
        foreach ($baum as $row) {
          // gelesenes Level kleiner als das letzte:
          // differenz an Leveln ermitteln und soviele </ul> ausgeben
          if($row['level'] < $level) {
            $diff = $level - $row['level'];
            $html .= "</li>\n";
            $html .= str_repeat("</ul></li>\n", $diff);         }
          // gelesener Level  grösser als Vergleichslevel: neue Stufe beginnen
          if($row['level'] > $level){ $html .= "<ul>"; }
              if($row['level'] == $level) $html .= "</li>\n";
              // immer das <li> ... ausgeben
          $html .= "<li>".$row['title'];
              // falls level kleiner oder gleich vergleichslevel listitem schließen
          //if($row['level'] < $level) $html .= "</li>";
          // Vergleichswert festhalten
          $level = $row['level'];
        }
        // falls Vergleichslevel >= 0, muss bis auf Level 0 abgetragen werdne
            if ($level >= 0) $html .= str_repeat("</li></ul>\n", $level);
        $html .= "</li></ul>\n";
        echo $html;

    gruß, markus

  5. stega sagt:

    Kurz Frage zum Ausgabeskript von Markus Winkelmann:

    am Anfang soll das Array stehen, das dann verarbeitet wird. Wie kann ich denn meine Daten so ins Array laden, dass sie dann korrekt verarbeitet werden? Ich habe es mit mysql_fetch_assoc probiert, aber er bringt nur die erste “id” Spalte dann in der Anzeige. Und auch mit mysql_fetch_assoc funktioniert die Ausgabe leider nicht…

    danke für eure Hilfe – super Tutorial!!!

  6. hpoe sagt:

    @Markus: danke für deine Korrektur, es ging mir mehr ums prinzipielle daran! Es ist etwas verwirrend wenn im Kommentar das Array $hierarchy heisst und nachher mit $baum gearbeitet wird.

    @stega: deine Frage ist etwas sehr weit gefasst, da es darauf an kommt, welches DB Interface vervendet wird. Ein ganzes Array auf einmal, ohne durch das Resultat der Query zu loopen und das Array selbst zu bauen gibt es nur mit PDO.

  7. arabeske sagt:

    hier das Ganze mal als smarty script:

    {assign var=”level” value=’0′}
    {assign var=”diff” value=’0′}
    {foreach from=$list item=row name=’c’}
    {if $row.depth < $level}
    {math equation='l – d' l=$level d=$row.depth assign=diff}

    {“”|str_repeat:$diff}
    {/if}
    {if $row.depth > $level} {/if}
    {if $row.depth == $level} {/if}

    {$row.username}
    {if $row.depth < $level} {/if}
    {*$level = $row.depth*}
    {assign var=level value=$row.depth}
    {/foreach}
    {if $level > 0} {“”|str_repeat:$level} {/if}

Eine Antwort schreiben

Ihre E-Mail-Adresse wird nicht veröffentlicht. Benötigte Felder sind markiert mit *

You may use these HTML tags and attributes: <a href=""> <blockquote cite=""> <pre lang=""> <b> <strong> <i> <em>