计算受限深度树中子树的数量

Question

我在MySQL中使用每个节点的parent_id字段有一个树结构。该结构相当大，但只有大约8层深。每个节点还有一个child_counter字段。

我正在寻找一种高性能的方法来计算（和更新）每个节点所拥有的子节点的数量（通过儿童，包括儿童等），最好不要使用太多的SQL调用。我不认为这会超快，只是够好。

我希望有一些方法可以在算法迭代时进行批量更新。

Answer 1

我已经实现了这样的东西，但不完全。你能够在每个节点上存储一个“深度”整数，来标记它们在树中的深度吗？如果是这样，你可以用8个查询来做到这一点，如果索引适当，将是非常合理的。像这样的东西我认为（没有mysql方便）。你会从最低深度​​查询（即8）向上： UPDATE Node SET child_counter = ((SELECT SUM(child_counter) FROM Node WHERE parent_id = id) + (SELECT COUNT(0) FROM Node WHERE parent_id = id)) WHERE depth = x

Answer 2

这里是一个很好的文章：Managing Hierarchical Data in MySQL

您目前使用邻接表型号额外的数列。但实际上，您尝试从分层数据中获得的结果看起来好像使用嵌套集模型可以更容易地进行建模。