Insert/update efficient solution to store hierarchical data in MySQL?

Question

I understand there are several patterns for storing hierarchical data in a relational database such as using adjacency lists, nested sets, etc.

However, the drawback with something like a nested set is that if you frequently have to update nodes by adding/removing children, there's a high cost to then update the rest of the table.

What's a solution for a scenario such as the following example:

                 (Parent1)
               /     |      \
         (Child1) (Child2)  (Child3)
         /           |
[Child1a, Child1b][Child2a] 

where it will be a frequent requirement to update to:

              (Parent1)
               /     |      \
         (Child1) (Child4)  (Child5)
         /           |         \
   [Child1a, Child1b][Child4a] [Child5a]

etc.

My data will be nested at most 3 levels deep, but the idea is that the solution should support many of this little trees stored in the table, and children can be updated/modified in a performant manner.

Answer 1

The least expensive method of storing hierarchical data in terms of storage and complexity of updates is Adjacency List.

• Defining a child's parent updates exactly 1 row
• Moving a child to a new parent updates exactly 1 row
• Removing a subtree of N nodes is a deletion of N rows
• Adding a subtree of N nodes is an insertion of N rows

The other techniques like Nested Sets or Path Enumeration or Closure Table require more complex updates, but the tradeoff is that those techniques support arbitrary-depth operations without needing recursive query syntax.

If you can guarantee that the tree is never deeper than three levels, you can do many operations with Adjacency List with a couple of simple outer joins.

Note that MySQL 8.0 is implementing recursive query syntax, so the workaround techniques may become less necessary in the future.