Liste d'adjacence par rapport au modèle d'ensemble imbriqué

Question

J'ai examiné la liste d'adjacence et le modèle d'ensemble imbriqué pour trouver la solution arborescente optimale. Jusqu'à présent, je pensais que l'un des principaux avantages de Nested Set Model était que je pouvais utiliser une requête SQL et du code pour obtenir un arbre complet. Mais il est compliqué de mettre à jour/insérer des nœuds et l'arbre entier peut facilement être corrompu.

Puis je suis tombé sur ces deux postes:

Recursive categories with a single query?

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

Le code suivant me permet d'utiliser contiguïté Liste avec une requête SQL. Il me semble que la liste d'adjacence est plus facile à mettre à jour et moins susceptible de corrompre l'arbre entier.

Que pensez-vous de ce code?

Générer un tableau multidimensionnel pour refléter la structure de l'arbre

$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); 

Préparer une liste à puces avec des noeuds imbriqués

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

Le code semble être tout à fait correct et donné un nombre raisonnable de lignes (Des millions de lignes ne le sont pas) ne vous frappera pas trop fort, dans le sens des performances.

Mais je pense que vous avez posé la mauvaise question:

met Nested entrent en jeu lorsque vous devez hiérarchies de cheminement et il serait trop coûteux pour aller chercher toute la table afin de trouver le parent du parent d'un certain noeud. Avec les listes d'adjacence, vous aurez besoin de plusieurs requêtes pour y parvenir ou laissez PHP faire le travail avec des boucles imbriquées (ce qui signifie O (n^2) pire cas).

Dans les deux cas, les ensembles imbriqués seront généralement plus performants si vous recherchez des ancêtres (par exemple, recherchez un produit dans une hiérarchie de catégories imbriquées).

Voir cet article: Managing Hierarchical Data in MySQL. Cela vous donnera un bon point de départ pour implémenter les différentes requêtes/mises à jour/insertions/suppressions.