问题

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

邻接表

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

  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;

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

  SELECT * FROM dept_info01 WHERE dept_parent_id =1001

优点

结构简单

缺点

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

路径枚举

在设计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. 通过模糊查询

    SELECT
      *
    FROM
    dept_info02
    WHERE
    dept_parent_ids like '%1001%'
   

2. 使用 FIND_IN_SET 函数

  SELECT
  * 
  FROM
  dept_info02 
  WHERE
  FIND_IN_SET( '1001', dept_parent_ids )

优点:

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;

祖先后代关系表

  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. 支持移动节点;

缺点

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

2. 查询所有祖先

  SELECT
  c.*
  FROM
  dept_info03 AS c
  INNER JOIN dept_tree_path_info t ON c.dept_id = t.ancestor
  WHERE
  t.descendant = 3001

3. 查询所有后代

  SELECT
  c.*
  FROM
  dept_info03 AS c
  INNER JOIN dept_tree_path_info t ON c.dept_id = t.descendant
  WHERE
  t.ancestor = 1001

4. 删除所有子树

  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
  )

5. 删除叶子节点

  DELETE 
  FROM
  dept_tree_path_info 
  WHERE
  descendant = 2001