Tree Structures & Hierarchical Data

Relevant source files

• backend/sql/mysql/init_snowflake_test_data.sql
• backend/sql/mysql/init_test_data.sql
• backend/sql/postgresql/init_snowflake_test_data.sql
• backend/sql/postgresql/init_test_data.sql
• backend/utils/build_tree.py

Purpose and Scope

This document details how the system manages hierarchical data structures, specifically Menu trees and Department trees. It covers the data models using self-referential parent_id patterns, the tree building utilities in backend/utils/build_tree.py CRUD operations with hierarchical constraints, and frontend-specific adaptations for vben5 admin.

For information about role-based access control and menu permissions, see 6.3. For database schema and ORM relationships, see 7.2.

---

Hierarchical Data Overview

The system implements two primary tree structures:

Structure	Purpose	Self-Referential Field	Frontend Usage
Menu Tree	Navigation hierarchy and permission structure	parent_id	Sidebar navigation via vben5
Department Tree	Organizational hierarchy	parent_id	Department selection and data filtering

Both structures use the same underlying pattern: flat database tables with parent_id foreign keys that reference the same table, transformed into nested tree structures via utility functions.

Sources: backend/app/admin/service/menu_service.py1-137 backend/app/admin/service/dept_service.py1-125

---

Tree Building Utilities

Core Tree Building Module

The backend/utils/build_tree.py module provides utility functions that transform flat database query results with parent_id references into nested tree structures with children arrays.

Diagram: Tree Building Data Flow

Tree Building Algorithms

The get_tree_data() function at backend/utils/build_tree.py71-97 provides two algorithms for constructing hierarchical structures, controlled by the BuildTreeType enum:

Algorithm	Enum Value	Function	Performance	Use Case
Traversal	BuildTreeType.traversal	traversal_to_tree()	O(n)	Default, production use
Recursive	BuildTreeType.recursive	recursive_to_tree()	O(n²)	Alternative, slower

Traversal Algorithm (traversal_to_tree at backend/utils/build_tree.py25-50)

This is the default algorithm. It builds the tree in a single pass:

1. Creates a dictionary mapping node['id'] to node objects for O(1) lookup
2. Iterates through nodes once:
   • If parent_id is None, adds node to root-level tree list
   • Otherwise, looks up parent in dictionary and appends node to parent['children']
   • If parent not found, adds node to root-level (orphaned nodes)
3. Returns the tree list

Recursive Algorithm (recursive_to_tree at backend/utils/build_tree.py53-68)

This algorithm recursively builds the tree:

1. For each node with matching parent_id, recursively finds its children
2. If children exist, assigns them to node['children']
3. Appends node to tree

The recursive approach is noted in comments as having significant performance impact due to repeated iterations over the full node list.

Data Transformation Example

Diagram: Flat to Tree Transformation

The get_tree_nodes() function at backend/utils/build_tree.py10-22 handles serialization and optional sorting before tree construction. It calls select_list_serialize() to convert ORM model instances to dictionaries, then optionally sorts by the specified sort_key (default: 'sort').

Sources: backend/utils/build_tree.py10-22 backend/utils/build_tree.py25-50 backend/utils/build_tree.py53-68 backend/utils/build_tree.py71-97

---

Menu Tree Implementation

Menu Service Tree Operations

The MenuService class in backend/app/admin/service/menu_service.py provides three tree-related operations:

Diagram: Menu Tree Data Flow

get_tree() - Administrative Menu Tree

The MenuService.get_tree() method at backend/app/admin/service/menu_service.py33-45 returns the complete menu tree for administrative purposes, with optional filtering by title and status. It calls menu_dao.get_all() to retrieve matching menus, then passes them to get_tree_data() for tree construction. This endpoint is used in admin interfaces to display and manage the full menu hierarchy.

get_sidebar() - User-Specific Sidebar

The MenuService.get_sidebar() method at backend/app/admin/service/menu_service.py48-70 generates a user-specific sidebar navigation structure based on permissions:

