Efficient Hierarchical Menu Storage in MySQL: Adjacency List vs Closure Table

Background

In many backend admin systems menus are hierarchical; a simple parent_id column works for small data but causes performance and maintenance problems when the tree grows or nodes are moved.

Problems with plain adjacency list

Fetching a subtree requires recursive queries or loading all rows into memory, leading to N+1 queries or high memory usage.

MySQL 8 supports WITH RECURSIVE but older versions (5.7) cannot use it, and deep recursion hurts performance.

Moving a node forces recomputation of relationships for all descendants, which is error‑prone under concurrency.

Very deep recursion can cause stack overflow.

Three mainstream storage schemes

Adjacency List

Each row stores only its direct parent_id. Simple to insert and move a node, but subtree queries are slow because they need recursion.

CREATE TABLE sys_menu (
    id BIGINT AUTO_INCREMENT PRIMARY KEY COMMENT 'Menu ID',
    menu_name VARCHAR(50) NOT NULL COMMENT 'Menu name',
    parent_id BIGINT COMMENT 'Parent menu ID, NULL for root',
    menu_url VARCHAR(255) COMMENT 'Menu URL',
    sort INT DEFAULT 0 COMMENT 'Order'
) COMMENT 'System menu table';

Path Enumeration

Each row stores the full path (e.g. “/1/2/3”). Subtree queries become a simple LIKE, but inserting or moving a node requires updating the path of every descendant, and the path length limits depth.

CREATE TABLE sys_menu (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    menu_name VARCHAR(50) NOT NULL,
    parent_id BIGINT,
    menu_path VARCHAR(1000) COMMENT 'Full path like /1/2/3',
    menu_url VARCHAR(255),
    sort INT DEFAULT 0
);

Closure Table

A separate table stores every ancestor‑descendant pair together with the depth. One JOIN can retrieve any subtree or ancestor chain without recursion, at the cost of extra storage and write‑side complexity.

-- Main menu table (keeps adjacency list)
CREATE TABLE sys_menu (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    menu_name VARCHAR(50) NOT NULL,
    parent_id BIGINT,
    menu_url VARCHAR(255),
    sort INT DEFAULT 0
);

-- Closure table
CREATE TABLE sys_menu_closure (
    ancestor_id BIGINT NOT NULL,
    descendant_id BIGINT NOT NULL,
    depth INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id)
);

Comparison

Insert speed: adjacency > path > closure. Subtree query: closure fastest, path moderate, adjacency slowest. Moving nodes: adjacency fast, path requires bulk updates, closure needs rebuilding the affected rows. Storage overhead grows from adjacency (small) to closure (large).

Recommended hybrid solution

Combine adjacency list for fast inserts/moves and a closure table for efficient read‑heavy queries. The main table keeps parent_id, while the closure table is updated in the same transaction whenever a node is added, moved, or deleted.

SpringBoot + MyBatis‑Plus implementation

Entity classes SysMenu and SysMenuClosure map to the two tables. Mapper interfaces provide methods for direct child lookup, batch insertion into the closure table, and queries such as selectSubTree. Service layer handles the transactional logic: insert the menu, then build its closure rows; when moving a node, update parent_id and rebuild the closure for the affected subtree.

@Service
@Transactional
public class SysMenuService {
    // addMenu, moveMenu, rebuildMenuClosure, getMenuTree …
}

Performance tips

Wrap both table writes in a single @Transactional method to keep data consistent.

Use batchInsert for closure rows instead of looping INSERT statements.

When rebuilding closures after a move, process the current node first, then recurse to children.

Replace the O(n²) in‑memory tree builder with a grouping‑by map to achieve O(n) complexity.

Other use cases

The same pattern works for product categories, organizational charts, threaded comments, permission trees, or any domain that requires “unlimited depth + frequent queries”.