How to store big binary tree

How to store big binary trees (about thousands in depth). We tried to store in database, in table with rows开发者_StackOverflow: elem, parent, left_child, right_child but it's very slow to handle this tree (to calculate, draw a part of it).

Which way you recommend? (calculating may be done in php). May be to store it in XML or json (text file) or in some matrices?

You could use an array or other linear store (e.g. relation id->node value) in the way that each node x has the children 2*x and 2*x+1. The problem might be that there are unused ids if the tree is unbalanced.

Sample:

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

Seems like writing to something like XML as you suggest would be best. Converting to XML and then back when you want to reload it would be pretty straight forward.

I use a structure like 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 super easy to query huge depth trees, because the query is linear. There is a bit more data in each line, but that makes it quicker.

For example you can get a whole subtree with a simple query like:

$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 by 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;
    }

NOTE! When I get back the children and path columns, I split them into arrays for PHP to be able to better work with them.