The MPTT algorithm is, as the name states, a modification of pre-order tree traversal; each node of the tree has two extra values associated to it, to assist in the traversal of the tree.
Data structure
| Node ID | Name | Left MPTT value | Right MPTT value |
|---|---|---|---|
| 1 | (Root) | 1 | 16 |
| 2 | Articles | 2 | 11 |
| 5 | Fiction | 3 | 8 |
| 7 | Fantasy | 4 | 5 |
| 8 | Sci-fi | 6 | 7 |
| 6 | Reference | 9 | 10 |
| 3 | Portfolio | 12 | 13 |
| 4 | Contact | 14 | 15 |
SELECT * from Pages order by mpttLeft asc
Numbers are assigned such that a path can be traced around the tree, taking in every node. The path here starts at (Root), flowing down the left, around the bottom of the Fiction subtree, then up to the Reference branch of Articles, and from there to the other branches of (Root), before flowing back to (Root).
Note that leaf nodes (those with no children) have Left and Right values immediately after each other; Portfolio, for example, is 12/13. Note also that the parent of a node has a smaller Left and a bigger Right; this can be used to trace up the tree finding parent nodes, until you hit a Left of 1 (meaning the root node). For example, Fantasy (4/5) has a parent of Fiction (3/8), which has a parent of Articles (2/11).
Operations
- Addition
-
To add a node, simply add 2 to all the values after that node, then insert the node into place. As an example, inserting a "Horror" section under Fiction is a simple matter of:
- Finding where to insert "Horror" (after 7)
- Adding 2 to every Left value past 7
- Adding 2 to every Right value past 7
- Inserting a new row, "Horror", with Left=8 and Right=9
- Removal
-
A very similar process is used to delete a node from the tree. For example, to delete "Fantasy":
- Fetch the Right value of the node (in this case, 5)
- Subtract 2 from every Left value past 5
- Subtract 2 from every Right value past 5
- Remove the node row