Django自递归外键过滤查询所有子项的问题

Question

我有一个模型，其中包含自引用的外键关系：

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')

现在我想获取一个人所有多层级的子项。我该如何编写Django查询？它需要像递归函数一样工作。

- Ahsan

Answer 1

你可以随时向你的模型添加递归函数：

编辑：根据SeomGi Han的更正进行了修正

def get_all_children(self, include_self=True):
    r = []
    if include_self:
        r.append(self)
    for c in Person.objects.filter(parent=self):
        _r = c.get_all_children(include_self=True)
        if 0 < len(_r):
            r.extend(_r)
    return r

如果你有很多递归或数据，请不要使用此方法...

仍然建议像 errx 建议的那样使用 mptt。

编辑：2021年，由于此答案仍然受到关注 :/

改用 django-tree-queries ！

- sunn0

---

应该使用get_all_children()作为函数调用，并且需要使用r = r + c.get_all_children()，否则你会得到嵌套的列表。我似乎没有编辑它自己的权限。 - alan

根据评论更新了代码。如果每个人都可以编辑所有帖子，我们将会面临一个大问题 :) - sunn0

我认为内部函数调用中也应该有 include_self=True。否则，在每次递归时，我们只是下降了一个更深的层次，从未向 r 添加任何内容。只有在进行这种更改后，它才能正确地工作。 - andy

你的解决方案很好，但是未经测试。最后，r是一个嵌套的空列表。请考虑修复它。 - bobleujr

https://dev59.com/MJ_ha4cB1Zd3GeqP5NII#42676632 - user4426017

Answer 2

你应该了解MPTT（Modified Preorder Tree Traversal）算法。这里有Django实现的代码。 https://github.com/django-mptt/django-mptt/

- errx

---

需要使用第三方解决方案吗？还有其他方法吗？ - Ahsan

@Ashan：你可以随时在这里阅读相关内容：http://dev.mysql.com/tech-resources/articles/hierarchical-data.html，然后自己编写代码。 - Tomasz Zieliński

Answer 3

sunn0的建议非常好，但是get_all_children()返回的结果有点奇怪。它会返回类似于[Person1，[Person3，Person4]，[]]这样的内容。应该将其更改为以下内容。

def get_all_children(self, include_self=True):
    r = []
    if include_self:
        r.append(self)
    for c in Person.objects.filter(parent=self):
        _r = c.get_all_children(include_self=True)
        if 0 < len(_r):
            r.extend(_r)
    return r

- SeomGi Han

Answer 4

如果您知道树的最大深度，可以尝试以下方法（未经测试）：

Person.objects.filter(Q(parent=my_person)|Q(parent__parent=my_person)| Q(parent__parent__parent=my_person))

- Tomasz Zieliński

Answer 5

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')



    def get_children(self):
          children = list()
          children.append(self)
          for child in self.children.all():
              children.extend(children.get_children())
          return children

get_children() 会使用相关名称获取实例的所有子项，然后对找到的子项递归调用get_children()，直到找不到更多的数据/子项。

- Ahsan Iqbal

---

这个答案可以通过添加解释来改进。 - Sean

完成，现在可以了吗？ - Ahsan Iqbal

Answer 6

我也会使用QuerySet编写，因为这样可以让您链接它们。 我将提供检索所有子项和所有父项的答案。

class PersonQuerySet(QuerySet):
    def descendants(self, person):
        q = Q(pk=person.pk)
        for child in person.children.all():
            q |= Q(pk__in=self.descendants(child))
        return self.filter(q)

    def ancestors(self, person):
        q = Q(pk=person.pk)
        if person.parent:
            q |= Q(pk__in=self.ancestors(person.parent))
        return self.filter(q)

现在我们需要将PersonQuerySet设置为管理器。

class Person(TimeStampedModel):
    name = models.CharField(max_length=32)
    parent = models.ForeignKey('self', null=True, blank=True, related_name='children')

    people = PersonQuerySet.as_manager()

---

所以这是最终的查询。

albert_einstein = Person.people.get(name='Albert Einstein')
bernhard_einstein = Person.peole.get(name='Bernhard Caesar Einstein')
einstein_folks = Person.people.descendants(albert_einstein).ancestors(bernhard_einstein)

---

注意： 以下解决方案与之前的其他答案一样慢。我已经检查了每次递归到其子/父级时数据库的访问情况。（如果有人能通过一些优化和缓存进一步改进，这将更好，也许在查询之前预取相关数据）。同时，mptt更实用。

- Yeo

Answer 7

我知道这已经过时了，但是可能会有人受益。

     def get_all_children(self, container=None):
         if container is None:
             container = []
         result = container
         for child in self.children.all():
             result.append(child)
             if child.children.count() > 0:
                 child.get_all_children(result)
         return result

然后，只需将此作为 property（如果适用的话，也可以是 cached_property）添加到模型中，以便在任何实例上调用。

- yusuf.oguntola

---

这并没有回答问题者的问题，即“获取一个人的所有多级子代”... 实际上，这只会获取一个人的直接子代（即一级）。 - Yeo

感谢 @Yeo，我可能误解了问题。我刚刚更新了我的回答，其中包含我在一个项目中使用的类似代码段。 - yusuf.oguntola

Answer 8

我曾经遇到过一个非常类似的业务问题，即给定一个团队成员，我需要找出他下面的所有团队成员。但是由于员工数量很大，递归解决方案非常低效，而且我的API从服务器那里得到了超时错误。

被接受的解决方案会取得节点，进入它的第一个子节点并一直深入到层次结构的底部。然后再返回到第二个子节点（如果存在），再次深入到底部。简而言之，它会逐个探索所有节点并将所有成员附加到数组中。这会导致大量的数据库调用，如果要探索大量节点，则应该避免使用此方法。我提出的解决方案按层获取节点。数据库调用次数等于层数。请查看此SO链接以获取解决方案。

- Shubhanshu

Answer 9

这是我编写的代码，用于获取所有通过它们的“child”字段连接的帖子的所有步骤

steps = Steps.objects.filter(post = post) 
steps_ids = steps.values_list('id', flat=True) 

获取“steps”的所有子代（包括嵌套子代）：

objects   = Steps.objects.filter(child__in=steps_ids) 
while objects:
    steps     = steps | objects 
    steps_ids = objects.values_list('id', flat=True) 
    objects   = Steps.objects.filter(child__in=steps_ids) 

- Augustin Guyonnet