Mastering Hierarchical Queries: Nested Set Model for Efficient Tree Operations in MySQL

Problem Statement

When a tree‑like structure is stored by keeping the parent ID on each child row, it works for small data sets but becomes inefficient as the data grows and business requirements become more complex.

The typical requirements are:

Find all descendant departments of a given department.

Count the total number of descendant departments.

Determine whether a node is a leaf.

Nested Set Model Overview

Instead of storing only parent_id, each node receives two additional values: lft (left) and rgt (right). Traversing the tree from the root, we assign incremental left values, and when we finish a subtree we assign the right value. After this process every node has a left/right pair that uniquely defines its position.

Example diagram:

After assigning left/right values we can drop the parent_id column and keep only lft and rgt.

Query All Descendants

To retrieve a department and all of its descendants, select rows whose lft is between the left and right values of the target node.

SET @lft := 9;
SET @rgt := 18;
SELECT * FROM department WHERE lft BETWEEN @lft AND @rgt ORDER BY lft ASC;
/* The BETWEEN also returns the node itself; use > and < if you only need children. */

Count Descendants

The number of descendants can be calculated without a separate query:

Formula: total = (right - left - 1) / 2

-- Example calculations
-- Director of Administration
-- (18 - 9 - 1) / 2 = 4
-- CEO
-- (20 - 1 - 1) / 2 = 9
-- Accountant (leaf)
-- (14 - 13 - 1) / 2 = 0

Leaf Detection

A node is a leaf when its right value is exactly one greater than its left value (or left + 1 = right).

-- Leaf test
IF rgt - 1 = lft THEN /* leaf */ END IF;
-- Or equivalently
IF lft + 1 = rgt THEN /* leaf */ END IF;

Insert Department

When inserting a new node, all existing nodes with a left or right value greater than the insertion point must be increased by 2. This is usually done inside a transaction.

SET @lft := 7;   -- left value for the new node
SET @rgt := 8;   -- right value for the new node
SET @level := 5; -- depth of the new node
BEGIN;
UPDATE department SET lft = lft + 2 WHERE lft > @lft;
UPDATE department SET rgt = rgt + 2 WHERE rgt >= @lft;
INSERT INTO department (name, lft, rgt, level) VALUES ('New Dept', @lft, @rgt, @level);
COMMIT;

Delete Department

Deletion is the inverse operation: after removing a node, shift subsequent left/right values down by 2.

SET @lft := 7;   -- left of node to delete
SET @rgt := 8;   -- right of node to delete
BEGIN;
UPDATE department SET lft = lft - 2 WHERE lft > @lft;
UPDATE department SET rgt = rgt - 2 WHERE rgt > @lft;
DELETE FROM department WHERE lft = @lft AND rgt = @rgt;
COMMIT;

Query Direct Children

To fetch only the immediate children of a department, match the level and ensure the left/right values are strictly inside the parent’s interval.

SET @level := 2;   -- level of the parent (e.g., General Manager)
SET @lft   := 2;   -- left of the parent
SET @rgt   := 19;  -- right of the parent
SELECT * FROM department
WHERE lft > @lft AND rgt < @rgt AND level = @level + 1;

Query Ancestor Path

To obtain the full ancestry chain of a node, select rows whose left is less than the node’s left and right is greater than the node’s right.

SET @lft := 3;   -- left of the target node (e.g., Product Dept)
SET @rgt := 8;   -- right of the target node
SELECT * FROM department WHERE lft < @lft AND rgt > @rgt ORDER BY lft ASC;

JavaScript Tree Builder (Demo)

let list = [
  {id:1, name:'root', lft:1, rgt:8, level:1},
  {id:2, name:'child', lft:2, rgt:7, level:2},
  {id:3, name:'grandson', lft:3, rgt:4, level:3},
  {id:4, name:'grandson2', lft:5, rgt:6, level:3}
];
let rights = [];
let mp = {};
list.forEach(item => {
  if (rights.length > 0) {
    while (rights[rights.length-1] < item.rgt) rights.pop();
  }
  let _level = rights.length;
  item._level = _level;
  mp[_level] = item.id;
  item.parent_id = (_level-1) in mp ? mp[_level-1] : null;
  item.is_leaf = item.lft === item.rgt - 1;
  rights.push(item.rgt);
});

const recursive = (_list, parent_id = null) => {
  const tree = [];
  _list.forEach(item => {
    if (item.parent_id === parent_id) {
      const children = recursive(_list, item.id);
      tree.push({ ...item, children: children.length ? children : (item.is_leaf ? null : []) });
    }
  });
  return tree;
};
console.log(recursive(list));

Conclusion

The nested set model provides fast read‑operations for hierarchical data, solving the three common queries without recursive joins. Its main drawback is that every insert or delete requires updating the left/right values of all subsequent nodes, which can be costly for very large trees.