如何将树形结构存储在数据库中


今天来看看一个比较头疼的问题,如何在数据库中存储树形结构呢?

像mysql这样的关系型数据库,比较适合存储一些类似表格的扁平化数据,但是遇到像树形结构这样有深度的人,就很难驾驭了。

举个栗子:现在有一个要存储一下公司的人员结构,大致层次结构如下:

那么怎么存储这个结构?并且要获取以下信息:

  • 查询小天的直接上司。
  • 查询老宋管理下的直属员工。
  • 查询小天的所有上司。
  • 查询老王管理的所有员工。

Adjacency List 只存储当前节点的父节点信息

CREATE TABLE Employees(
    eid int,
    ename VARCHAR(100),
    position VARCHAR(100),
    parent_id int
)

记录信息简单粗暴,那么现在存储一下这个结构信息:

好的,现在开始进入回答环节:

  • 查询小天的直接上司:

    SELECT e2.eid,e2.ename FROM employees e1,employees e2 WHERE e1.parent_id=e2.eid AND e1.ename='小天'

  • 查询老宋管理下的直属员工

    SELECT e1.eid,e1.ename FROM employees e1,employees e2 WHERE e1.parent_id=e2.eid AND e2.ename='老宋'

  • 查询小天的所有上司

这里肯定没法直接查,只能用循环进行循环查询,先查直接上司,再查直接上司的直接上司,依次循环,这样麻烦的事情,还是得先建立一个存储过程:

睁大眼睛看仔细了,接下来是骚操作环节

CREATE DEFINER=`root`@`localhost` FUNCTION `getSuperiors`(`uid` int) RETURNS varchar(1000) CHARSET gb2312
BEGIN
    DECLARE superiors VARCHAR(1000) DEFAULT '';
    DECLARE sTemp INTEGER DEFAULT uid;
    DECLARE tmpName VARCHAR(20);

    WHILE (sTemp>0) DO
        SELECT parent_id into sTemp FROM employees where eid = sTemp;
        SELECT ename into tmpName FROM employees where eid = sTemp;
        IF(sTemp>0)THEN
            SET superiors = concat(tmpName,',',superiors);
        END IF;
    END WHILE;
        SET superiors = LEFT(superiors,CHARACTER_LENGTH(superiors)-1);
    RETURN superiors;
END

SQL SERVER CET 表达式

;with TeamMember as(
    select *, ES_EId as DM, 0 as rank from [dbo].[T_EmployeeSystem]
    where ES_EId in (690)
    union all
    select te.*, tm.DM, tm.rank + 1 from [dbo].[T_EmployeeSystem] te
    join TeamMember tm on te.ES_EId = tm.ES_PEId
)

select te.E_StaffID as StaffID, te.E_AD as ADName, te.E_EN_Name as UserName from TeamMember tm
left join [dbo].[T_Employee] te on te.E_Id = tm.ES_EId and te.E_Activited = '1'
where te.E_Id is not null 

这一段存储过程可以查询子节点的所有父节点,来试验一下 

好的,骚操作完成。

显然,这样。获取子节点的全部父节点的时候很麻烦。

  • 查询老王管理的所有员工

思路如下:先获取所有父节点为老王id的员工id,然后将员工姓名加入结果列表里,在调用一个神奇的查找函数,即可进行神奇的查找:

CREATE DEFINER=`root`@`localhost` FUNCTION `getSubordinate`(`uid` int) RETURNS varchar(2000) CHARSET gb2312
BEGIN   
DECLARE str varchar(1000);  
DECLARE cid varchar(100);
DECLARE result VARCHAR(1000);
DECLARE tmpName VARCHAR(100);
SET str = '$';   
SET cid = CAST(uid as char(10));   
WHILE cid is not null DO   
  SET str = concat(str, ',', cid); 
  SELECT group_concat(eid) INTO cid FROM employees where FIND_IN_SET(parent_id,cid);         
END WHILE;
  SELECT GROUP_CONCAT(ename) INTO result FROM employees WHERE FIND_IN_SET(parent_id,str);
RETURN result;   
END

SQL SERVER 可以采用 CET(Common Table Expressions) 表达式

