CODEWITHSUNDEEP
phpmysqlsorting
Lea Hayes
Lea Hayes

Reputation: 64196

MySQL SELECT Tree Parent IDs

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

Upvotes: 3

Views: 22100

Answers (5)

Emil Vikström
Emil Vikström

Reputation: 91902

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!

Upvotes: 13

Jared Eckersley
Jared Eckersley

Reputation: 21

Here is another way to do your PHP function.

function buildTree() {
  $data = array();
  $pointers = array();

  $sql = "SELECT ID,PARENT,TITLE FROM TREE ORDER BY TITLE ASC";
  $res = $this->db->query($sql);

  while ($row = $res->fetch(PDO::FETCH_ASSOC)) {
    if(!isset($pointers[$row['ID']])) {
      $pointers[$row['ID']] = $row;
    }

    if(!empty($row['PARENT'])) {
      if(!isset($pointers[$row['PARENT']])) {
        $pointers[$row['PARENT']] = $row;
      }
      $pointers[$row['PARENT']][$row['ID']] =  &$pointers[$row['ID']];
    } else {
      $data[$row['ID']] = &$pointers[$row['ID']]; // This is our top level
    }
  }

  unset($pointers);
  return $data;
}

Upvotes: 0

ElizaWy
ElizaWy

Reputation: 121

I just finished this recursive function, and thought it was an elegant way about the problem. Here's what I did once I made a basic SELECT mysql query:

function orderChildren($data){
    $tree = array();
    foreach($data as $value){
        if($value['parent_id'] == null){  // Values without parents
            $tree[$value['id']] = $this->goodParenting($value, $data);
        }
    }
    return $tree;
}

private function goodParenting($parent, $childPool){
    foreach($childPool as $child){
        if($parent['id'] == $child['parent_id']){
            $parent['children'][$child['id']] = $this->goodParenting($child, $childPool);
        }
    }
    return $parent;
}

Upvotes: 0

Lea Hayes
Lea Hayes

Reputation: 64196

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.

Upvotes: 5

user330315
user330315

Reputation:

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?

Upvotes: 4

Related Questions