| Issue 29: | building an efficient hierarchy | |
| 2 people starred this issue and may be notified of changes. | Back to list |
hi, firstly, this is not a defect as such, more a question about the most efficient way to build a hierarchical tree using django-mptt. i am using django-mptt to build multiple trees with up to (and sometimes exceeding) 50000 nodes, with a varying number of levels in each tree. the general formula i'm using for making the tree is: p = Tree() n1 = Tree(parent=p) n1.save() n2 = Tree(parent=p) n2.save() n3 = Tree(parent=n1) n3.save() ... nothing too radical there. however, on a mysql 5.0 database i am finding quite poor performance as the number of nodes per tree increases - i believe this is related to the various update sql calls that are made when .save() is called on a child (from _create_tree_space for example). is it possible to precompute the tree without calling .save() on each node until the very end and then issue a single/fewer sql to store the hierarchy? if there is a more suitable forum for this question then please let me know. thanks mark.
Oct 12, 2008
Project Member
#1
jonathan.buchanan
Labels:
-Type-Defect Type-Enhancement
Dec 5, 2008
Of course you can! If you have all tree in runtime and want to put it in mysql database you can precompute ALL left/right/level/tree_id attributes before insertion. Try to understand MPTT algorithm - and you will find that easy (: On the other hand - you can make this is two steps: insert your data without mptt attributes at all (take a look into save(raw=True)). And after that use Model.tree.rebuild() from issue#13 (find my patch there). rebuild() uses computation inside python and, thus, _create_tree_space, _create_space or _space_manager are not utilized). Performance is - 1 simple UPDATE query per 1 db ROW. :) The drawback is recursion inside python code. I have no time to make it without recursion now :(. Thus, VERY deep trees may eat VERY much memory and hit python recursion limit.
Dec 5, 2008
Another notice: if you want to insert nodes into existent tree (e.g. using Model.save ()), make sure you have all mptt indexes in your table (lft, right, level, tree_id). But, if you want to initially create tree using my rebuild() function - it is better to temporarily remove all mptt indexes before updating and reenabling after rebuild (). I didnt tested that by myself. But in theory... (:
Dec 5, 2008
Also dont forget mptt preordering! Usually trees have just 1 type of ordering (or 2:
one and "reversed-one"). So, it is good idea to put nodes in valid order in db.
Do this:
<title=root>
<title=asd>
<title=dsa>
<title=zzz>
Even if zzz inserted before asd. order_insertion_by=['title'] will make this trick.
After that Model.objects.order_by('tree_id', 'left') will output PREORDERED tree. If
you add order_insertion_by=['title'] into your mptt.register() call, my rebuild()
function from issue#13 will also utilize it as well.
Sep 20, 2010
rebuild() is in since 0.3. Deferred updates is Issue 46
Status:
Duplicate
Mergedinto: 46 |