数据结构PTT优化部门树查询

news/2025/2/22 10:51:54

数据结构PTT优化部门树查询

进入正文之前先给出一个概念,可以在看完文章后再来看这个数据结构概念

预排序遍历树（Modified Preorder Tree Traversal，简称MPTT）是一种通过冗余字段优化树形结构查询效率的算法，常用于解决多层级分类（如部门树、商品分类）的递归查询性能瓶颈问题。其核心是通过深度优先遍历预计算为每个节点添加左右边界值（lft和rgt），实现以空间换时间的高效查询。

1.业务场景

实际开发中遇到两个接口:

  1. 部门树查询接口,部门结构中需要查出租户下的所有部门树结构
  2. RBAC权限控制中有"本级及其自己"的权限范围,需要一次查出该部门及其子部门

数据表的设计上，通过一个 parent_id 字段关联是父部门id,通过该字段查询到这个部门的子部门的列表。然后通过递归不断地遍历查询出所有的部门并且组装成树。

java">public List<DepartMent> queryByParentId(int parentId){
        //这里执行数据库查询
        //select * from department where tenant_id=xxx and parent_id=xxx;
        ...
    };
    public List<DepartMent> getChildren(int parentId){
        //查出子部门
        List<DepartMent> children = queryByParentId(parentId);
        for (DepartMent departMent : children) {
            List<DepartMent> child = getChildren2(departMent.getId());
            departMent.setChildren(child);
        }
        return children;
    }

问题就出现在递归逻辑,此处是每封装一个部门,就需要执行一次sql查询,当

  • 部门层级过深
  • 部门数量过多

都会导致sql查询的执行次数过多

这里先考虑两种常见的树查询优化方案:

  1. 懒查询:一次只查询一级部门节点,慢慢展开,但在数据权限查询接口不支持,因为需要一次查出所有子部门

  2. 直接用租户 id 查询出所有的部门数据然后再组装成树

    确实可以解决部门树的查询，但是数据权限的子部门那里查询从出所有数据组装也会超时(解释这中方案有什么不适合权限接口的地方,我的想法是这种全查的方式在查出后还需要对数据进行递归处理)

    java">public List<DepartMent> getChildrenOptimized(int parentId) {
    List<DepartMent> allDepartments = queryAllDepartments(); // 一次性查询所有部门
    return buildTree(parentId, allDepartments);
}

private List<DepartMent> buildTree(int parentId, List<DepartMent> allDepartments) {
    List<DepartMent> children = new ArrayList<>();
    for (DepartMent dept : allDepartments) {
        if (dept.getParentId() == parentId) {
            dept.setChildren(buildTree(dept.getId(), allDepartments));
            children.add(dept);
        }
    }
    return children;
}

解决问题的核心还是传入任何一个部门的id就能迅速查出子部门.

解决方案

  1. 加缓存,每一个部门id都缓存子部门的数据,但初次构建缓存的查询依旧慢…(这里请分析缓存方案的缺点)
  2. 减少数据库查询的次数

引入数据结构方案

实现及业务改造

以如下部门结构为例

设计数据结构规则:

为每个节点添加两个值leftValue, rightValue，代表数据的范围,需要满足以下要求：

  1. 每个节点的 leftValue < rightValue
  2. 子节点的 leftValue > 父节点的 leftValue
  3. 子节点的 rightValue < 父节点的 rightValue

则部门结构树初始化如下:

此时可以发现一个部门的所有子部门的 leftValue 和 rightValue 是在父部门的范围内的。

如果想查出指定部门的子部门,执行以下sql即可

select * from dept where tenant_id=xxx and left_value > #{leftValue} and left_value < #{rightValue}

业务伪代码如下

java">//1. 查询该部门的 leftValue 和 rightValue
Dept dept = queryDeptFromMysql(parentId);
int leftValue = dept.getLeftValue();
int rightValue = dept.getRightValue();

//2. 通过leftValue 和 rightValue 查询子部门
List<Dept> childDepts = queryChildDeptsFromMysql(leftValue, rightValue);

//3.对childDepts组装查询结果

