1

私のdjangoアプリケーションは、次のようにいくつかの階層データをDBに保存します。

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

ここで、そのツリーデータをjqGridツリーに表示するには、そのデータを隣接リストまたはネストされたセットに変換する必要があります。これら2つの方法は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に依存しないようにしたいです。

4

2 に答える 2

2

SQLデータベースに階層データを格納するためのアルゴリズムがあります。これは、 Modified PreorderTreeTraversalと呼ばれます。詳細については、「データベースへの階層データの保存」の記事を参照してください。これにより、1つのクエリでサブツリーのすべてのアイテムを選択できます。

Djangoには、それを実装するアプリケーションがあります-django-mptt

実際にはデータベースを変更する必要がありますが、これには2つの数値列の追加が含まれるため、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 に答える