Adjacency List Compared to Nested Dial Model

Question

I searched the list of Adjacency and Nested Set Model to find the optimal tree.

So far, I thought that one of the main advantages of the Nested Set model is that I can use one SQL query and some code to get a complete tree. But it is difficult to update / insert nodes, and the whole tree can be easily damaged.

Then I came across these two posts:

Recursive categories with one query?

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

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

What do you think of this code?

Creating a multidimensional 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 quite normal, and given a reasonable number of lines (millions of lines not), you won’t hit you too hard on performance.

But I think you asked the wrong question:

Nested sets come into play when you need a trace hierarchy , and it would be too expensive to get the whole table to find the parent of the parent specific node. Using adjacency lists, you need a few queries to do this, or let PHP do the work with nested loops (which means O (n ^ 2) is the worst case).

In any case, nested sets will usually work better when searching for ancestors is your goal (for example, to find a product in a hierarchy of nested categories).

See this article: Managing Hierarchical Data in MySQL . This will give you a good starting point on how to implement various requests / updates / inserts / deletes.