树形结构递归查询与嵌套结构转换：Flask + PostgreSQL 完整实现
递归查询与树形结构转换：Flask + PostgreSQL 完整实现
本文在flask背景下，基于原始的SQL实现菜单树的查询，包括递归查询、树形结构转换以及API端点实现。
完整实现代码
from flask import Flask, jsonify, request
from flask_sqlalchemy import SQLAlchemy
from sqlalchemy import text
import jsonapp = 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 treedef get_menu_tree(menu_id=None):"""执行递归查询并返回树形结构:param menu_id: 可选，指定根节点菜单ID:return: 嵌套的树形结构"""# 构建递归查询SQLsql = """WITH RECURSIVE menu_tree AS (SELECT menu_id, parent_id, menu_name,1 AS level,CAST(menu_id AS TEXT) AS pathFROM sys_menuWHERE """# 根据是否指定menu_id添加不同条件if menu_id:sql += "menu_id = :menu_id"else:sql += "parent_id = -1"sql += """UNION ALLSELECT m.menu_id, m.parent_id, m.menu_name,mt.level + 1,mt.path || ',' || m.menu_idFROM sys_menu mINNER JOIN menu_tree mt ON m.parent_id = mt.menu_id)SELECT * FROM menu_treeORDER 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}), 500if __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 pathFROM sys_menuWHERE /* 条件：如果传入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 mINNER JOIN menu_tree mt ON m.parent_id = mt.menu_id
)
SELECT * FROM menu_tree
ORDER BY path; -- 按路径排序确保父子顺序
路径与层级计算：
level：从根节点开始的层级，根节点为1path：从根节点到当前节点的路径，如 “1,3,5”
2. 树形结构转换算法
build_tree 函数工作原理：
- 筛选直接子节点：从节点列表中找出指定父节点的所有直接子节点
- 构建节点对象：为每个子节点创建包含元数据和子节点列表的对象
- 递归构建子树：对每个子节点递归调用自身构建子树
- 路径和层级处理：在递归过程中维护正确的路径和层级
时间复杂度：
- 平均情况：O(n)
- 最坏情况：O(n²)（当树退化为链表时）
3. API端点处理流程
- 接收可选的
menu_id参数 - 执行递归查询获取扁平节点列表
- 转换为嵌套树形结构
- 指定
menu_id：以该节点为根 - 未指定：从根节点开始
- 指定
- 返回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 Cachecache = 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}# ...
关键设计决策
-
不使用ORM关系：
- 直接使用SQL查询提高灵活性
- 避免ORM在复杂查询中的性能开销
- 更精确控制递归查询逻辑
-
路径存储设计：
- 使用逗号分隔的字符串存储路径
- 便于排序和层级判断
- 比递归查询更高效
-
树形结构转换：
- 在应用层而非数据库层转换
- 更灵活处理复杂树结构
- 避免数据库过度计算
-
API设计：
- 支持指定根节点
- 统一返回嵌套JSON
- 包含层级和路径信息
适用场景
- 菜单管理系统：展示层级化菜单结构
- 组织架构：展示部门树形关系
- 分类系统：商品分类、文章分类等
- 权限系统：展示权限继承关系
- 导航系统：多级导航菜单
扩展建议
-
添加节点过滤：
def get_menu_tree(menu_id=None, status=0, visible=1):# 在基础查询中添加条件sql += " AND status = :status AND visible = :visible"# ... -
添加额外字段：
SELECT menu_id, parent_id, menu_name,icon, -- 添加图标字段status,visible,... -
路径解析工具：
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接口，能够满足各种树形数据展示需求。