Load hierarchical data from database into array

Question

I have a table in the database with the following structure/data:

n_id      n_parent_id      ... some other fields ...
====      ===========      =========================
 1         null            ...
 2         null            ...
...
11            1            ...
12            1            ...
...
25            2            ...
...
65           11            ...
66           11            ...
...

This table stores hierarchical data, as can be seen from the sample above. I need to load this into a PHP array in a tree-like fasion, so that the array would contain something like this:

Array
(
    [1] => Array
        (
            [n_id] => 1
            [n_parent_id] => 
            [other_data] => ...
            [children] => Array
                (
                    [11] => Array
                        (
                            [n_id] => 11
                            [n_parent_id] => 1
                            [other_data] => ...
                            [children] => Array
                                 (
                                    [65] => Array
                                        (
                                            [n_id] => 65
                                            [n_parent_id] => 11
                                            [other_data] => ...
                                        )
                                 )
   ... and so on ...
)

I can easily deal with one level:

//ordering will ensure that parent row is always read before children rows
//my data is set up in this way.
$query = "select n_id, n_parent_id, other_data from hierarchy_table order by n_parent_id, n_id";
if(($dbs = $dbh->query($query)) === FALSE) {
    $e = $dbh->errorInfo();
    // ... deal with error
}
$result = array();
while($row = $dbs->fetch(PDO::FETCH_ASSOC)) {
    if(is_null($row['n_parent_id'])) {
        $result[$row['n_id']] = array(
            'n_id' => $row['n_id'],
            'n_parent_id' => null,
            'other_data' => ...,
            'children' => array()
        );
    }
    elseif(isset($result[$row['n_parent_id']])) {
        $result[$row['n_parent_id']]['children'][$row['n_id']] = array(
            'n_id' => $row['n_id'],
            'n_parent_id' => $row['n_parent_id'],
            'other_data' => ...
            children => array()
        );
    }
}

However I can't seem to get my head around extending this to multiple levels without really having to loop recursively over the whole array every time I need to add a row. Naturally, had it been Java or C, I would just store pointers to data structures and that would solve the issue, but in PHP this isn't really that easy. At the end of this all, I will need to send the json_encode of this to the client.

This question covers a similar issue, but I don't have the actual hierarchical information in the database - only parent id's.

Any help on this is appreciated.

EDIT: my database table contains hundreds of thousands of rows, therefore performance is important.

possible duplicate of Recursive function to generate multidimensional array from database result — deceze
– deceze ♦, Commented Mar 24, 2014 at 18:09
@bpositive Do not make pointless/useless edits - they are not helpful and will be reverted. — Aleks G
– Aleks G, Commented Mar 24, 2014 at 19:10
@deceze Thanks for the pointer. The linked question does provide a sort of solution, however in my cases the database table may contains hundreds of thousands of records, therefore the function you provided in that answer will be very-very inefficient... Naturally, scanning/looping over the whole array multiple times is an option, but if at all possible, I'd like to avoid it. — Aleks G
– Aleks G, Commented Mar 24, 2014 at 19:14
Fair enough, but that makes the problem quite a bit harder (as you already know). — deceze
– deceze ♦, Commented Mar 24, 2014 at 20:36
@deceze Yeah, I know... PHP isn't the best language for speed optimisation... — Aleks G
– Aleks G, Commented Mar 24, 2014 at 20:50

Aleks G · Accepted Answer · 2014-03-27 12:29:36Z

After some struggling I managed to get what I need using one pass over the recordset (only reading each record once) - using references. As memory reference support is rather limited in PHP, there are some funny things required to keep thins working (e.g. a new variable name for each row that I'm reading from the DB). Anyway, here's the code that I ended up with (this code only deals with id and parent_id - but it's trivial to read/store further data):

$dbh = new PDO(CONNECT_STRING, USERNAME, PASSWORD);
$dbs = $dbh->query("SELECT n_id, n_parent_id from test_table order by n_parent_id, n_id");
$elems = array();

while(($row = $dbs->fetch(PDO::FETCH_ASSOC)) !== FALSE) {
    $row['children'] = array();
    $vn = "row" . $row['n_id'];
    ${$vn} = $row;
    if(!is_null($row['n_parent_id'])) {
        $vp = "parent" . $row['n_parent_id'];
        if(isset($data[$row['n_parent_id']])) {
            ${$vp} = $data[$row['n_parent_id']];
        }
        else {
            ${$vp} = array('n_id' => $row['n_parent_id'], 'n_parent_id' => null, 'children' => array());
            $data[$row['n_parent_id']] = &${$vp};
        }
        ${$vp}['children'][] = &${$vn};
        $data[$row['n_parent_id']] = ${$vp};
    }
    $data[$row['n_id']] = &${$vn};
}
$dbs->closeCursor();

$result = array_filter($data, function($elem) { return is_null($elem['n_parent_id']); });
print_r($result);

When executed on this data:

mysql> select * from test_table;
+------+-------------+
| n_id | n_parent_id |
+------+-------------+
|    1 |        NULL |
|    2 |        NULL |
|    3 |           1 |
|    4 |           1 |
|    5 |           2 |
|    6 |           2 |
|    7 |           5 |
|    8 |           5 |
+------+-------------+

The last print_r produces this output:

Which is exactly what I was looking for.

lsblsb · Accepted Answer · 2015-10-31 20:07:01Z

Since I was also faced with an almost identical problem and the creative (!) solution by Aleks G did not exactly fullfill my needs, because i save my hierarchical data with the nested set model, here is my solution when working with nested sets (that took a while to implement). The $data array must be sorted on the basis of a preorder traversal.

Usage Example:

$data =
[
    0 => ['ID' => 0, 'depth' => 0],
    1 => ['ID' => 1, 'depth' => 1],
    2 => ['ID' => 2, 'depth' => 2],
    3 => ['ID' => 6, 'depth' => 2],
    4 => ['ID' => 10, 'depth' => 1]
];

$IDs = hierachicDataToArray($data);
print_r($IDs);

$IDs = hierachicDataToArray($data, true);
print_r($IDs);

Output:

Array
(
    [0] => Array
        (
            [1] => Array
                (
                    [2] => 2
                    [6] => 6
                )

            [10] => 10
        )

)

Array
(
    [0] => Array
        (
            [ID] => 0
            [depth] => 0
            [children] => Array
                (
                    [1] => Array
                        (
                            [ID] => 1
                            [depth] => 1
                            [children] => Array
                                (
                                    [2] => Array
                                        (
                                            [ID] => 2
                                            [depth] => 2
                                            [children] => Array
                                                (
                                                )

                                        )

                                    [6] => Array
                                        (
                                            [ID] => 6
                                            [depth] => 2
                                            [children] => Array
                                                (
                                                )

                                        )

                                )

                        )

                    [10] => Array
                        (
                            [ID] => 10
                            [depth] => 1
                            [children] => Array
                                (
                                )

                        )

                )

        )

)

Method:

/**
 * Convert hierarchic data records to a multidimensional array.
 * Expects an array in the form: [<i> => ['ID' => <int ID>, 'depth' => <int depth>, '<string>' => <mixed>, ...]]
 * At least the 'ID' and 'depth' key/value pairs must exist.
 * @author: lsblsb[at]gmx.de
 * @copyright: GPL-3.0
 * 
 * @param array $data The data array.
 * @param bool $incData = false Whether to include additional data or not.
 * @param bool $IDKeys = true Whether to use IDs as key or not (false only possible when $incData = true)
 * 
 * @return array[]
 */
function hierarchicDataToArray(array $data, $incData = false, $IDKeys = true)
{
    $nodes = [];

    foreach($data as $i => $record)
    {
        $ID = $record['ID'];
        $depth = $record['depth'];
        $prevRecord = isset($data[$i-1]) ? $data[$i-1] : false;
        $prevDepth = $prevRecord ? $prevRecord['depth'] : false;
        $prevID = $prevRecord ? $prevRecord['ID'] : false;
        $nextRecord = isset($data[$i+1]) ? $data[$i+1] : false;
        $nextDepth = $nextRecord ? $nextRecord['depth'] : false;
        $nextID = $nextRecord ? $nextRecord['ID'] : false;

        if($prevRecord && $prevDepth >= $depth)
        {
            $pID = $depthIDs[$depth-1];
            if($depth == 1)
            {
                if($incData)
                    $nodes[$pID]['children'][$ID] = &$refs[$ID];
                else
                    $nodes[$pID][$ID] = &$refs[$ID];
            }
            else
            {
                if($incData)
                    $refs[$pID]['children'][$ID] = &$refs[$ID];
                else
                    $refs[$pID][$ID] = &$refs[$ID];
            }
        }

        if($nextRecord && $nextDepth > $depth)
        {
            if($depth == 0)
            {
                if($incData)
                {
                    if(!isset($nodes[$ID])) $nodes[$ID] = $record;
                    $nodes[$ID]['children'][$nextID] = &$refs[$nextID];
                }
                else
                    $nodes[$ID][$nextID] = &$refs[$nextID];
            }
            else
            {
                if($incData)
                {
                    if(!isset($refs[$ID])) $refs[$ID] = $record;
                    $refs[$ID]['children'][$nextID] = &$refs[$nextID];
                }
                else
                    $refs[$ID][$nextID] = &$refs[$nextID];
            }
        }
        else
        {
            $node = $incData ? $record + ['children' => []] : $ID;
            $refs[$ID] = $node;
        }

        if(!$IDKeys && $incData)
        {
            if(!$nextRecord)
            {
                $nodes = array_values($nodes);
                $nodes[0]['children'] = array_values($nodes[0]['children']);
            }
            elseif($nextDepth < $depth)
            {
                $pID = $depthIDs[$depth-1];
                $refs[$pID]['children'] = array_values($refs[$pID]['children']);
            }
        }

        $depthIDs[$depth] = $ID;
    }

    return $nodes;
}

Collectives™ on Stack Overflow

Load hierarchical data from database into array

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related