CODEWITHSUNDEEP
phpmysqlsortingnested-sets
Ivar
Ivar

Reputation: 4392

PHP: Sort data from nested sets

We're currently building a website with a categorized MySQL table containing various competences, and we noticed that the nested set model would be optimized for this. Although, we've got a pretty serious problem - the nested set model doesn't allow any sorting, and we really need that possibility. I'd like the output data to be array(id, name, depth), as this function supports (though without any kind of 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've started with a function but have no idea how to continue:

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 without any good result.

Thank you in advance.

EDIT: Now I've tried some with the uasort() function which feels to be the right way, but the problem still remain.

Upvotes: 1

Views: 3137

Answers (3)

Alistair Evans
Alistair Evans

Reputation: 36483

If you need sort a set of nodes in a tree, and maintain unlimited numbers of levels in the tree, might 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 maintain a left and right value for each node. You could also maintain a depth column for each node, which tells which level of the tree it is in. You can use these left and right values to sort nodes by their order in the tree, and use the depth value to only select a given number of levels of the tree.

The only notable downside of this approach is that you have to actively maintain those left and right values when altering the structure of the nodes.

Upvotes: 1

staticsan
staticsan

Reputation: 30555

Taking a stab in the dark, since nested set-tree data is, by definition, already sorted, it sounds like you need to convert the data into another format (usually a flat one) in order to sort it. The easiest way to achieve this is to simply work through the data, creating a flat dataset as you go.

You do already have a few options in the SQL. Ordering by the Left ID gets you in-order traversal, if I have the terminology correct. This is usually what people want when they list a set-tree as it makes sense when flattened into a list. I'd be experimenting with the ORDER BY clause in the SQL; for example, ordering by the depth parameter would give you a level-order traversal. Try combining that with node.name.

Upvotes: 0

n3rd
n3rd

Reputation: 6089

In my experience using the nested set model is not really necessary unless you expect some really heavy traffic. I'm not sure what exactly you need the hierarchy for, but I would recommend checking whether a simple parent-son-table with a cache in front of it wouldn't suffice, it's much easier to maintain and work with

Again, this of course depends on your application and how worried you are about performance issues.

Upvotes: 0

Related Questions