Storing trees and hierarchies in MySQL

Storing hierarchical data can be challenging, frustrating, and extremely efficient. When investigating strategies for relational database storage, two come to mind: adjacency list and nested set. This post will focus on the former.

Database structure
In the adjacency list model, each item in the table contains a reference to its parent, or NULL if it’s at the top level. This makes the table structure very simple table with only three fields in the most basic implementation. Therefore, you could actually update it manually if needed.

CREATE TABLE category
(
        id INT AUTO_INCREMENT PRIMARY KEY,
        name VARCHAR(16) NOT NULL,
        id_parent INT DEFAULT NULL
);

Retrieve the tree in PHP
First, pull all the rows from the db table into an array. Then, pass the array to the function below and it will return a nested object. Watch out for circular references. Conceptually, this code is recursively going through each node and adding it to the current level if it belongs there.

function buildTree($nodes, $id = 0)
{
	$tree = array();

	if(is_array($nodes))
	{
		foreach($nodes as $node)
			if($node->id_parent == $id)
				array_push($tree, $node);

		for($x = 0; $x < count($tree); $x++)
			$tree[$x]->children = buildTree($nodes, $tree[$x]->id);

		return $tree;
	}

	return null;
}

Conclusion
This function is not the most efficient operation to do on each request, but ideally you would cache the result and only update when the tree structure changes. For a more robust solution, consider the nested set model.

For more reading, here’s a great article by Mike Hillyer titled Managing Hierarchical Data in MySQL.

Next ArticleButton-Hacking the Lenovo Yoga