Choosing a tree implementation

Treebeard provides four different tree implementations, each with the same API:

1. Adjacency List (AL): fast writes at the cost of slow reads. Not appropriate for use cases where reads occur more often than writes.

2. Materialized Path (MP): the most compatible and commonly used implementation.

3. Nested Sets (NS): efficient reads at the cost of high maintenance on write/delete operations.

4. PostgreSQL Ltree (LT) (experimental): PostgreSQL-specific efficient tree implementation.

More details can be found on the documentation page for each implementation.

The table below illustrates the relative performance of each implementation for various operations. Actual timings differ by database engine and system resources, so the data are only meaningful to compare the relative strengths of each tree implementation.

The code used to generate the benchmarks can be found in the source code at tests/test_benchmarks.py, which can be run with:

TEST_BENCHMARKS=1 tox -- tests/test_benchmarks.py --benchmark-group-by func

Operation	AL	NS	MP	LT
Insertion: 100 nodes	172ms	421ms	204ms	204ms
Insertion: 100 nodes with node_order_by supplied in random order	103ms	1200ms	1500ms	920ms
Read: fetch all descendants of a root	14ms	0.9ms	0.7ms	0.6ms
Move: root to child, child to root	23ms	15ms	6ms	3ms
Delete: delete a root and all descendants	35ms	10ms	8ms	5ms