MySQL SELECT Tree Parent IDs

Question

How can I sort the records of a SELECT statement so that they represent a valid tree?

All of my attempts show sub-nodes nested under wrong parent nodes. What is the most reliable way to achieve this ordering?

Data

ID      Parent ID      Title
--------------------------------------------
0       NULL           Root
1       0              Node A
2       0              Node B
3       1              Sub-Node C
4       1              Sub-Node D
5       3              Sub-Node E

Output

ID      Parent ID      Title
--------------------------------------------
0       NULL           Root
1       0              Node A
3       1              Sub-Node C
5       3              Sub-Node E
4       1              Sub-Node D
2       0              Node B

Data Visualisation

Root
    Node A
        Sub-Node C
            Sub-Node E
        Sub-Node D
    Node B

Solution 1

Following the advice of @Blindy I have implemented this sort with PHP. Here are the two functions that seem to solve this issue relatively easily.

protected function _sort_helper(&$input, &$output, $parent_id) {
    foreach ($input as $key => $item)
        if ($item->parent_id == $parent_id) {
            $output[] = $item;
            unset($input[$key]);

            // Sort nested!!
            $this->_sort_helper(&$input, &$output, $item->id);
        }
}

protected function sort_items_into_tree($items) {
    $tree = array();
    $this->_sort_helper(&$items, &$tree, null);
    return $tree;
}

I would be interested to hear if there is a simpler approach, but this does seem to work.

Solution 2

You can use Nested Sets. Check out this article:

Managing Hierarchical Data in MySQL

The author describes a few different methods for building hierarchies in SQL, complete with example queries. It's a very good read about this subject!

Solution 3

MySQL has no support for recursive queries

You will need to self join the table as many times as the maximum hierarchy level is, but still it's pretty ugly to get one row for each hierarchy level that way.

See these posts for some ideas and examples:

Category Hierarchy (PHP/MySQL)

how can we write mysql query where parent id have a child id and next time child id is a parent id how can i do?

Comments

[RouR]

Call-time pass-by-reference has been removed in php5.4

[Lea Hayes]

@RouR If I recall this just means that you need to change the way you invoke _sort_helper. Instead try using $this->_sort_helper($input, $output, $item->id); and $this->_sort_helper($items, $tree, null);. Let me know if this helps and I will update my answer accordingly :)

[Broco]

I know this is an old question but just for future reference: Nested Sets are good for tree-structures that are being read most of the time but rarely changed (INSERT, UPDATE, DELETE) because writing options in nested sets are extremely costly: robsite.net/…

[Emil Vikström]

Thank you, Broco! I agree somewhat with that solution. Feel free to post your own answer. It's in essence a materialized view!