Mastering MySQL Hierarchical Queries with the Nested Set Model

Are you using recursive queries for MySQL tree structures? The classic approach stores the parent ID on each child row, which works for small data but becomes inefficient as the hierarchy deepens and the dataset grows.

Typical requirements

Find all descendant departments of a given department.

Count the total number of descendant departments.

Determine whether a node is a leaf.

Improved method: Preorder (nested‑set) traversal

Instead of repeatedly recursing, assign each node a lft (left) and rgt (right) value while traversing the tree. Leaf nodes receive consecutive left/right values; internal nodes enclose the range of their descendants.

After the traversal, the parent_id column can be removed and replaced by lft and rgt columns.

id | name   | lft | rgt | level
---+--------+-----+-----+------
1  | 董事长 | 1   | 20  | 1
2  | 总经理 | 2   | 19  | 2
3  | 产品部 | 3   | 8   | 3
4  | 设计部 | 4   | 5   | 4
4  | 研发部 | 6   | 7   | 4
6  | 行政总监| 9   | 18  | 3
7  | 财核部 |10   |15   | 4
8  | 出纳   |11   |12   | 5
8  | 会计   |13   |14   | 5
10 | 行政部 |16   |17   | 4

Query all descendants

Set the target node's left and right values, then select rows whose lft falls between them:

SET @lft := 9;   -- left of the target node
SET @rgt := 18;  -- right of the target node
SELECT * FROM department WHERE lft BETWEEN @lft AND @rgt ORDER BY lft ASC;

Count descendants

The number of descendants can be calculated without an extra query: Total = (right - left - 1) / 2 Examples:

行政总监子孙数 = (18 - 9 - 1) / 2 = 4
董事长子孙数 = (20 - 1 - 1) / 2 = 9
会计子部门数 = (14 - 13 - 1) / 2 = 0

Determine leaf node

A node is a leaf when right - 1 = left (or equivalently left + 1 = right).

设计部: 5 - 1 = 4  → leaf
董事长: 20 - 1 ≠ 1 → not leaf

Insert a new department

When inserting, shift the lft and rgt values of all nodes to the right of the insertion point by 2, then insert the new row.

SET @lft := 7;   -- left value for the new node
SET @rgt := 8;   -- right value for the new node
SET @level := 5; -- level for 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('新部门', @lft, @rgt, @level);
COMMIT;

Delete a department

Delete a node and collapse the gap by subtracting 2 from the left/right values of subsequent nodes.

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;

Direct child query

Retrieve only the immediate children of a node:

SET @level := 2;   -- level of the parent (e.g., 总经理)
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;

Ancestor path query

Find all ancestors of a node:

SET @lft := 3;   -- left of the target (产品部)
SET @rgt := 8;   -- right of the target
SELECT * FROM department WHERE lft < @lft AND rgt > @rgt ORDER BY lft ASC;

Convert result set to a tree in JavaScript

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 => {
  while (rights.length && 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);
});

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

The only drawback of this method is that every insert or delete requires updating the left/right values of all subsequent nodes by adding or subtracting 2.