Geek asks and answers

How to store a large binary tree

How to store large binary trees (about a thousand in depth). We tried to save in the database in a table with the lines: elem, parent, left_child, right_child but very slowly process this tree (calculate, draw part of it).

Which way do you recommend? (calculation can be done in php). Maybe store it in XML or json (text file) or in some matrices?

+3
source share
3 answers

You can use an array or other linear storage (for example, the id → node relationship) so that each node x has children 2 * x and 2 * x + 1. The problem may be that there are unused identifiers if the tree is not balanced .

Example:

    2---4---8
   /   \   \9
1--     5---10
   \       \11
    3---6---12
       \   \13
        7---14
           \15
0

, - XML, , . XML, , , .

0

I use a structure like the following

id  parent  tree    slug    name    path    children
1   0       1       root    Root    ||          |5|
2   7       1       child-1 Child 1 |1-5-8-7|   |3|

It is very simple to query huge depth trees because the query is linear. Each row has a bit more data, but it speeds up execution.

For example, you can get the whole subtree with a simple query, for example:

$sql = 'SELECT * FROM `'.$this->_table_name.'` WHERE 
            `path` LIKE "%-:parent-%"
            OR `path` LIKE "%|:parent-%"
            OR `path` LIKE "%-:parent|%"
            OR `path` LIKE "%|:parent|%"';

$result = $this->_db->custom_query($sql, array('parent' => $root->id));

And then build the depth array with a simple function:

private function _build_tree(Node $root, $data)
    {
        $mapped_node = array(
            'node' => $root,
            'subnodes' => array()
        );

        if ( !empty($root->children) )
        {
            foreach( $root->children as $child )
            {
                if ( array_key_exists($child, $data) )
                {
                    $mapped_node['subnodes'][] = $this->_build_tree($data[$child], $data);
                }
            }
        }

        return $mapped_node;
    }

ATTENTION! When I return the children and path columns, I break them into arrays for PHP to be able to work better with them.

0
source

More articles:


All Articles