Lista de adyacencia frente al modelo de conjunto anidado

Question

He estado buscando en la Lista de adyacencia y en el Conjunto anidado para encontrar la solución de árbol óptima.

Hasta ahora, pensaba que una de las principales ventajas de Nested Set Model era que podía usar una consulta SQL y un código para obtener un árbol completo. Pero es complicado actualizar/insertar nodos y todo el árbol puede dañarse fácilmente.

Entonces tropecé con estos dos mensajes:

Recursive categories with a single query?

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

El siguiente código me permite usar lista de adyacencia con una consulta SQL. Me parece que la Lista de adyacencia es más fácil de actualizar y es menos probable que corrompa todo el árbol.

¿Qué opinas sobre este código?

Generar una matriz multidimensional para reflejar la estructura de árbol

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

Preparar una lista desordenada con nodos anidados

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

El código parece estar bastante bien y dado un número razonable de filas (millones de filas no lo son) no te golpearán demasiado duro, en lo que respecta al rendimiento.

Pero creo que ha hecho la pregunta equivocada:

anidada establece entran en juego cuando se necesita para jerarquías transversales y que sería demasiado costoso para traer toda la mesa con el fin de encontrar el padre del padre de un nodo determinado. Con listas de adyacencia, necesitaría múltiples consultas para lograr esto o permitir que PHP haga el trabajo con bucles anidados (lo que significa O (n^2) en el peor de los casos).

De cualquier forma, los conjuntos anidados generalmente tendrán un rendimiento mucho mejor cuando encontrar objetivos ancestrales (por ejemplo, encontrar un producto en una jerarquía de categorías anidadas).

Ver este artículo: Managing Hierarchical Data in MySQL. Le dará un buen punto de partida sobre cómo implementar las diversas consultas/actualizaciones/inserciones/eliminaciones.