Nested Datasets Hierarchy Pattern in MySQL

Straight to the point

How do we maintain a hierarchical structure in MySQL tables? Consider the tree which represents various divisions and their subdivisions in the Encyclopedia.

(a) Encyclopedia divisions tree

How can we convert this into a relational model? Or, simply, how can we store this hierarchy in a relational table?

a) One way to do this is, Adjacency List Model. We are not discussing this model here. Refer to this link to know more about this model. This model involves a lot of joins to process complex multi-level hierarchical data.

b) Another way is, Nested Datasets Model. In this model, we will consider the tree as containers. That is, considering the child sub-tree is a container that presents in the parent container.
In this model, we will maintain two ids for each node. One is the left id and another one is the right id.

So, let's the number each node in the above encyclopedia tree.

(b) Tree after we number left and right for every node.

The numbering process is more like traversing the tree in order,

the left side of the root -> left side of subtree -> right side of the subtree -> right side of the root

In every traverse, we are incrementing the id by one.

From the above Fig. b, we can see the child nodes of any node will be in the range of left and right values.

For example, take the node “Maths” as root node, it’s left value is 2 and it’s right value is 7.
So, the child nodes of the “Maths” node will be in the range [2, 7].
In MySQL query, you can get the child nodes of the “Maths” node by using BETWEEN Statement.
ie. BETWEEN left_value AND right_value.

Now, look at these concepts in terms of the queries.

Encyclopedia TABLE SCHEMA :

Table creation query

After populating some initial value, the table will look like,

Don’t worry! You’ll see about the insert query soon.

Select Query to read all children nodes for a given node.

How can we get all children nodes for a given node? Say, we want to get all the section inside the “Maths” department. We can do this with a single self join on the left_value and right_value column irrespective of the depth of the “Maths” department.

select child_node.* from encyclopedia as child_node left join encyclopedia as parent_node on child_node.left_value between parent_node.left_value and parent_node.right_value where parent_node.name = “Maths”;

This query will return,

Inserting a new node under any node:

Say, we want to insert a node with the name “Trigonometry” under the “Maths” department. The query will be,

Begin;

select @target_right := right_value from encyclopedia where name = “Maths”;

update encyclopedia set left_value = left_value + 2 where left_value > @target_right;

update encyclopedia set right_value = right_value + 2 where right_value≥ @target_right;

insert into encyclopedia(name, left_value, right_value) values(“Trigonometry”, @target_right, @target_right + 1);

commit;

Deleting a complete sub-tree:

Say, we need to delete a node with the name “Maths”. Deleting a node should delete its child nodes too. The query will be,

begin;

select @target_left := left_value, @target_right := right_value, @target_width := right_value — left_value + 1 from encyclopedia where name = “Maths”;

delete from encyclopedia where left_value between @target_left and @target_right;

update encyclopedia set right_value = right_value — @target_width where right_value > @target_right;

update encyclopedia set left_value = left_value — @target_width where left_value > @target_right;

commit;

In these ways, we can process the table using two pointers(left and right values).

Conclusion:
The nested data set model is really useful when your requirements need to process more complex, frequent, multi-level hierarchy process. It’s coming with a trade-off “READ vs UPDATE(insert, delete)”.

Please comment on your suggestions on this model.