1. Superuser: Calls menu_dao.get_sidebar(db, None) to retrieve all menus
2. Regular User: Collects menu IDs from request.user.roles relationships, then calls menu_dao.get_sidebar(db, list(menu_ids)) to retrieve authorized menus
3. Empty Permissions: Returns empty list

The method uses get_vben5_tree_data() instead of get_tree_data() to format the tree structure according to vben5 admin frontend sidebar component requirements.

Sources: backend/app/admin/service/menu_service.py48-70 backend/app/admin/api/v1/sys/menu.py16-19 backend/app/admin/api/v1/sys/menu.py30-37

Role-Menu Tree Relationship

The RoleService.get_menu_tree() method at backend/app/admin/service/role_service.py67-81 returns the menu tree structure for a specific role. After validating the role exists via role_dao.get(), it retrieves the role's assigned menus using role_dao.get_menus() and constructs the tree with get_tree_data(). This is used when configuring role permissions to display which menus are assigned to the role. The API endpoint is exposed at GET /sys/role/{pk}/menus.

Sources: backend/app/admin/service/role_service.py67-81 backend/app/admin/api/v1/sys/role.py32-38

---

Department Tree Implementation

Department Service Tree Operations

The DeptService class in backend/app/admin/service/dept_service.py manages the organizational hierarchy tree.

Diagram: Department Tree Operations and Constraints

get_tree() - Department Hierarchy

The DeptService.get_tree() method at backend/app/admin/service/dept_service.py34-57 returns the department tree with optional filtering by name, leader, phone, and status. It calls dept_dao.get_all() with a request_user parameter that enables row-level security filtering through the data permission system (see 6.4), ensuring users only see departments within their data permission scope. The filtered results are then passed to get_tree_data() for tree construction.

Sources: backend/app/admin/service/dept_service.py34-57 backend/app/admin/api/v1/sys/dept.py24-36

---

Hierarchical Constraints and Validations

Both Menu and Department trees enforce strict constraints to maintain data integrity.

Parent Validation

When creating or updating a hierarchical entity with a parent_id, the system validates parent existence:

Service	Create Method	Update Method	Validation Logic
MenuService	Line 85-88	Line 107-110	Check parent menu exists via menu_dao.get()
DeptService	Line 71-74	Line 92-95	Check parent dept exists via dept_dao.get()

Both MenuService.create() and MenuService.update() validate parent menu existence at backend/app/admin/service/menu_service.py85-89 and backend/app/admin/service/menu_service.py107-110 Similarly, DeptService.create() and DeptService.update() validate parent department existence at backend/app/admin/service/dept_service.py71-74 and backend/app/admin/service/dept_service.py92-95 If the parent does not exist, an errors.NotFoundError is raised.

Sources: backend/app/admin/service/menu_service.py85-89 backend/app/admin/service/menu_service.py107-110 backend/app/admin/service/dept_service.py71-74 backend/app/admin/service/dept_service.py92-95

Self-Reference Prevention

During update operations, the system prevents entities from referencing themselves as parents. Both MenuService.update() at backend/app/admin/service/menu_service.py111-112 and DeptService.update() at backend/app/admin/service/dept_service.py96-97 check if obj.parent_id == entity.id and raise errors.ForbiddenError if true, preventing invalid self-referential hierarchies.

Sources: backend/app/admin/service/menu_service.py111-112 backend/app/admin/service/dept_service.py96-97

Deletion Protection

Before deleting a node, the system checks for dependent children to prevent orphaned records:

Diagram: Deletion Protection Flows

The MenuService.delete() method at backend/app/admin/service/menu_service.py118-133 calls menu_dao.get_children() to check for child menus. If any exist, it raises errors.ConflictError. Upon successful deletion, it clears affected user caches via user_cache_manager.clear_by_menu_id().

The DeptService.delete() method at backend/app/admin/service/dept_service.py102-121 performs two validation checks before deletion:

