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

Taconite

Looks ok apart from the foreach($query AS $row) that is not needed and will raise an error. – Tearle

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.

Mannerly

Answer 2

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

Desmid