Django MPTT documentation¶

Contents:

If you’re new to django-mptt, you may want to start with these documents to get you up and running:

Overview ¶

Contents

Overview
- What is Modified Preorder Tree Traversal?
- What is django-mptt?
  - Feature overview

What is Modified Preorder Tree Traversal?¶

MPTT is a technique for storing hierarchical data in a database. The aim is to make retrieval operations very efficient.

The trade-off for this efficiency is that performing inserts and moving items around the tree is more involved, as there’s some extra work required to keep the tree structure in a good state at all times.

Here’s a good article about MPTT to whet your appetite and provide details about how the technique itself works:

Trees in SQL

Storing Hierarchical Data in a Database

Managing Hierarchical Data in MySQL

What is `django-mptt`?¶

django-mptt is a reusable Django app which aims to make it easy for you to use MPTT with your own Django models.

It takes care of the details of managing a database table as a tree structure and provides tools for working with trees of model instances.

Feature overview ¶

Simple registration of models - fields required for tree structure will be added automatically.
The tree structure is automatically updated when you create or delete model instances, or change an instance’s parent.
Each level of the tree is automatically sorted by a field (or fields) of your choice.
New model methods are added to each registered model for:
- changing position in the tree
- retrieving ancestors, siblings, descendants
- counting descendants
- other tree-related operations
A TreeManager manager is added to all registered models. This provides methods to:
- move nodes around a tree, or into a different tree
- insert a node anywhere in a tree
- rebuild the MPTT fields for the tree (useful when you do bulk updates outside of django)
Form fields for tree models.
Utility functions for tree models.
Template tags and filters for rendering trees.
Translations for:
- Danish
- French
- German
- Polish

Installation ¶

Contents

Installation
- Official releases
- Development version

Official releases ¶

Official releases are available from PyPI. You can install it using the pip:

pip install django-mptt

You can also download the .zip distribution file and unpack it. Inside is a script named setup.py. Enter this command:

python setup.py install

…and the package will install automatically.

Development version ¶

Alternatively, you can get the latest source from our git repository:

git clone git://github.com/django-mptt/django-mptt.git django-mptt

Add the resulting folder to your PYTHONPATH or symlink the mptt directory inside it into a directory which is on your PYTHONPATH, such as your Python installation’s site-packages directory.

You can verify that the application is available on your PYTHONPATH by opening a Python interpreter and entering the following commands:

>>> import mptt
>>> mptt.VERSION
(0, 5, '+dev')

When you want to update your copy of the source code, run git pull from within the django-mptt directory.

Caution

The development version may contain bugs which are not present in the release version and introduce backwards-incompatible changes.

If you’re tracking master, keep an eye on the recent Commit History before you update your copy of the source code.

Tutorial¶

The Problem¶

You’ve created a Django project, and you need to manage some hierarchical data. For instance you’ve got a bunch of hierarchical pages in a CMS, and sometimes pages are children of other pages

Now suppose you want to show a breadcrumb on your site, like this:

Home > Products > Food > Meat > Spam > Spammy McDelicious

To get all those page titles you might do something like this:

titles = []
while page:
    titles.append(page.title)
    page = page.parent

That’s one database query for each page in the breadcrumb, and database queries are slow. Let’s do this a better way.

The Solution¶

Modified Preorder Tree Traversal can be a bit daunting at first, but it’s one of the best ways to solve this problem.

If you want to go into the details, there’s a good explanation here: Storing Hierarchical Data in a Database or Managing Hierarchical Data in Mysql

tl;dr: MPTT makes most tree operations much cheaper in terms of queries. In fact all these operations take at most one query, and sometimes zero:

get descendants of a node
get ancestors of a node
get all nodes at a given level
get leaf nodes

And this one takes zero queries:

count the descendants of a given node

Enough intro. Let’s get started.

Getting started¶

Add `mptt` To `INSTALLED_APPS`¶

As with most Django applications, you should add mptt to the INSTALLED_APPS in your settings.py file:

INSTALLED_APPS = (
    'django.contrib.auth',
    # ...
    'mptt',
)

Set up your model¶

Start with a basic subclass of MPTTModel, something like this:

from django.db import models
from mptt.models import MPTTModel, TreeForeignKey

class Genre(MPTTModel):
    name = models.CharField(max_length=50, unique=True)
    parent = TreeForeignKey('self', on_delete=models.CASCADE, null=True, blank=True, related_name='children')

    class MPTTMeta:
        order_insertion_by = ['name']

You must define a parent field which is a TreeForeignKey to 'self'. A TreeForeignKey is just a regular ForeignKey that renders form fields differently in the admin and a few other places.

Because you’re inheriting from MPTTModel, your model will also have a number of other fields: level, lft, rght, and tree_id. These fields are managed by the MPTT algorithm. Most of the time you won’t need to use these fields directly.

That MPTTMeta class adds some tweaks to django-mptt - in this case, just order_insertion_by. This indicates the natural ordering of the data in the tree.

Now create and apply the migrations to create the table in the database:

python manage.py makemigrations <your_app>
python manage.py migrate

Create some data¶

Fire up a django shell:

python manage.py shell

Now create some data to test:

from myapp.models import Genre
rock = Genre.objects.create(name="Rock")
blues = Genre.objects.create(name="Blues")
Genre.objects.create(name="Hard Rock", parent=rock)
Genre.objects.create(name="Pop Rock", parent=rock)

Make a view¶

This one’s pretty simple for now. Add this lightweight view to your views.py:

def show_genres(request):
    return render(request, "genres.html", {'genres': Genre.objects.all()})

And add a URL for it in urls.py:

(r'^genres/$', show_genres),

Template¶

django-mptt includes some template tags for making this bit easy too. Create a template called genres.html in your template directory and put this in it:

{% load mptt_tags %}
<ul>
    {% recursetree genres %}
        <li>
            {{ node.name }}
            {% if not node.is_leaf_node %}
                <ul class="children">
                    {{ children }}
                </ul>
            {% endif %}
        </li>
    {% endrecursetree %}
</ul>

That recursetree tag will recursively render that template fragment for all the nodes. Try it out by going to /genres/.

There’s more; check out the docs for custom admin-site stuff, more template tags, tree rebuild functions etc.

Now you can stop thinking about how to do trees, and start making a great django app!

`order_insertion_by` gotcha¶

In the example above, we used order_insertion_by option, which makes django-mptt order items in the tree automatically, using name key. What does this mean, technically? Well, in case you add items in an unordered manner, django-mptt will update the database, so they will be ordered in the tree.

So why this is exactly a gotcha?

Well, it is not. As long as you don’t keep instances with references to old data. But chances are you do keep them and you don’t even know about this.

In case you do, you will need to reload your items from the database, or else you will be left with strange bugs, looking like data inconsistency.

The sole reason behind that is we can’t actually tell Django to reload every single instance of django.db.models.Model based on the table row. You will need to reload manually, by calling Model.refresh_from_db().

For example, using that model from the previous code snippet:

>>> root = Genre.objects.create(name="")
#
# Bear in mind, that we're going to add children in an unordered
# manner:
#
>>> b = OrderedInsertion.objects.create(name="b", parent=root)
>>> a = OrderedInsertion.objects.create(name="a", parent=root)
#
# At this point, the tree will be reorganized in the database
# and unless you will refresh the 'b' instance, it will be left
# containing old data, which in turn will lead to bugs like:
#
>>> a in a.get_ancestors(include_self=True)
True
>>> b in b.get_ancestors(include_self=True)
False
#
# What? That's wrong! Let's reload
#
>>> b.refresh_from_db()
>>> b in b.get_ancestors(include_self=True)
True
# Everything's back to normal.

Topic docs:

Models and Managers ¶

Contents

Setting up a Django model for MPTT ¶

Start with a basic subclass of MPTTModel, something like this:

from django.db import models
from mptt.models import MPTTModel, TreeForeignKey

class Genre(MPTTModel):
    name = models.CharField(max_length=50, unique=True)
    parent = TreeForeignKey('self', on_delete=models.CASCADE, null=True, blank=True, related_name='children')

You must define a parent field which is a ForeignKey to 'self'. Recommended: use TreeForeignKey. You can call it something different if you want - see Model Options below.

Because you’re inheriting from MPTTModel, your model will also have a number of other fields: level, lft, rght, and tree_id. Most of the time you won’t need to use these fields directly, but it’s helpful to know they’re there.

Please note that if you are using multi-inheritance, MPTTModel should usually be the first class to be inherited from:

class Genre(MPTTModel,Foo,Bar):
    name = models.CharField(max_length=50, unique=True)

Since MPTTModel inherits from models.Model, this is very important when you have “diamond-style” multiple inheritance : you inherit from two Models that both inherit from the same base class (e.g. models.Model) . In that case, If MPTTModel is not the first Model, you may get errors at Model validation, like AttributeError: 'NoneType' object has no attribute 'name'.

Model Options ¶

Sometimes you might want to change the names of the above fields, for instance if you’ve already got a field named level and you want to avoid conflicts.

To change the names, create an MPTTMeta class inside your class:

class Genre(MPTTModel):
    name = models.CharField(max_length=50, unique=True)
    parent = TreeForeignKey('self', on_delete=models.CASCADE, null=True, blank=True, related_name='children')

    class MPTTMeta:
        level_attr = 'mptt_level'
        order_insertion_by=['name']

The available options for the MPTTMeta class are:

parent_attr

The name of a field which relates the model back to itself such that each instance can be a child of another instance. Defaults to 'parent'.

Users are responsible for setting this field up on the model class, which can be done like so:

parent = TreeForeignKey('self', on_delete=models.CASCADE, null=True, blank=True, related_name='children')

For the following four arguments, if fields with the given names do not exist, they will be added to the model dynamically:

left_attr

The name of a field which contains the left tree node edge indicator, which should be a PositiveIntegerField. Defaults to 'lft'.

right_attr

The name of a field which contains the right tree node edge indicator, which should be a PositiveIntegerField. Defaults to 'rght'.

tree_id_attr

The name of a field which contains the tree id of each node, which should be a PositiveIntegerField. Defaults to 'tree_id'.

Items which do not have a parent are considered to be “root” nodes in the tree and will be allocated a new tree id. All descendants of root nodes will be given the same tree id as their root node.

level_attr

The name of a field which contains the (zero-based) level at which an item sits in the tree, which should be a PositiveIntegerField. Defaults to 'level'.

For example, root nodes would have a level of 0 and their immediate children would have have a level of 1.

order_insertion_by

A list of field names which should define ordering when new tree nodes are being inserted or existing nodes are being reparented, with the most significant ordering field name first. Defaults to [].

It is assumed that any field identified as defining ordering will never be NULL in the database.

Note

This will require an extra database query to determine where nodes should be positioned when they are being saved. This option is handy if you’re maintaining mostly static structures, such as trees of categories, which should always be in alphabetical order.

Warning

Please take extra caution in case you keep the references to the in-database objects when using this field. In cases of insertion or other updates, where django-mptt will need to re-order the tree you will most likely be left with dangling references. Please see order_insertion_by gotcha for details.

Registration of existing models ¶

The preferred way to do model registration in django-mptt is by subclassing MPTTModel.

However, sometimes that doesn’t quite work. For instance, suppose you want to modify Django’s Group model to be hierarchical.

You can’t subclass MPTTModel without modifying the Group source. Instead, you can do:

import mptt
from mptt.fields import TreeForeignKey
from django.contrib.auth.models import Group

# add a parent foreign key
TreeForeignKey(Group, on_delete=models.CASCADE, blank=True, null=True).contribute_to_class(Group, 'parent')

mptt.register(Group, order_insertion_by=['name'])

MPTTModel instance methods ¶

Subclasses of MPTTModel have the following instance methods:

`get_ancestors(ascending=False, include_self=False)`¶

Creates a QuerySet containing the ancestors of the model instance.

These default to being in descending order (root ancestor first, immediate parent last); passing True for the ascending argument will reverse the ordering (immediate parent first, root ancestor last).

If include_self is True, the QuerySet will also include the model instance itself.