1. Calls dept_dao.get_join() to load the department with relationships, then checks dept.users - raises errors.ConflictError if users are assigned
2. Calls dept_dao.get_children() - raises errors.ConflictError if child departments exist

Upon successful deletion, it clears Redis cache entries for all affected users using redis_client.delete() with the JWT_USER_REDIS_PREFIX key pattern.

Sources: backend/app/admin/service/menu_service.py118-133 backend/app/admin/service/dept_service.py102-121

---

Vben5 Sidebar Generation

The get_vben5_tree_data() function at backend/utils/build_tree.py100-132 provides specialized tree formatting for the vben5 admin frontend sidebar component.

Diagram: Vben5 Sidebar Data Flow

Vben5 Meta Structure

The get_vben5_tree_data() function transforms standard menu records into vben5 format by:

1. Extracting meta_keys = {'title', 'icon', 'link', 'cache', 'display', 'status'} from menu records
2. Creating a meta object for each node with vben5-specific properties
3. Using traversal_to_tree() to build the hierarchical structure

Property Mapping Table:

Menu DB Field	Vben5 Meta Property	Transformation Logic
title	meta.title	Direct mapping
icon	meta.icon	Direct mapping
link	meta.iframeSrc	Only if type == 3 (iframe), else empty
link	meta.link	Only if type == 4 (external link), else empty
cache	meta.keepAlive	Direct mapping (boolean)
display	meta.hideInMenu	Inverted: not bool(node['display'])
status	meta.menuVisibleWithForbidden	Inverted: not bool(node['status'])

The function preserves all other node properties (like id, name, path, component, perms, parent_id) outside the meta object, ensuring the full menu structure is available for routing and permission checks.

Example Transformation:

Input (Menu DB Record):
{
  "id": 1,
  "title": "Dashboard",
  "name": "Dashboard",
  "path": "/dashboard",
  "icon": "ant-design:dashboard-outlined",
  "type": 1,
  "link": "",
  "cache": 1,
  "display": 1,
  "status": 1,
  "parent_id": null
}

Output (Vben5 Format):
{
  "id": 1,
  "name": "Dashboard",
  "path": "/dashboard",
  "type": 1,
  "parent_id": null,
  "meta": {
    "title": "Dashboard",
    "icon": "ant-design:dashboard-outlined",
    "iframeSrc": "",
    "link": "",
    "keepAlive": true,
    "hideInMenu": false,
    "menuVisibleWithForbidden": false
  }
}

This separation allows the generic get_tree_data() function to remain framework-agnostic while providing frontend-specific property mappings for vben5 sidebar rendering. The function is called exclusively in MenuService.get_sidebar() at backend/app/admin/service/menu_service.py68

Sources: backend/utils/build_tree.py100-132 backend/app/admin/service/menu_service.py68

---

Tree Data Flow Summary

The following table summarizes all tree-related endpoints and their data flow:

Endpoint	Service Method	DAO Method	Tree Builder	Purpose
GET /sys/menu	menu_service.get_tree()	menu_dao.get_all()	get_tree_data()	Admin menu management
GET /sys/menu/sidebar	menu_service.get_sidebar()	menu_dao.get_sidebar()	get_vben5_tree_data()	User navigation sidebar
GET /sys/role/{pk}/menus	role_service.get_menu_tree()	role_dao.get_menus()	get_tree_data()	Role-menu configuration
GET /sys/dept	dept_service.get_tree()	dept_dao.get_all()	get_tree_data()	Department hierarchy

All tree structures share the same architectural pattern:

1. Database query returns flat list of records with parent_id
2. Service layer calls tree builder utility
3. Tree builder recursively constructs nested structure
4. API layer returns JSON with hierarchical children arrays

Sources: backend/app/admin/api/v1/sys/menu.py1-83 backend/app/admin/api/v1/sys/dept.py1-82 backend/app/admin/api/v1/sys/role.py32-38