python - 检索 mptt 查询集的祖先查询集的高效函数

Question

有没有人有一个有效的算法来检索 mptt 查询集的所有祖先？到目前为止我能想到的最好的是这样的:

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    queryset_aggs = queryset.values_list('tree_id', 'level').annotate(max_lft=Max('lft'), min_rght=Min('rght'))
    new_queryset = queryset.none()
    for tree_id, level, max_lft, min_rght in queryset_aggs:
        ancestors = MyModel.objects.filter(
           tree_id=tree_id,
           level__lt=level, 
           lft__lte=max_lft,
           rght__gte=min_rght,
        )
        new_queryset = ancestors | new_queryset
    return new_queryset

这种方法有两个问题:

1. 如果有不相邻的分支，它会失败(即它实际上不起作用)
2. 它非常低效，因为它最终在最终查询中有 number_of_trees*number_of_levels 子句，它可以非常快地变得非常大

我愿意在其他地方缓存祖先，但我想不出一种有效的方法。我考虑过添加一个字段，其中包含一个逗号分隔的祖先 ID 列表，然后在一个 extra 中执行 GROUP_CONCAT(我在 MySQL 中)，但我认为这可能会变得很大/很慢。

Answer 1

我不得不写一次类似的算法。我有一个显示 MPTT 树的 View ，它是一棵非常大的树，所以我无法在 HTML 模板中加载它的所有数据。所以我在初始加载时只显示根节点，并使用 Ajax 加载其他节点。

在我的老板要求我实现“搜索”选项之前，它一直运行良好。搜索必须查看所有节点并在找到匹配项时分解树。我花了一段时间才弄明白这一点，但我终于明白了。这是 a 提出的解决方案:

from django.db.models import Q

def get_parents(self, qs):
    tree_list = {}
    query = Q()
    for node in qs:
        if node.tree_id not in tree_list:
            tree_list[node.tree_id] = []

        parent =  node.parent.pk if node.parent is not None else None,

        if parent not in tree_list[node.tree_id]:
            tree_list[node.tree_id].append(parent)

            query |= Q(lft__lt=node.lft, rght__gt=node.rght, tree_id=node.tree_id)

    return YourModel.objects.filter(query)

它只需要运行两个查询，作为参数传递的初始 qs 和函数返回的最终查询集。 tree_list 是一个字典，用于存储已添加到查询集中的节点，它是一种优化，并不是算法工作所必需的。但由于我正在处理一棵相对较大的树，所以我不得不将其包括在内。

我猜你可以把这个方法变成一个管理器并让它更通用，即让它适用于任何 MPTT 模型而不仅仅是 YourModel