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.