Adjacency list vs. nested set model

Question

I have been looking into Adjacency List and Nested Set Model to find the optimal tree solution.

Up until now I thought one of the main advantages of Nested Set Model was that I could use one SQL query and some code to get a complete tree. But it is complicated to update/insert nodes and the whole tree can easily get corrupted.

Then I stumbled over these two posts:

Recursive categories with a single query?

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

The following code allows me to use Adjacency List with one SQL query. It seems to me that Adjacency List is easier to update and less likely to corrupt the whole tree.

What do you think about this code?

Generate an multi dimensional array to reflect the tree structure

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

Prepare an unordered list with nested nodes

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

The code seems to be quite ok and given a reasonable number of rows (millions of rows aren't) won't hit you too hard, performancewise.

But I think you've asked the wrong question:

Nested sets come into play when you need to traverse hierarchies and it'd be too costly to fetch the whole table in order to find the parent of the parent of a certain node. With adjacency lists you'd need multiple queries to achieve this or let PHP do the work with nested loops (which means O(n^2) worst case).

Either way, nested sets will generally perform way better when finding ancestors is your goal (e.g. find a product in a hierarchy of nested categories).

See this article: Managing Hierarchical Data in MySQL. It will give you a good starting point on how to implement the various queries/updates/insertions/deletions.