有效计算树中存储的树叶

我有一个Django项目，它有两个模型：组和人员。组可以包含Person对象或其他Group对象。组不能形成一个循环（即组A包含包含组A的组B），这导致树形结构，其中个人对象是叶子。有效计算树中存储的树叶

我的问题是 - 如何使用尽可能少的SQL查询来计算高级组（如根组）中包含的所有Group对象和Person对象？

与O（N）天真的方法（其中N是亚组＃），SQL查询将是：

def Group(models.Model): 
    name = models.CharField(max_length=150) 
    parent_group = models.ForeignKey('self', related_name=child_groups, null=True, blank=True) 

    # returns tuple (# of subgroups, # of person objects) 
    def count_objects(self): 
     count = (self.child_groups.count(), self.people.count()) 
     for child_group in self.child_groups.all(): 
      # this adds tuples together (e.g: (1,2) and (1,2) make (2,4)) 
      tuple(map(operator.add, count, child_group.count_objects())) 

def Person(models.Model): 
    user = models.ForeignKey(User) 
    picture = models.ImageSpecField(...) 
    group = models.ForeignKey('Group', related_name="people")

是否有改善这种方式，或者我应该只存储组对象中的这些值？

来源

2012-08-29 Temuz

所以这是一个存在的问题，许多其他人已经解决。如果您使用的Django，检查了这一点： http://django-mptt.github.com/django-mptt/index.html

来源

2012-08-29 03:32:55 Temuz

+1对于mptt，可能是为这类任务存储树的最佳方法。 –

在Postgres的你可以使用recursive查询，虽然在Django对此没有直接的支持。
另外，你可以考虑denormalising计数，可能有库来做到这一点。快速谷歌给了我：http://pypi.python.org/pypi/django-composition/
如果你必须经常选择相同的值，他们并没有改变那么多，你可以尝试缓存它们。

来源

2012-08-29 03:38:17 Wolph

有效计算树中存储的树叶

回答

相关问题