Oftentimes when building a website or web application you will encounter the need for a hierarchical structure. It can be for menus, simulating a folder structure or a category hierarchy.
Usually, for a tree structure to be useful
- A node (item in the tree) can have a parent - or if not, it will be at the root of the tree
- All immediate children of a node can be fetched
- All children and the children's children can be fetched
- Nodes can be moved to another parent
There are several approaches to implementing tree structures with a relational database.
The simple parent-child approach
The naive, down-to-business aproach is to simply add a parent ID to the database table of the item.
Advantages:
- Easy to implement
- Inserting or updating data is quick as it is confined to a single row
- Querying is quick as long as it only ever queries the immediate children or immediate parent of a node
Disadvantages
- Traversing the tree - or parts hereof - is slow as it has to work its way down the tree
- Protection against circular references - setting the parent of a node to a child of the same node - becomes more difficult the further the distance between the nodes
Nested Sets
The nested set model is to number the nodes according to a tree traversal, which visits each node twice, assigning numbers in the order of visiting, and at both visits.
This leaves two numbers for each node, which are stored as two attributes - left and right. From the start, the first root node gets left attribute set to 1, if it has child nodes, the first child node gets the next number (2) as left attribute and if it in turn has a child node, that gets the next number (3) as left attribute. Are there no child nodes, the right attribute gets the next number (4) before moving on to the next sibling node. Are there no siblings, the parent node's right attribute is set to the next number (5) and so on.
- Root node 1 (left 1, right 8)
- Child node 1 (left 2, right 5)
- Child's child node 1 (left 3, right 4)
- Child node 2(left 6, right 7)
- Root node 2 (left 9, right 10)
Advantages
- Querying becomes inexpensive as hierarchy membership can be determined by comparing the left and right numbers
Disadvantages
- Adding, removing or moving a node requires renumbering a potentially large portion of the tree and is therefore expensive.
Laravel and Nested Sets
If you want to use Nested Sets in Laravel, the Baum package by Estanislau Trepat implements this pattern in an easy-to-use Composer package.
Materialized Paths
The Materialized Paths pattern is a way to have a tree hierarchy of nodes
In addition to the node data, it also stores the id(s) of the node’s ancestors or path as a string.
For example with the same tree structure as Nested Sets, we can illustrate Materialized Paths as follows:
- Root node 1 (id: 1, path: /)
- Child node 1 (id: 2, path /1/)
- Child's child node 1 (id: 3, path /1/2/)
- Child node 2(id: 4, path /1/)
- Root node 2 (id: 5, path /)
Materialized Paths are appropriate for ordered trees (e.g. menus, commercial categories, folder structures) and big trees that must be queried efficiently (e.g. threaded posts).
Advantages
- You can fetch all descendants of a node in a single query, no matter how deep the tree.
Drawbacks
- Insertions/moves/deletes require additional operations - in a much smaller scale than Nested Sets, though, as only a small portion of the tree needs to be recalculated for ordering and only child nodes to a moved node needs to have their paths updated
Laravel and Materialized Paths
If you want to utilize Materialized Paths in Laravel, we have created a Materialized Model package, ready to be used in recent Laravel versions.
