Applying the Nested Set Model for Hierarchical Department Queries in MySQL

Problem Statement

Traditional tree storage stores a parent ID on each child node, which works for small data sets but becomes inefficient when the hierarchy grows large and complex.

Requirements

Find all descendant departments of a given department.

Count the total number of descendant departments.

Determine whether a node is a leaf.

Improved Approach – Nested Set Model

The nested set model assigns a left (lft) and right (rgt) value to each node during a depth‑first traversal. A node’s descendants have lft and rgt values between the node’s own lft and rgt.

Table department structure:

id          部门编号
name        部门名称
level       所在树层级
parent_id   上级部门编号
lft         左值
rgt         右值

Query All Descendants

To retrieve a department and all its descendants, use a BETWEEN query on the left and right values.

SET @lft := 9; -- left value of the target department
SET @rgt := 18; -- right value of the target department
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

Example: for a node with lft=9 and rgt=18, total descendants = (18‑9‑1)/2 = 4.

Leaf Detection

A node is a leaf when rgt - 1 = lft (or equivalently lft + 1 = rgt ).

-- Example check
SELECT id, name, (rgt - 1 = lft) AS is_leaf FROM department;

Insert a New Department

When inserting, shift the left/right values of all nodes that appear after 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;
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

Deletion is the inverse: shrink the left/right values of following nodes by 2 and then remove the target row.

SET @lft := 7; -- left value of node to delete
SET @rgt := 8; -- right value 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 Children Query

To fetch only the immediate children, match the level and ensure the child’s left/right are directly inside the parent’s range.

SET @level := 2; -- parent level
SET @lft   := 2; -- parent left
SET @rgt   := 19; -- parent right
SELECT * FROM department WHERE lft > @lft AND rgt < @rgt AND level = @level + 1;

Ancestor Path Query

Retrieve the full ancestor chain of a node:

SET @lft := 3; -- left of target node
SET @rgt := 8; -- right of target node
SELECT * FROM department WHERE lft < @lft AND rgt > @rgt ORDER BY lft ASC;

JavaScript Example for Tree Rendering

The article also provides a JS snippet that converts a flat list (with lft/rgt/level) into a hierarchical tree structure.

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}
];
// compute parent_id and leaf flag, then build recursive tree

Conclusion

The nested set model solves the original three problems efficiently, at the cost of extra work when inserting or deleting nodes because the surrounding edges must be adjusted.

Readers are encouraged to discuss, comment, and share alternative solutions.