将分层数据从数据库加载到数组中

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.

Answer 1

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:

Array
(
    [1] => Array
        (
            [n_id] => 1
            [n_parent_id] => 
            [children] => Array
                (
                    [3] => Array
                        (
                            [n_id] => 3
                            [n_parent_id] => 1
                            [children] => Array
                                (
                                )

                        )

                    [4] => Array
                        (
                            [n_id] => 4
                            [n_parent_id] => 1
                            [children] => Array
                                (
                                )

                        )

                )

        )

    [2] => Array
        (
            [n_id] => 2
            [n_parent_id] => 
            [children] => Array
                (
                    [5] => Array
                        (
                            [n_id] => 5
                            [n_parent_id] => 2
                            [children] => Array
                                (
                                    [7] => Array
                                        (
                                            [n_id] => 7
                                            [n_parent_id] => 5
                                            [children] => Array
                                                (
                                                )

                                        )

                                    [8] => Array
                                        (
                                            [n_id] => 8
                                            [n_parent_id] => 5
                                            [children] => Array
                                                (
                                                )

                                        )

                                )

                        )

                    [6] => Array
                        (
                            [n_id] => 6
                            [n_parent_id] => 2
                            [children] => Array
                                (
                                )

                        )

                )

        )

)

Which is exactly what I was looking for.