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

You are very correct with your observation, I spent the past 2 days looking for a good implementation for a hierarchy data set. I found people that preferred the nested data model over the adjacent data list.

I personally prefer adjacent data list implementation because it is easy to understand, and intuitive; create, update and delete operations is quite simple to implement on parent and child data, the only downside I can say, is that you'd need to write an ugly SQL query to get all sub list from a parent code.

You can use this video to understand a bit more about this topic. Phil Waclawski: Using hierarchical data in MySQL trees vs nests