Adjazenzliste vs. verschachteltes Mengenmodell

Question

Ich habe in Adjazenzliste und Nested Set Model nach der optimalen Baumlösung gesucht.

Bisher dachte ich, einer der Hauptvorteile von Nested Set Model wäre, dass ich eine SQL-Abfrage und einen Code verwenden könnte, um einen vollständigen Baum zu erhalten. Es ist jedoch kompliziert, Knoten zu aktualisieren/einzufügen, und der gesamte Baum kann leicht beschädigt werden.

Dann stolperte ich über diese beiden Beiträge:

Recursive categories with a single query?

http://www.sitepoint.com/forums/showthread.php?t=570360

Der folgende Code ermöglicht es mir Adjazenzliste mit einer SQL-Abfrage zu verwenden. Es scheint mir, dass die Adjazenzliste leichter zu aktualisieren ist und weniger wahrscheinlich den ganzen Baum verfälscht.

Was denken Sie über diesen Code?

eine mehrdimensionale Array erzeugen, um die Baumstruktur

$nodeList = array(); 
    $tree = array(); 

    $query = mysql_query("SELECT id, title, page_parent FROM categories ORDER BY page_parent"); 
    while($row = mysql_fetch_assoc($query)){ 
     $nodeList[$row['id']] = array_merge($row, array('children' => array())); 
    } 
    mysql_free_result($query); 

    foreach($query AS $row){ 
     $nodeList[$row['id']] = array_merge($row, array('children' => array())); 
    } 

    foreach ($nodeList as $nodeId => &$node) { 
     if (!$node['page_parent'] || !array_key_exists($node['page_parent'], $nodeList)) { 
      $tree[] = &$node; 
     } else { 
      $nodeList[$node['page_parent']]['children'][] = &$node; 
     } 
    } 

    unset($node); 
    unset($nodeList); 

Bereiten Sie eine ungeordnete Liste mit verschachtelten Knoten

function printMenu ($arrTreeToTraverse, $ext = '.html', $breadcrumb = '') { 

// Pre loop stuff 
echo "<ul class=\"sf-menu\">\r\n"; 

foreach ($arrTreeToTraverse as $objItem) { 

    // Stuff relevant to the item, before looping over its children 
    if ($objItem['page_parent'] != 0) { 
     $breadcrumb .= '/'.$objItem['uri']; 
    } 
    else 
    { 
     $breadcrumb .= $objItem['uri']; 
    } 

    if ($objItem['uri'] == 'index') { 
     echo '<li><a href="/">'.$objItem['title'].'</a>'; 
    } else { 
     echo '<li><a href="'$_SERVER['SERVER_NAME'].'/'.$breadcrumb.$ext.'">'.$objItem['title'].'</a>'; 
    } 

    if ($objItem['children']) { 
    echo "\r\n"; 

     // Call the function again on the children 
     printMenu($objItem['children'], $ext, $breadcrumb); 
    }// if 

    // Extend breadcrumb if it is a child or 
    // reset breadcrumb if first level of tree 
    $parent = explode('/', $breadcrumb); 
    if ($objItem['page_parent'] != 0) { 
     $breadcrumb = $parent[0]; 
    } else { 
     $breadcrumb = ''; 
    } 

    echo "</li>\r\n"; 
}// foreach 

// Post loop stuff 
echo "</ul>\r\n"; 

}// function 

printMenu($navigation, '.html'); 

Answer 1

Der Code widerzuspiegeln scheint ganz in Ordnung und eine angemessene Anzahl von Zeilen gegeben zu sein (Millionen von Zeilen sind nicht) wird Sie nicht zu hart schlagen, performancewise.

Aber ich denke, Sie die falsche Frage gestellt haben:

Nested Sets ins Spiel kommen, wenn Sie brauchen, um Querungs Hierarchien und es wäre zu teuer, die gesamte Tabelle, um zu holen, zu finden das übergeordnete Element eines bestimmten Knotens. Mit Adjazenzlisten benötigen Sie mehrere Abfragen, um dies zu erreichen, oder lassen Sie PHP die Arbeit mit verschachtelten Schleifen (was O (n^2) schlimmsten Fall bedeutet).

In beiden Fällen werden verschachtelte Sätze im Allgemeinen besser funktionieren, wenn das Auffinden von Vorfahren Ihr Ziel ist (z. B. ein Produkt in einer Hierarchie verschachtelter Kategorien finden).

Sehen Sie diesen Artikel: Managing Hierarchical Data in MySQL. Es gibt Ihnen einen guten Ausgangspunkt, um die verschiedenen Abfragen/Updates/Einfügungen/Löschungen zu implementieren.