MPTT approach to tree structures simplifies the evaluation of parent and child relationship to two numbers comparation. One of the Forrest guys has a lecture on this topic at JavaDays 2020 conference. Although it is a relatively old algorithm, it has one key disadvantage and that is the high cost of writing a new item or moving it in the structure. These operations typically involve the recalculation of a large part of the tree, and if these boundaries are stored elsewhere due to the greater performance of SQL queries, this disadvantage is further multiplied.
For this reason, we have come up with a small mutation in this algorithm (called Pre-allocated Modified Preorder Tree Traversal), which, while accepting certain simplifications, allows you to define an equation that determines boundaries for each tree node so that write operations such as adding, removing or moving a node within the same superior node, which doesn't imply any boundary recalculation requirements at all.
The simplification to be undertaken is to define in advance the maximum number of levels of immersion in the tree, and the maximum number of children per node. At the same time, it is necessary to combine the data type long, which represents about 10 levels of the tree in depth with 55 items in one node.
The library also greatly simplifies the operations of moving nodes between different levels of the tree (including child nodes), although these operations remain just as write-intensive as in the original algorithm.
Implications of the PMPTT algorithm are summarized in this presentation.
For more information see section How to use
- JDK 1.8+
- Commons Logging (1.2.0+)
RDBMS version:
- Darwin library
- Spring framework (5.3.0+), works also on 4.3.X older version although not compilable due to JUnit tests
- MySQL
- Oracle
Do you missing one? Fill a pull request!
Use standard Maven 3 command:
mvn clean install
Start databases:
docker-compose -f docker/docker-compose.yml up
Run your tests in IDE or run:
mvn clean test
Help us maintain at least 80% code coverage!
See separate chapters for details: