如何存储大型二叉树

Question

如何存储大型二叉树（深度约为数千）。

我们尝试将其存储在数据库中，使用带有行的表：elem、parent、left_child、right_child，但是处理这个树非常慢（计算、绘制其中一部分）。

您推荐哪种方式？（可以在php中进行计算）。可以将其存储在XML或json（文本文件）中还是在某些矩阵中？

- Larry Foobar

---

标准的SQL设置对于这样的结构非常糟糕。表示很简单，但检索却非常麻烦。不过，Oracle和Postgres(?)通过“connect by prior”扩展支持递归查询。 - Marc B

一棵典型的树有多少个节点？一棵深度为1000层的二叉树可能包含2^1000个节点 - 这是一个非常大的数字（即使对于DBMS来说也是如此）。 - NealB

2 OZ_，不，我们使用关系型数据库（postgres）。 - Larry Foobar

2 NealB，是的，树可能有1000个层级... - Larry Foobar

是的，2^1000 = 1.07150861 × 10^301，你确定它是一棵树而不是一个链表吗？这个树有什么用？也许最好平衡这棵树或者使用像数据库设计中使用的B*树？ - rurouni

Answer 1

看起来像你建议的那样写入XML会是最好的选择。将其转换为XML，然后在重新加载时再转换回来将会非常简单明了。

- Ian Burris

---

所有东西都可以存储在XML中，但是有太多的选项：嵌套元素或引用ID的属性，甚至包含一些二进制格式的CDATA部分...;-) - rurouni

Answer 2

你可以使用数组或其他线性存储方式（例如关系id->节点值）来实现每个节点x都有2*x和2*x+1两个孩子节点。问题可能在于，如果树不平衡，则会有未使用的id。

示例：

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

- rurouni

---

如果您想显示子树，只需计算所需的ID并批量查找相应的值即可。 - rurouni

Answer 3

我使用以下结构：

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|

查询深度巨大的树非常容易，因为查询是线性的。

每行中有更多的数据，但这使得查询更快。

例如，您可以通过简单的查询获取整个子树：

$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));

然后通过一个简单的函数构建深度数组：

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

注意！当我获取到孩子和路径列时，我将它们分割成数组，以便PHP更好地处理它们。

- Gadratil