Web applications often need a way to represent and store hierarchies.
A menu with its submenus. A category with its subcategories. A comment and its replies.
Storing the hierarchy, and later reconstructing it from the stored data is just a part of the puzzle. We also need a way to find the parents or children of an item. We need to be able to re-parent an item (move it to another part of the hierarchy). Finally, there is the need to order items in a way that reflects their position in the hierarchy.
There are several ways to do this, each with its own pros and cons:
- Adjacency list
- Nested set
- Closure table (aka bridge table)
- Materialized path (path enumeration)
Looking at our storage requirements, materialized path starts to look like a simpler option:
Storing the hierarchy in a materialized path requires only one column in the table.
Storing the hierarchy in a closure table requires an additional table with a large number of rows.
The closure table also won’t work if you need to sort items by hierarchy, and re-parenting items is slow and costly. On the other hand, it’s normalized, which can’t be said for materialized paths.
So, let’s give materialized paths a shot. We’ll then see how our encoding trick makes it even better.