树形结构递归查询与嵌套结构转换：Flask + PostgreSQL 完整实现

递归查询与树形结构转换：Flask + PostgreSQL 完整实现

本文在flask背景下，基于原始的SQL实现菜单树的查询，包括递归查询、树形结构转换以及API端点实现。

完整实现代码

from flask import Flask, jsonify, request
from flask_sqlalchemy import SQLAlchemy
from sqlalchemy import text
import json

app = Flask(__name__)
app.config['SQLALCHEMY_DATABASE_URI'] = 'postgresql://user:password@localhost/mydb'
app.config['SQLALCHEMY_TRACK_MODIFICATIONS'] = False
db = SQLAlchemy(app)

class Menu(db.Model):
    __tablename__ = 'sys_menu'
    menu_id = db.Column(db.Integer, primary_key=True)
    parent_id = db.Column(db.Integer, nullable=False, default=-1)
    menu_name = db.Column(db.String(100), nullable=False)
    # 其他字段...
    visible = db.Column(db.Integer, nullable=False, default=1)
    status = db.Column(db.Integer, nullable=False, default=0)

def build_tree(nodes, parent_id=-1, level=0, path=""):
    """
    将扁平列表转换为嵌套树形结构
    :param nodes: 从数据库查询的扁平节点列表
    :param parent_id: 当前处理的父节点ID
    :param level: 当前层级（用于递归）
    :param path: 当前路径（用于递归）
    :return: 嵌套的树形结构
    """
    tree = []
    # 筛选当前父节点的直接子节点
    children = [n for n in nodes if n['parent_id'] == parent_id]
    
    for child in children:
        # 为当前节点构建完整路径
        node_path = f"{path},{child['menu_id']}" if path else str(child['menu_id'])
        
        # 构建当前节点
        node = {
            'menu_id': child['menu_id'],
            'menu_name': child['menu_name'],
            'parent_id': child['parent_id'],
            'level': level,
            'path': node_path,
            'children': []
        }
        
        # 递归构建子树
        grandchildren = build_tree(
            nodes, 
            parent_id=child['menu_id'], 
            level=level + 1,
            path=node_path
        )
        
        # 添加子节点
        node['children'] = grandchildren
        
        # 添加当前节点到树
        tree.append(node)
    
    return tree

def get_menu_tree(menu_id=None):
    """
    执行递归查询并返回树形结构
    :param menu_id: 可选，指定根节点菜单ID
    :return: 嵌套的树形结构
    """
    # 构建递归查询SQL
    sql = """
    WITH RECURSIVE menu_tree AS (
        SELECT 
            menu_id, 
            parent_id, 
            menu_name,
            1 AS level,
            CAST(menu_id AS TEXT) AS path
        FROM sys_menu
        WHERE 
    """
    
    # 根据是否指定menu_id添加不同条件
    if menu_id:
        sql += "menu_id = :menu_id"
    else:
        sql += "parent_id = -1"
    
    sql += """
        UNION ALL
        SELECT 
            m.menu_id, 
            m.parent_id, 
            m.menu_name,
            mt.level + 1,
            mt.path || ',' || m.menu_id
        FROM sys_menu m
        INNER JOIN menu_tree mt ON m.parent_id = mt.menu_id
    )
    SELECT * FROM menu_tree
    ORDER BY path;
    """
    
    # 执行查询
    params = {'menu_id': menu_id} if menu_id else {}
    result = db.session.execute(text(sql), params)
    
    # 将结果转换为字典列表
    nodes = [dict(row) for row in result.mappings()]
    
    # 如果没有结果，返回空列表
    if not nodes:
        return []
    
    # 转换树形结构
    if menu_id:
        # 指定menu_id时，以该节点为根
        root_node = next((n for n in nodes if n['menu_id'] == menu_id), None)
        if not root_node:
            return []
        
        # 构建以指定节点为根的树
        tree = [{
            'menu_id': root_node['menu_id'],
            'menu_name': root_node['menu_name'],
            'parent_id': root_node['parent_id'],
            'level': root_node['level'],
            'path': root_node['path'],
            'children': build_tree(
                nodes, 
                parent_id=root_node['menu_id'],
                level=root_node['level'] + 1,
                path=root_node['path']
            )
        }]
    else:
        # 未指定menu_id时，从根节点开始构建完整树
        tree = build_tree(nodes, parent_id=-1)
    
    return tree

@app.route('/api/menus', methods=['GET'])
def get_menus():
    """API端点：获取菜单树形结构"""
    # 获取查询参数
    menu_id = request.args.get('menu_id', type=int)
    
    try:
        # 获取菜单树
        menu_tree = get_menu_tree(menu_id)
        return jsonify({
            'code': 200,
            'message': 'Success',
            'data': menu_tree
        })
    except Exception as e:
        return jsonify({
            'code': 500,
            'message': f'Error: {str(e)}',
            'data': None
        }), 500

if __name__ == '__main__':
    app.run(debug=True)

功能解析

1. 递归查询设计

查询逻辑：

