Taxonomy MPTT

Simple,fast and easy to understand example of how to build nested sets
for Drupal taxonomies (or any other adjacency list for that matter).

Two versions a are available, present in branches master and hybrid (hybrid being by far the fastest).

Supports multiple parents.

This module servers as an example of how nested sets could be implemented. The goal is to provide an easy to understand implementation.

Experiences and ideas might be offered to the module Leftandright - Nested Set Taxonomy

Master

A 3-step process implemented as a Drupal batch job.

1. Sort and count depth of all terms (we need this to perform step 2)
2. Count children recursively for all terms (backwards through depth)
3. Traverse entire tree and generate left + right values

Go to the edit page of a vocabulary to generate the nested sets.

To find a sub tree afterwards, e.g. for all terms under tid:14

SELECT c.tid 
FROM taxonomy_mptt parent
INNER JOIN taxonomy_mptt children ON children.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.tid = 14

The SQL is currently MySQL only due to JOINed UPDATEs. As this module is purely for academic purposes, I have no immediate intention of generalizing this. JOINed UPDATEs should be possible with other databases, but Postgres for example, uses another notation. If anyone know how to perform joined updates through PDO, please don't hesitate to tell me.

Performance

Using 916373 terms with a max depth of 11:

1. Presorted and counted distance: 10 - took 76.97954392 seconds
2. Counted children - took 40.79763699 seconds
3. Processed 916373 terms - took 615.57286191 seconds

Total: ~733 seconds

Hybrid

A 3-step process implemented as a Drupal batch job.

1. Count depth of all terms while materialized paths
2. Count children recursively for all terms (backwards through depth)
3. Iterate through all terms (sorted by materialized path) and generate left + right values

Go to the edit page of a vocabulary to generate the nested sets.

To find a sub tree afterwards, e.g. for all terms under tid:14

SELECT c.tid 
FROM taxonomy_mptt parent
INNER JOIN taxonomy_mptt children ON children.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.tid = 14

The SQL is MySQL only due to the same reason as in "master", but also because of step three using database variables.

Performance

Using 916383 terms with a max depth of 11:

1. Materialized paths and counted distance: 11 - took 84.97616386 seconds
2. Counted children - took 20.76042104 seconds
3. Processed 916373 terms - took 33.53683901 seconds

Total: ~140 seconds