Issue 29: building an efficient hierarchy
Status:  Duplicate
Merged:  issue 46
Owner: ----
Closed:  Sep 2010
Reported by mstreatf...@gmail.com, Aug 19, 2008
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
(No comment was entered for this change.)
Labels: -Type-Defect Type-Enhancement
Dec 5, 2008
#2 mocksoul
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
#3 mocksoul
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
#4 mocksoul
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
Project Member #5 craig.ds@gmail.com
rebuild() is in since 0.3. Deferred updates is Issue 46
Status: Duplicate
Mergedinto: 46