Jorgen's blog Jorgen's blog
首页
  • 平台架构
  • 混合式开发记录
  • 推送服务
  • 数据分析
  • 实时调度
  • 架构思想

    • 分布式
  • 编程框架工具

    • 编程语言
    • 框架
    • 开发工具
  • 数据存储与处理

    • 数据库
    • 大数据
  • 消息、缓存与搜索

    • 消息队列
    • 搜索与日志分析
  • 前端与跨端开发

    • 前端技术
    • Android
  • 系统与运维

    • 操作系统
    • 容器化与 DevOps
  • 物联网与安全

    • 通信协议
    • 安全
    • 云平台
收藏
  • 关于我
  • 终身学习
  • 关于时间的感悟
  • 分类
  • 标签
  • 归档
GitHub (opens new window)

jorgen

Love it, make mistakes, learn, keep grinding.
首页
  • 平台架构
  • 混合式开发记录
  • 推送服务
  • 数据分析
  • 实时调度
  • 架构思想

    • 分布式
  • 编程框架工具

    • 编程语言
    • 框架
    • 开发工具
  • 数据存储与处理

    • 数据库
    • 大数据
  • 消息、缓存与搜索

    • 消息队列
    • 搜索与日志分析
  • 前端与跨端开发

    • 前端技术
    • Android
  • 系统与运维

    • 操作系统
    • 容器化与 DevOps
  • 物联网与安全

    • 通信协议
    • 安全
    • 云平台
收藏
  • 关于我
  • 终身学习
  • 关于时间的感悟
  • 分类
  • 标签
  • 归档
GitHub (opens new window)
  • 平台架构
  • 技术选型
  • 开发脚手架
  • UI规范
  • 开发规范
  • 代码分支管理模型
  • 需求分析与管理
  • 权限设计
  • 树形组织设计
    • 邻接表
      • 优点
      • 缺点
    • 路径枚举
      • 优点:
      • 缺点:
    • 闭包表
      • 优点
      • 缺点
      • 闭包表相关操作
  • 协议设计
  • 指令交互
  • OTA
  • 规则引擎
  • 数据流转
  • 报告生成与导出
  • 监控设备接入
  • 时序数据库
  • 平台监控
  • 云⛈
  • 接口设计
  • 安全传输
  • CI&CD
  • 缓存
  • 消息处理引擎
  • 性能调优🔥
  • 线上事故🔥
  • 混合式开发记录
  • 推送服务
  • 机器人通信协议
  • 数据分析
  • flink模板工程
  • 实时调度
  • 机器人模块化设计
  • STM32入门
  • 开发日志
Jorgen
2023-02-05
目录

树形组织设计

问题

根据部门检索人员,选择一个顶级部门情况下,跨级展示当前部门以及子部门下的所有人员,表怎么设计更合理?

# 邻接表

这样是最常见的设计,能正确的表达菜单的树状结构且没有冗余数据,但在跨层级查询需要递归处理。

  CREATE TABLE `dept_info01` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
  `dept_id` int(10) NOT NULL COMMENT '部门id',
  `dept_name` varchar(100) NOT NULL COMMENT '部门名称',
  `dept_parent_id` int(11) NOT NULL COMMENT '父部门id',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
  PRIMARY KEY (`id`) USING BTREE
  ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
1
2
3
4
5
6
7
8
9

临近表

比如:查询某一个节点的直接子集

  SELECT * FROM dept_info01 WHERE dept_parent_id =1001
1

# 优点

结构简单

# 缺点

不使用递归情况下无法查询某节点所有父级,所有子集

# 路径枚举

在设计1基础上新增一个父部门id集字段,用来存储所有父集,多个以固定分隔符分隔,比如逗号。

CREATE TABLE `dept_info02` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
`dept_id` int(10) NOT NULL COMMENT '部门id',
`dept_name` varchar(100) NOT NULL COMMENT '部门名称',
`dept_parent_id` int(11) NOT NULL COMMENT '父部门id',
`dept_parent_ids` varchar(255) NOT NULL DEFAULT '' COMMENT '父部门id集',
`create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
`update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
1
2
3
4
5
6
7
8
9
10

路径枚举

比如:查询所有子集

  1. 通过模糊查询
     SELECT
       *
     FROM
     dept_info02
     WHERE
     dept_parent_ids like '%1001%'
    
    1
    2
    3
    4
    5
    6
  2. 使用 FIND_IN_SET 函数
  SELECT
  * 
  FROM
  dept_info02 
  WHERE
  FIND_IN_SET( '1001', dept_parent_ids )
1
2
3
4
5
6