此时就可以实现一次查出指定部门的所有子部门

可以看出其实是"一次查出所有"的变式,加字段后可以实现"指定部门一次查出所有",而且"权限查询接口"这里查出来后不需要做递归封装逻辑

数据结构的增删改查

1.初始化

初始化其实就是对部门树进行深度优先遍历,初始value为1,每次value+1

2.增加子部门

这里业务场景只考虑单部门,多部门可以参考3

a. 新增了一个部门 4-2 他的值分别是 4-1 的（rightValue +1, rightValue+2）即 6,7
b. 因为 3-1 增加了子部门所以他的值范围必定发生变化，变化的增长值就是 2（也是增加的节点个数*2）因为部门 4-2 已经是 6,7 了所以 3-1 部门会发生变化为 3,8
c. 同理后续右边（比发生变化的值大的）节点的值都会发生对应的变化

其实不难看出，每个值大于等于 4-1 的 rightValue +1，（即新增加的 4-2 的 leftValue）的值都增加了 2，无论他是 leftValue 还是 rightValue。

那么新增加一个子节点的逻辑如下

  1. 新加部门初始化值后插入

  2. 更新右侧所有部门的值

    UPDATE dept
SET left_value = IF(left_value > #{leftValue}, left_value + #{changeValue}, left_value),
    right_value = IF(right_value > #{leftValue}, right_value + #{changeValue}, right_value)
where tenant_id= #{tenantId};
3.刪除

  1. 先将目标部门移除

  2. 目标部门右侧的所有值-changeValue(2*删除节点数量)

    UPDATE dept
SET left_value = IF(left_value > #{leftValue}, left_value - #{changeValue}, left_value),
    right_value = IF(right_value > #{leftValue}, right_value - #{changeValue}, right_value)
where tenant_ids = #{tenantId};

在这里插入图片描述

删除部门包含子部门同理(changValue变化)

4.移动部门:

比如将部门3-1转移到部门3-2下

-->

移动部门可以结合删除和新增分为两步走:

  1. 先将目标部门移除
  2. 将目标部门及其子部门进行初始化
  3. 执行插入

相比于单部门插入,前置多了一步初始化,即从父部门的rightValue+1开始深度遍历移动部门,之后走"新增子部门"逻辑插入部门,右侧的值增加changeValue(插入节点数*2)

优化效果

部门树接口(约1.8W个部门)返回速度从20s优化到400ms

本人的思考点

在学习这个技术方案的过程中,较为困惑的一点就是数据结构优化的方案相比一次查出所有然后进行封装的方案有什么改进的地方

对比维度全量查询+内存组装方案预排序遍历树（PTT）方案
查询性能1次全表查询 + O(n)内存递归构建1次范围查询 + O(1)内存组装
适用场景数据量<1万且层级<5层的数据量较小场景,写多读少数据量>1万或需要高频权限校验的场景
内存消耗需全量加载数据集（1.8W部门≈10MB+内存）按需加载结果集（子部门查询≈KB级内存）
写入性能无额外维护成本插入/删除需更新右侧所有节点值（O(n)级操作）
维护复杂度天然适配现有业务逻辑需独立维护左右值，存在并发写风险
扩展性无法直接支持范围权限控制原生支持"包含子部门"类范围查询
数据一致性天然保证需事务保证左右值更新与业务操作的一致性
树结构调整仅需更新parent_id字段需全量重构左右值（移动子树时间复杂度O(n^2)）
  1. 零递归处理：通过left_value BETWEEN parent_left AND parent_right即可直接获得完整子树
  2. 数据库级过滤：权限校验可直接在SQL层面完成，避免全量数据传输

非常感谢你看到这里,针对这种方案如果还有什么疑惑或思考点,欢迎交流

                  | 需全量重构左右值（移动子树时间复杂度O(n^2)） |
  1. 零递归处理：通过left_value BETWEEN parent_left AND parent_right即可直接获得完整子树
  2. 数据库级过滤：权限校验可直接在SQL层面完成，避免全量数据传输

非常感谢你看到这里,针对这种方案如果还有什么疑惑或思考点,欢迎交流

文末声明:此技术方案出自师兄夜斗,一位优秀的前辈


http://www.niftyadmin.cn/n/5862134.html

相关文章

Elasticsearch 中如何限制和指定 IP 地址的访问？

Elasticsearch 中如何限制和指定 IP 地址的访问？

在现代的微服务架构中&#xff0c;保护系统不受未授权访问是非常重要的&#xff0c;尤其是在网关层。极限网关&#xff08;INFINI Gateway&#xff09;作为我们服务架构的入口&#xff0c;它的安全性直接影响到整个系统的稳定与安全。 极限网关提供了强大的 IP 访问控制 功能&a…
阅读更多...
web安全:跨站请求伪造 (CSRF)

web安全:跨站请求伪造 (CSRF)

跨站请求伪造 (CSRF) ​ 跨站请求伪造&#xff08;CSRF&#xff0c;Cross-Site Request Forgery&#xff09; 是一种网络攻击方式&#xff0c;攻击者诱使受害者在未经其授权的情况下执行特定操作。CSRF 利用受害者已登录的身份和浏览器自动发送的认证信息&#xff08;如 Cooki…
阅读更多...
如何查找 UBuntu的 arm版本

如何查找 UBuntu的 arm版本

Ubuntu官网 https://ubuntu.com/ 如图&#xff1a; 点击 Tab栏的Download Ubuntu >> Server >> ARM >> 点击Download 24.04.2 LTS 即可 如果需要其他版本 点击 Alternative and previous releases 进入到如下页面选择想要的版本下载即可
阅读更多...
支持向量机 (Support Vector Machine, SVM)

支持向量机 (Support Vector Machine, SVM)

支持向量机 (Support Vector Machine, SVM) 支持向量机&#xff08;SVM&#xff09;是一种广泛应用于分类、回归分析以及异常检测的监督学习算法。它基于结构风险最小化&#xff08;Structural Risk Minimization&#xff0c;SRM&#xff09;原则&#xff0c;通过寻找一个最优…
阅读更多...
【论文阅读笔记】知识蒸馏：一项调查 | CVPR 2021 | 近万字翻译+解释

【论文阅读笔记】知识蒸馏：一项调查 | CVPR 2021 | 近万字翻译+解释

目录 1 引言 2 知识 2.1 Response-Based Knowledge 2.2 Feature-Based Knowledge 2.3 Relation-Based Knowledge 3 蒸馏方案 3.1 Offline Distillation 3.2 Online Distillation 3.3 Self-Distillation 4 师生架构 5 蒸馏算法 5.1 Adversarial Distillation 5.2 M…
阅读更多...
ArcGIS Pro进行坡度与坡向分析

ArcGIS Pro进行坡度与坡向分析

在地理信息系统中&#xff0c;坡度分析是一项至关重要的空间分析方法&#xff0c;旨在精确计算地表或地形的坡度&#xff0c;为地形特征识别、土地资源规划、环境保护、灾害预警等领域提供科学依据。本文将详细介绍如何利用ArcGIS Pro这一强大的地理信息系统软件&#xff0c;进…
阅读更多...
【接口测试】使用Requests库发送POST请求

【接口测试】使用Requests库发送POST请求

POST请求用于向服务器提交数据&#xff0c;比如提交一个表单新建一个用户、或修改一个用户信息等操作。 对于POST请求&#xff0c;我们可以通过浏览器开发者工具或者其他外部工具来进行抓包&#xff0c;得到请求的URL、请求头&#xff08;request headers&#xff09;以及请求…
阅读更多...
XML Schema 元素替换

XML Schema 元素替换

XML Schema 元素替换 引言 XML（可扩展标记语言）是一种用于存储和传输数据的标记语言。XML Schema 是一种用于定义 XML 文档结构的语言，它描述了 XML 文档的结构、数据类型和约束。在处理 XML 文档时，有时需要对特定的元素进行替换，以满足特定的需求。本文将介绍 XML Sch…
阅读更多...
最新文章

Copyright @ 2022~2023