;with TeamMember as(
    select *, ES_EId as DM, 0 as rank from [dbo].[T_EmployeeSystem]
    where ES_EId in (select * from #teamLeader)
    union all
    select te.*, tm.DM, tm.rank + 1 from [dbo].[T_EmployeeSystem] te
    join TeamMember tm on te.ES_PEId = tm.ES_EId
)

select te.E_StaffID as StaffID, te.E_AD as ADName, te.E_EN_Name as UserName from TeamMember tm
left join [dbo].[T_Employee] te on te.E_Id = tm.ES_EId and te.E_Activited = '1'
where te.E_Id is not null and tm.ES_EId not in (select * from #teamLeader)

虽然搞出来了,但说实话,真是不容易。。。

这种方法的优点是存储的信息少,查直接上司和直接下属的时候很方便,缺点是多级查询的时候很费劲。所以当只需要用到直接上下级关系的时候,用这种方法还是不错的,可以节省很多空间。后续还会介绍其它存储方案,并没有绝对的优劣之分,适用场合不同而已。

Path Enumeration 路径枚举法,记录下根节点到每个子节点的路径

先创建表

CREATE TABLE employees2(
    eid INT,
    ename VARCHAR(100),
    position VARCHAR(100),
    path VARCHAR(200)
)

然后插入数据:

现在我们来回答一下之前的问题:

  • 查询小天的直接上司

    在上一个解决方案中能轻而易举做到的事情,在这个方案中却有些麻烦了,因为需要对path字段进行字符串处理,去掉“/”+自身id才是直接上司的path值。又开始一顿骚操作:

    SELECT e1.eid,e1.ename FROM employees2 e1,employees2 e2 WHERE e2.ename = '小天' AND e1.path = REPLACE(e2.path,CONCAT('/',e2.eid),'');
    

    好像这个操作还不够sao,2333,结果如下:

  • 查询老宋管理下的直属员工

    怎么查管理下的直属员工呢?那就要用模糊查询了:

    SELECT e2.eid,e2.ename FROM employees2 e1,employees2 e2 WHERE e1.ename = '老宋' AND e2.path REGEXP CONCAT(e1.path,'/[0-9]{1,}$');
    

    这里用了正则匹配,匹配所有path符合规则的记录,结果如下:

  • 查询小天的所有上司

    SELECT e1.eid,e1.ename FROM employees2 e1,employees2 e2 WHERE e2.ename='小天' AND e2.path like concat(e1.path,'/%');
    

    这里就能体现这种存储结构的优势了。不看效率的话,还是很方便的。

  • 查询老王管理的所有员工

    SELECT e2.eid,e2.ename FROM employees2 e1,employees2 e2 WHERE e1.ename='老王' AND e2.path like concat(e1.path,'/%');
    

    看吧,查起来就so easy了。

    不用像之前那样写一大段存储过程了,简单粗暴。

小结一下,存储路径的方式在进行多级查询的时候十分方便,而在查询直接上下级的时候稍微复杂一点。还有一个很明显的缺点,那就是path的大小是指定的,所以理论上是不能进行无限层级的存储的,path值设置的越大,浪费的空间就越多。

Closure Table 闭包表(环表)

Closure Table 闭包表(环表),保存每个节点与其各个子节点的关系,也就是记录以其为根节点的全部子节点信息。直接上代码就明白了:

这里要创建两个表,一个表用来存储信息:

CREATE TABLE employees3(
    eid INT,
    ename VARCHAR(100),
    position VARCHAR(100)
)

一个表用来存储关系

CREATE TABLE emp_relations(
    root_id INT,
    depth INT,
    is_leaf TINYINT(1),
    node_id INT
)

这里的root_id用来存放以其为根节点的路径,node_id表示节点处的eid,depth表示根节点到该节点的深度,is_leaf表示该节点是否为叶子节点。

接下来插入数据:

可以看出,这个关系表有点大,我们先来看看查询效果如何:

  • 查询小天的直接上司

    这里只需要在关系表中找到node_id为小天id,depth为1的根节点id即可。

    SELECT e2.ename BOSS FROM employees3 e1,employees3 e2,emp_relations rel 
    WHERE e1.ename='小天' AND rel.node_id=e1.eid AND rel.depth=1 AND e2.eid=rel.root_id
    

  • 查询老宋管理下的直属员工

    思路差不多,只要查询root_id为老宋eid且深度为1的node_id即为其直接下属员工id

    SELECT e1.eid,e1.ename 直接下属 FROM employees3 e1,employees3 e2,emp_relations rel 
    WHERE e2.ename='老宋' AND rel.root_id=e2.eid AND rel.depth=1 AND e1.eid=rel.node_id
    

  • 查询小天的所有上司

    只要在关系表中找到node_id为小天eid且depth大于0的root_id即可

    SELECT e2.eid,e2.ename 上司 FROM employees3 e1,employees3 e2,emp_relations rel 
    WHERE e1.ename='小天' AND rel.node_id=e1.eid AND rel.depth>0 AND e2.eid=rel.root_id
    

  • 查询老王管理的所有员工

    只要在关系表中查找root_id为老王eid,depth大于0的node_id即可

    SELECT e1.eid,e1.ename 下属 FROM employees3 e1,employees3 e2,emp_relations rel 
    WHERE e2.ename='老王' AND rel.root_id=e2.eid AND rel.depth>0 AND e1.eid=rel.node_id
    

我们可以发现,这四个查询的复杂程度是一样的,这就是这种存储方式的优点,而且可以让另一张表只存储跟节点紧密相关的信息,看起来更简洁。但缺点也显而易见,关系表会很庞大,当层次很深,结构很庞大的时候,关系表数据的增长会越来越快,相当于用空间效率来换取了查找上的时间效率。

总结

至此,树形结构在数据库中存储的三种方式就介绍完了,接下来对比一下三种方法:

  • 方案一:Adjacency List

    • 优点:只存储上级id,存储数据少,结构类似于单链表,在查询相邻节点的时候很方便。添加删除节点都比较简单。
    • 缺点:查询多级结构的时候会显得力不从心。
    • 适用场合:对多级查询需求不大的场景比较适用。
  • 方案二:Path Enumeration

    • 优点:查询多级结构的时候比较方便。查询相邻节点时也比较ok。增加或者删除节点的时候比较简单。
    • 缺点:需要存储的path值可能会很大,甚至超过设置的最大值范围,理论上无法无限扩张。
    • 适用场合:结构相对简单的场景比较适合。
  • 方案三:Closure Table

  - 优点:在查询树形结构的任意关系时都很方便。   - 缺点:需要存储的数据量比较多,索引表需要的空间比较大,增加和删除节点相对麻烦。   - 适用场合:纵向结构不是很深,增删操作不频繁的场景比较适用。

知识共享许可协议
《如何将树形结构存储在数据库中》 常伟华 创作。
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议 | 3.0 中国大陆许可协议进行许可。

站内公告

A PHP Error was encountered

Severity: Core Warning

Message: PHP Startup: zip: Unable to initialize module Module compiled with module API=20060613 PHP compiled with module API=20090626 These options need to match

Filename: Unknown

Line Number: 0

Backtrace: