Whether you build your own forum, threaded comments, or categorization system, there will be a moment when you need to save hierarchical structures in a database. Although the tables of relational databases (such as MySQL and PostgreSQL) are flat, there is a fast and effective way to store hierarchical structures. It is called Modified Preorder Tree Traversal (MPTT). MPTT allows you to read tree structures without recursive calls to the database.
Firstly, let's get familiar with the terminology of tree structures. A tree data structure is a nested collection of nodes, starting at the root node and with references to child nodes. There are restrictions: for instance, no node should reference back to create a loop and no reference should be duplicated. The following are some other terms to remember:
- A parent is any node that has references to child nodes.
- Descendants are nodes that can be reached by recursively traversing from a parent to its children. Therefore, a node's descendants will be its child, the child's children, and so on.
- Ancestors are nodes that can be reached by recursively traversing from a child to its parent. Therefore, a node's ancestors will be its parent, the parent's parent, and so on up to the root.
- Siblings are nodes with the same parent.
- A leaf is a node without children.
Now, I'll explain how MPTT works. Imagine laying out your tree horizontally with the root node at the top. Each node in the tree has left and right values. Imagine them as small left and right handles on the left- and right-hand sides of the node. Then, you walk (traverse) around the tree counterclockwise, starting from the root node, and mark each left or right value that you find with a number: 1, 2, 3, and so on. It will look similar to the following diagram:
In the database table of this hierarchical structure, you have a title, left value, and right value for each node.
Now, if you want to get the subtree of the B node with 2 as the left value and 11 as the right value, you will have to select all of the nodes that have a left value between 2 and 11. They are C, D, E, and F.
To get all of the ancestors of the D node with 5 as the left value and 10 as the right value, you have to select all of the nodes that have a left value that is less than 5 and a right value that is more than 10. These would be B and A.
To get the number of the descendants for a node, you can use the following formula:
descendants = (right - left - 1) / 2
Therefore, the number of descendants for the B node can be calculated as shown in the following formula:
(11 - 2 - 1) / 2 = 4
If we want to attach the E node to the C node, we will have to update the left and right values only for the nodes of their first common ancestor, the B node. Then, the C node will still have 3 as the left value; the E node will get 4 as the left value and 5 as the right value; the right value of the C node will become 6; the left value of the D node will become 7; the left value of the F node will stay at 8; the others will also remain the same.
Similarly, there are other tree-related operations with nodes in MPTT. It might be too complicated to manage all of this by yourself for every hierarchical structure in your project. Luckily, there is a Django app called django-mptt that has a long history of handling these algorithms and provides a straightforward API to handle the tree structures. Another app, django-treebeard, has also been tried and tested and gained additional traction as a powerful alternative when it replaced MPTT in django CMS 3.1. In this chapter, you will learn how to use these helper apps.