PHP: sorting data from nested sets
We are currently building a website with a MySQL categorized table containing various competencies and we have noticed that the nested collection model will be optimized for this. Although we have a rather serious problem - the nested set model does not allow for sorting, and we really need this capability. I would like the output to be an array (id, name, depth) , as this function supports (albeit without any sorting):
function tree()
{
$query = 'SELECT node.id, node.name, (COUNT(parent.name) - 1) AS depth FROM test_competence AS node, test_competence AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY node.lft';
$result = mysql_query($query) or die(mysql_error());
while($data = mysql_fetch_assoc($result))
{
$returnarray[] = $data;
}
return $returnarray;
}
I started with a function, but have no idea how to proceed:
function tree_sorted()
{
//Get data
$query = 'SELECT node.id, node.name, node.parent, (COUNT(parent.name) - 1) AS depth FROM test_competence AS node, test_competence AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY node.lft';
$result = mysql_query($query) or die(mysql_error());
//Fetch gotten data
while($data = mysql_fetch_assoc($result))
{
$fetched[$data['depth']][$data['id']] = array($data['name'], $data['parent']);
}
//Sort fetched data
foreach($fetched as $i => $row)
{
asort($row);
$sorted[$i] = $row;
}
//Merge sorted data (???)
foreach($sorted as $i => $arr)
{
foreach($arr as $x => $row)
{
$returnarray[] = array('id' => key($row), 'name' => $row[0], 'depth' => $x);
}
}
Any help would be greatly appreciated. I've googled for different ways to sort data from nested sets, but no good result.
Thanks in advance.
EDIT : I have now tried using the uasort () function, which seems to be correct, but the problem still remains.
a source to share
If you need to sort a set of nodes in a tree and maintain an unlimited number of levels in the tree, may I recommend using pre-ordered tree traversal?
See http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ for an example implementation.
The point is that you are storing the left and right value for each node. You can also store a depth column for each node that tells you what level of the tree it is at. You can use these left and right values to sort the nodes according to their order in the tree and use the depth value to select only a given number of tree levels.
The only notable drawback to this approach is that you must actively maintain these left and right values when changing the node structure.
a source to share
In my experience, using the nested set model is really not required unless you are expecting some really heavy traffic. I'm not sure what you need the hierarchy for, but I would recommend checking if a simple parent table with a cache in front of it would not be much easier to maintain and work with
Again, this of course depends on your application and how worried you are about performance issues.
a source to share
Taking a hit in the dark, since the nested dataset data is by definition already sorted, it looks like you need to convert the data to a different format (usually flat) in order to sort it. The easiest way to achieve this is to simply work with the data, creating a flat dataset as you go.
You already have several options in SQL. When ordering by left ID, you will get a detour in order if I have the correct terminology. This is usually what people want when they list many trees, as it makes sense when they flatten out into a list. I would experiment with a sentence ORDER BY
in SQL; for example ordering by depth will give you a level traversal. Try combining this with node.name
.
a source to share