WITH RECURSIVE menu_tree AS (
    -- 基础查询：选择根节点
    SELECT 
        menu_id, 
        parent_id, 
        menu_name,
        1 AS level,
        CAST(menu_id AS TEXT) AS path
    FROM sys_menu
    WHERE 
        /* 条件：如果传入menu_id则选择该节点，否则选择根节点 */
    
    UNION ALL
    
    -- 递归查询：选择子节点
    SELECT 
        m.menu_id, 
        m.parent_id, 
        m.menu_name,
        mt.level + 1,  -- 层级递增
        mt.path || ',' || m.menu_id  -- 路径扩展
    FROM sys_menu m
    INNER JOIN menu_tree mt ON m.parent_id = mt.menu_id
)
SELECT * FROM menu_tree
ORDER BY path;  -- 按路径排序确保父子顺序

路径与层级计算：

• level：从根节点开始的层级，根节点为1
• path：从根节点到当前节点的路径，如 “1,3,5”

2. 树形结构转换算法

build_tree 函数工作原理：

1. 筛选直接子节点：从节点列表中找出指定父节点的所有直接子节点
2. 构建节点对象：为每个子节点创建包含元数据和子节点列表的对象
3. 递归构建子树：对每个子节点递归调用自身构建子树
4. 路径和层级处理：在递归过程中维护正确的路径和层级

时间复杂度：

• 平均情况：O(n)
• 最坏情况：O(n²)（当树退化为链表时）

3. API端点处理流程

1. 接收可选的 menu_id 参数
2. 执行递归查询获取扁平节点列表
3. 转换为嵌套树形结构
   • 指定 menu_id：以该节点为根
   • 未指定：从根节点开始
4. 返回JSON格式的树形数据

使用示例

1. 获取完整菜单树

GET /api/menus

响应示例：

{
  "code": 200,
  "message": "Success",
  "data": [
    {
      "menu_id": 1,
      "menu_name": "系统管理",
      "parent_id": -1,
      "level": 1,
      "path": "1",
      "children": [
        {
          "menu_id": 2,
          "menu_name": "用户管理",
          "parent_id": 1,
          "level": 2,
          "path": "1,2",
          "children": []
        },
        {
          "menu_id": 3,
          "menu_name": "角色管理",
          "parent_id": 1,
          "level": 2,
          "path": "1,3",
          "children": [
            {
              "menu_id": 4,
              "menu_name": "权限分配",
              "parent_id": 3,
              "level": 3,
              "path": "1,3,4",
              "children": []
            }
          ]
        }
      ]
    }
  ]
}

2. 获取指定菜单的子树

GET /api/menus?menu_id=3

响应示例：

{
  "code": 200,
  "message": "Success",
  "data": [
    {
      "menu_id": 3,
      "menu_name": "角色管理",
      "parent_id": 1,
      "level": 1,
      "path": "3",
      "children": [
        {
          "menu_id": 4,
          "menu_name": "权限分配",
          "parent_id": 3,
          "level": 2,
          "path": "3,4",
          "children": []
        }
      ]
    }
  ]
}

性能优化策略

1. 数据库层面优化

-- 添加索引
CREATE INDEX idx_menu_parent ON sys_menu(parent_id);
CREATE INDEX idx_menu_path ON sys_menu USING GIN (path gin_trgm_ops);

2. 查询优化

# 添加缓存（使用Flask-Caching）
from flask_caching import Cache

cache = Cache(app, config={'CACHE_TYPE': 'SimpleCache'})

@app.route('/api/menus', methods=['GET'])
@cache.cached(timeout=300, query_string=True)  # 缓存5分钟
def get_menus():
    # ...

3. 分页处理大型树

# 修改递归查询添加分页
sql += """
    LIMIT :limit OFFSET :offset
"""

# 在get_menu_tree中添加参数
def get_menu_tree(menu_id=None, limit=100, offset=0):
    # ...
    params = {
        'menu_id': menu_id,
        'limit': limit,
        'offset': offset
    } if menu_id else {
        'limit': limit,
        'offset': offset
    }
    # ...

关键设计决策

1. 不使用ORM关系：

   • 直接使用SQL查询提高灵活性
   • 避免ORM在复杂查询中的性能开销
   • 更精确控制递归查询逻辑

2. 路径存储设计：

   • 使用逗号分隔的字符串存储路径
   • 便于排序和层级判断
   • 比递归查询更高效

3. 树形结构转换：

   • 在应用层而非数据库层转换
   • 更灵活处理复杂树结构
   • 避免数据库过度计算

4. API设计：

   • 支持指定根节点
   • 统一返回嵌套JSON
   • 包含层级和路径信息

适用场景

1. 菜单管理系统：展示层级化菜单结构
2. 组织架构：展示部门树形关系
3. 分类系统：商品分类、文章分类等
4. 权限系统：展示权限继承关系
5. 导航系统：多级导航菜单

扩展建议

1. 添加节点过滤：

   def get_menu_tree(menu_id=None, status=0, visible=1):
       # 在基础查询中添加条件
       sql += " AND status = :status AND visible = :visible"
       # ...
   

2. 添加额外字段：

   SELECT 
       menu_id, 
       parent_id, 
       menu_name,
       icon,  -- 添加图标字段
       status,
       visible,
       ...
   

3. 路径解析工具：

   def get_path_info(path):
       """解析路径信息"""
       ids = path.split(',')
       return {
           'level': len(ids),
           'ids': [int(id) for id in ids],
           'parent_ids': [int(id) for id in ids[:-1]]
       }
   

这个实现提供了从数据库递归查询到树形结构转换的完整解决方案，既保持了高效性，又提供了灵活的API接口，能够满足各种树形数据展示需求。