計算受限深度樹中子樹的數量

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

您目前使用鄰接表型號額外的數列。但實際上，您嘗試從分層數據中獲得的結果看起來好像使用嵌套集模型可以更容易地進行建模。