高效函数以获取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，用逗号分隔，然后在额外的查询中使用GROUP_CONCAT（我用的是MySQL），但我觉得这样可能会变得很大/很慢。

Answer 1

我之前也写过一个类似的算法。我有一个视图要展示一个MPTT树，这棵树非常大，所以我不能把所有的数据都加载到HTML模板里。因此，我只在初始加载时显示了根节点，然后用Ajax来加载其他节点。

这个方法运行得很好，直到我老板让我加一个“搜索”选项。这个搜索需要在所有节点中查找，并在找到匹配项时展开树。花了我一段时间才搞明白这个怎么做，但最后我解决了。下面是我想到的解决方案：

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。

Answer 2

这样做怎么样：

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    new_queryset = queryset.none()
    for obj in queryset:
        new_queryset = new_queryset | obj.get_ancestors()
return new_queryset

这仍然是len(queryset)的条件。你可以通过先处理一下，去掉那些在queryset中是其他对象祖先的对象，来稍微减少一些条件，比如这样：

min_obj_set = []
for obj in queryset.order_by('tree_id', '-level'):
    for obj2 in min_obj_set:
        if obj.is_ancestor_of(obj2):
            break
    else:
        min_obj_set.append(obj)

虽然上面的代码只是个例子，但如果你的queryset里有很多对象，使用二叉搜索树（BST）可能会更好。

不过，你得测试一下这样做是否能比更大的数据库查询速度更快。