# 优点:

  1. 方便查询所有的子集;
  2. 可以因此通过比较字符串dept_parent_ids长度获取当前节点层级 ;

# 缺点:

  1. 新增节点时需要将dept_parent_ids字段值处理好;
  2. dept_parent_ids字段的长度很难确定,无论长度设为多大,都存在不能够无限扩展的情况;
  3. 节点移动复杂,需要同时变更所有子集中的dept_parent_ids字段值 ;

# 闭包表

闭包表是解决分级存储的一个简单而优雅的解决方案,这是一种通过空间换取时间的方式;

  1. 需要额外创建了一张TreePaths表它记录了树中所有节点间的关系;
  2. 包含两列,祖先列与后代列,即使这两个节点之间不是直接的父子关系;
  3. 同时增加一行指向节点自己;

主表

  CREATE TABLE `dept_info03` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
  `dept_id` int(10) NOT NULL COMMENT '部门id',
  `dept_name` varchar(100) NOT NULL COMMENT '部门名称',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
  PRIMARY KEY (`id`) USING BTREE
  ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
1
2
3
4
5
6
7
8

主表

祖先后代关系表

  CREATE TABLE `dept_tree_path_info` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键',
  `ancestor` int(10) NOT NULL COMMENT '祖先id',
  `descendant` int(10) NOT NULL COMMENT '后代id',
  `depth` tinyint(4) NOT NULL DEFAULT '0' COMMENT '层级深度',
  PRIMARY KEY (`id`) USING BTREE
  ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
1
2
3
4
5
6
7

主表

# 优点

  1. 非递归查询减少冗余的计算时间;
  2. 方便非递归查询任意节点所有的父集;
  3. 方便查询任意节点所有的子集;
  4. 可以实现无限层级;
  5. 支持移动节点;

# 缺点

  1. 层级太多情况下移动树节点会带来关系表多条操作 ;
  2. 需要单独一张表存储对应关系,在新增与编辑节点时操作相对复杂 ;
  3. 结合使用可以将邻接表方式与闭包表方式相结合使用。实际上就是将父id冗余到主表中,在一些只需要查询直接关系的业务中就可以直接查询主表,而不需要关联2张表了。在需要跨级查询时祖先后代关系表就显得尤为重要。

其实,在以往的工作中,曾见过不同类型的设计,邻接表,路径枚举,邻接表路径枚举一起来的都见过。每种设计都各有优劣,如果选择设计依赖于应用程序中哪种操作最需要性能上的优化。

设计 表数量 直接查询子 查询子树 同时查询多个节点子树 插入 删除 移动
邻接表 1 简单 需要递归 需要递归 简单 简单 简单
枚举路径 1 简单 简单 查多次 相对复杂 简单 复杂
闭包表 2 简单 简单 简单 相对复杂 简单 复杂

结论

只需要建立子父集关系中可以使用邻接表方式; 涉及向上查找,向下查找的需要建议使用闭包表方式;

# 闭包表相关操作

  1. 插入新节点
  INSERT INTO dept_tree_path_info (ancestor, descendant,depth)
  SELECT t.ancestor, 3001,t.depth+1 FROM dept_tree_path_info AS t 
  WHERE t.descendant = 2001
  UNION ALL
  SELECT 3001,3001,1
1
2
3
4
5
  1. 查询所有祖先
  SELECT
  c.*
  FROM
  dept_info03 AS c
  INNER JOIN dept_tree_path_info t ON c.dept_id = t.ancestor
  WHERE
  t.descendant = 3001
1
2
3
4
5
6
7
  1. 查询所有后代
  SELECT
  c.*
  FROM
  dept_info03 AS c
  INNER JOIN dept_tree_path_info t ON c.dept_id = t.descendant
  WHERE
  t.ancestor = 1001
1
2
3
4
5
6
7
  1. 删除所有子树
  DELETE 
  FROM
  dept_tree_path_info 
  WHERE
  descendant IN 
  ( 
  SELECT
  a.dept_id 
  FROM
  ( SELECT descendant dept_id FROM dept_tree_path_info WHERE ancestor = 1001 ) a
  )
1
2
3
4
5
6
7
8
9
10
11
  1. 删除叶子节点
  DELETE 
  FROM
  dept_tree_path_info 
  WHERE
  descendant = 2001
1
2
3
4
5
#临近表#路径枚举#闭包表
上次更新: 2023/02/19, 11:42:06
权限设计
协议设计

← 权限设计 协议设计→

最近更新
01
STM32入门
03-09
02
ADB调试
03-09
03
微信小程序学习记录
02-09
更多文章>
Theme by Vdoing | Copyright © 2019-2025 Jorgen | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式