浅谈MYSQL中树形结构表3种设计优劣分析与分享

吾爱主题阅读：104 2024-04-02 08:06:04 评论：0

简介

在开发中经常遇到树形结构的场景，本文将以部门表为例对比几种设计的优缺点；

问题

需求背景：根据部门检索人员，
问题：选择一个顶级部门情况下，跨级展示当前部门以及子部门下的所有人员，表怎么设计更合理？

递归吗？递归可以解决，但是势必消耗性能

设计1：邻接表

注:（常见父id设计）

表设计

1 2 3 4 5 6 7 8 9 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;

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

sql示例

1.查询某一个节点的直接子集

1	`select` `*` `from` `dept_info01` `where` `dept_parent_id =1001`

优点

结构简单 ;

缺点

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

设计2：路径枚举

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

表设计

1 2 3 4 5 6 7 8 9 10 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;

sql示例

1.查询所有子集
1).通过模糊查询

1 2 3 4 5 6 select * from dept_info02 where dept_parent_ids like '%1001%'

2).推荐使用 find_in_set 函数

1 2 3 4 5 6 select * from dept_info02 where find_in_set( '1001' , dept_parent_ids )

优点

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

缺点

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

设计3：闭包表

闭包表是解决分级存储的一个简单而优雅的解决方案，这是一种通过空间换取时间的方式 ;
需要额外创建了一张treepaths表它记录了树中所有节点间的关系 ;
包含两列，祖先列与后代列，即使这两个节点之间不是直接的父子关系；同时增加一行指向节点自己 ;

表设计

主表

1 2 3 4 5 6 7 8 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 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;

注：depth 层级深度字段，自我引用为 1，直接子节点为 2，再一下层为 3，一次类推，第几层就是几。

sql示例

插入新节点

1 2 3 4 5 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 6 7 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 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 8 9 10 11 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 delete from dept_tree_path_info where descendant = 2001

移动节点

删除所有子树(先断开与原祖先的关系)
建立新的关系

优点

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

缺点

层级太多情况下移动树节点会带来关系表多条操作 ;
需要单独一张表存储对应关系，在新增与编辑节点时操作相对复杂 ;

结合使用

可以将邻接表方式与闭包表方式相结合使用。实际上就是将父id冗余到主表中，在一些只需要查询直接关系的业务中就可以直接查询主表，而不需要关联2张表了。在需要跨级查询时祖先后代关系表就显得尤为重要。

表设计

主表

1 2 3 4 5 6 7 8 9 create table `dept_info04` ( `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	简单	需要递归	需要递归	简单	简单	简单
枚举路径	1	简单	简单	查多次	相对复杂	简单	复杂
闭包表	2	简单	简单	简单	相对复杂	简单	复杂