Django模型的層次結構，以鄰接表或嵌套組 - 最佳方式（帶過濾）

我的Django的應用程序存儲在數據庫中的一些分層數據，如下：現在Django模型的層次結構，以鄰接表或嵌套組 - 最佳方式（帶過濾）

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

，爲了顯示該樹數據jqGrid樹我需要將數據轉換爲鄰接列表或嵌套集合，因爲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。 I 不能更改模型的模式（定義），因爲應用程序（和其他服務）的其他部分依賴於當前結構。

PS。 2.數據庫的背後，是Postgres的，但我想解決住DB無關，如果可能的話

來源

2012-11-15 migajek

這不是尾遞歸，因此它需要大量內存，爲什麼不使用使用隊列或DPS的堆棧的麪包優先搜索算法？爲什麼你會像這樣遍歷層次結構？ – PepperoniPizza

有一種在SQL數據庫中存儲分層數據的算法。它被稱爲修改先序樹遍歷。有關詳細信息，您可以閱讀Storing Hierarchical Data in a Database文章。它將允許您在一個查詢中選擇子樹的所有項目。

Django的存在是一個實現應用它 - django-mptt

其實你需要修改你的數據庫，但是這將包括增加兩個數值列，這樣你就可以離開parent等各個領域不變

來源

2012-11-16 10:04:03 Igor

你可以使用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-15 22:25:00

謝謝，但仍然有一些問題需要實現這一點...我害怕這麼多的查詢將是一個嚴重的性能殺手 – migajek

Django模型的層次結構，以鄰接表或嵌套組 - 最佳方式（帶過濾）

回答

相關問題