Return to Question

2. Nested Set (a.k.a Modified Preorder Tree Traversal)

2. Nested Set (a.k.a Modified Preorder Tree Traversal (MPTT))

MySQL

• Use session variables for Adjacency List

MySQL/MariaDB

• Use session variables for Adjacency List
• Use CTEs in MySQL 8.0 or MariaDB 10.2

• One more Nested Intervals vs. Adjacency List comparison: the best comparison of Adjacency List, Materialized Path, Nested Set and Nested Interval I've found.
• Models for hierarchical data: slides with good explanations of tradeoffs and example usage
• Representing hierarchies in MySQL: very good overview of Nested Set in particular
• Hierarchical data in RDBMSs: most comprehensive and well-organized set of links I've seen, but not much in the way of explanation

• Uses separate join table with: ancestor, descendant, depth (optional)
• Cheap ancestry and descendants
• Writes costs O(log n) (size of subtree) for insert, updates, deletes
• Normalized encoding: good for RDBMS statistics & query planner in joins
• Requires multiple rows per node

• Column: lineage (e.g. /parent/child/grandchild/etc...)
• Cheap descendants via prefix query (e.g. LEFT(lineage, #) = '/enumerated/path')
• Writes costs O(log n) (size of subtree) for insert, updates, deletes
• Non-relational: relies on Array datatype or serialized string format

• Like nested set, but with real/float/decimal so that the encoding isn't volatile (inexpensive move/insert/delete)
• Has real/float/decimal representation/precision issues
• Matrix encoding variant adds ancestor encoding (materialized path) for "free", but with added trickiness of linear algebra.

• General summary
• 2008 offers HierarchyId data type appears to help with Lineage Column approach and expand the depth that can be represented.

• One more Nested Intervals vs. Adjacency List comparison: the best comparison of Adjacency List, Materialized Path, Nested Set, and Nested Interval I've found.
• Models for hierarchical data: slides with good explanations of tradeoffs and example usage
• Representing hierarchies in MySQL: very good overview of Nested Set in particular
• Hierarchical data in RDBMSs: a most comprehensive and well-organized set of links I've seen, but not much in the way of explanation

• Uses separate join table with ancestor, descendant, depth (optional)
• Cheap ancestry and descendants
• Writes costs O(log n) (size of the subtree) for insert, updates, deletes
• Normalized encoding: good for RDBMS statistics & query planner in joins
• Requires multiple rows per node

• Column: lineage (e.g. /parent/child/grandchild/etc...)
• Cheap descendants via prefix query (e.g. LEFT(lineage, #) = '/enumerated/path')
• Writes costs O(log n) (size of the subtree) for insert, updates, deletes
• Non-relational: relies on Array datatype or serialized string format

• Like nested set, but with real/float/decimal so that the encoding isn't volatile (inexpensive move/insert/delete)
• Has real/float/decimal representation/precision issues
• Matrix encoding variant adds ancestor encoding (materialized path) for "free", but with the added trickiness of linear algebra.

• General summary
• 2008 offers HierarchyId data type that appears to help with the Lineage Column approach and expand the depth that can be represented.