If you use nested sets (sometimes referred to as Modified Pre-order Tree Traversal) you can extract the entire tree structure or any subtree within it in tree order with a single query, at the cost of inserts being more expensive, as you need to manage columns which describe an in-order path through thee tree structure.
For django-mptt, I used a structure like this:
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 1 null 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
Which describes a tree which looks like this (with id
representing each item):
1 +-- 2 | +-- 3 | +-- 4 | +-- 5 +-- 6 +-- 7
Or, as a nested set diagram which makes it more obvious how the lft
and rght
values work:
__________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________|
As you can see, to get the entire subtree for a given node, in tree order, you simply have to select all rows which have lft
and rght
values between its lft
and rght
values. It's also simple to retrieve the tree of ancestors for a given node.
The level
column is a bit of denormalisation for convenience more than anything and the tree_id
column allows you to restart the lft
and rght
numbering for each top-level node, which reduces the number of columns affected by inserts, moves and deletions, as the lft
and rght
columns have to be adjusted accordingly when these operations take place in order to create or close gaps. I made some development notes at the time when I was trying to wrap my head around the queries required for each operation.
In terms of actually working with this data to display a tree, I created a tree_item_iterator
utility function which, for each node, should give you sufficient information to generate whatever kind of display you want.
More info about MPTT: