1

我的 django 应用程序在数据库中存储了一些分层数据，如下所示：

 class Foo(Model):
     # ... fields
     parent = ForeignKey('self', null = True)

现在，为了在 jqGrid Tree 中显示该树数据，我需要将该数据转换为邻接列表或嵌套集，因为 jqGrid 支持这两种方法。

我编写了构建邻接列表的简单函数，如下所示（伪代码）

list=[]
def build_list(parent = None, level = 0)
    data = Foo.objects.select_related().filter(parent=parent).annotate(sub_count = Count('foo'))
    for x in objects:
        obj = {
        'name': x.name,
        'id': x.pk,
        'level': level,
        'isLeaf': x.sub_count == 0
        }
    list.append(obj)
    if x.sub_count > 0:
        build_list(x.pk, level + 1)

但是，随着记录数量的增加，我担心这种递归。

有没有更好的方法来做到这一点？

PS。我无法更改模型的架构（定义），因为应用程序（和其他服务）的其他部分依赖于当前结构。

PS。2. 后面的数据库是 Postgres，但如果可能的话，我希望解决方案保持 db-agnostic

4

2 回答 2

2

有一种算法用于在 SQL 数据库中存储分层数据。它被称为修改前序树遍历。您可以阅读在数据库中存储分层数据一文了解详细信息。它将允许您在一个查询中选择子树的所有项目。

对于 Django，有一个实现它的应用程序 -django-mptt

实际上，您将需要修改数据库，但这将包括添加两个数字列，因此您可以保留parent所有其他字段不变

于 2012-11-16T10:04:03.700 回答
1

您可以使用 BFS 来避免内存问题：

未经测试的代码：

def example_bfs():
    roots = Foo.objects.filter(parent=None).annotate(sub_count = Count('foo'))
    q = []
    q = list(roots)
    tree = []
    if q:
        iter = q.pop(0)
    else:
        return tree
    while iter:
        dict = {}
        objs = []
        childs = Foo.objects.filter(parent = iter).annotate(sub_count = Count('foo'))
        for x in childs:
            obj ={}
            objs.append(obj)
        dict[iter] = objs
        tree.append(dict)
        q += list(childs)
        level += 1 
        try:
            iter = q.pop(0)
        except:
            return tree
    return tree
于 2012-11-15T22:25:00.777 回答