【Mysql】mysql 存储树形结构（非遍历方法查找树结构）

Popo's Blog 8/23/2019 MySql Tree

背景：部门产品存在文件夹树形结构的功能，但原来的设计对于文件夹树的获取需要遍历进行IO 查询，存在性能瓶颈，探索非遍历方案获取树形结构，性能调优。

树结构如下：

测试数据树结构图

查询节点为 p,已知 p 节点id,探究分别查询 p 节点的父节点，祖父节点，子节点，子孙节点的复杂程度, 以及节点移动（p移动到b 节点下面）、节点删除(删除p节点，p节点子节点跟进，为d的子节点)、节点新增（p节点添加子节点 w）

原设计方案（Adjacency list 邻接表）：

每一条记录存parent_id

表结构：

CREATE TABLE `folder` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id，自增',
  `folderName` varchar(100) NOT NULL COMMENT '文件名',
  `parentId` int(11) NOT NULL COMMENT '父节点id',
  PRIMARY KEY (`id`),
  INDEX `idx_parent_id` (`parentId` ASC)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT = '文件夹表';

1
2
3
4
5
6
7

测试数据

    INSERT INTO `folder` (id,folderName,parentId)VALUES (1,'a',0); 
    INSERT INTO `folder` (id,folderName,parentId)VALUES (2,'b',0);  
    INSERT INTO `folder` (id,folderName,parentId)VALUES (3,'c',0);  
    INSERT INTO `folder` (id,folderName,parentId)VALUES (4,'d',1);  
    INSERT INTO `folder` (id,folderName,parentId)VALUES (5,'e',1);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (6,'f',1);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (7,'x',2);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (8,'y',2);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (9,'z',2);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (10,'p',4);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (11,'q',4);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (12,'r',4);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (13,'t',5);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (14,'u',10);
    INSERT INTO `folder` (id,folderName,parentId)VALUES (15,'v',14);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查询语句

p 节点的父节点

select * from folder where id=(select parentId from folder where id=10);

p 节点祖父节点

DROP FUNCTION IF EXISTS `getParentList`;
DELIMITER //
CREATE FUNCTION `getParentList`(rootId varchar(100)) 
RETURNS varchar(1000) 
BEGIN 
DECLARE fid varchar(100) default ''; 
DECLARE str varchar(1000) default rootId; 
WHILE rootId is not null  do 
	SET fid =(SELECT parentId FROM folder WHERE id = rootId); 
	IF fid is not null THEN 
		SET str = concat(str, ',', fid); 
		SET rootId = fid; 
	ELSE 
		SET rootId = fid; 
	END IF; 
END WHILE; 
return str;
END  //
DELIMITER ;
select * from folder where FIND_IN_SET(id,getParentList(10))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

p 节点子节点

select * from folder where parentId=10;

p 节点子孙节点

  `DROP FUNCTION IF EXISTS `getChildList`;
  DELIMITER //
  CREATE FUNCTION `getChildList`(rootId INT)
  RETURNS varchar(1000) READS SQL DATA
  BEGIN
    DECLARE sTemp VARCHAR(1000);
    DECLARE sTempChd VARCHAR(1000);
    SET sTemp = '$';
    SET sTempChd =cast(rootId as CHAR);
    WHILE sTempChd is not null DO
      SET sTemp = concat(sTemp,',',sTempChd);
      SELECT group_concat(id) INTO sTempChd FROM folder where FIND_IN_SET(parentId,sTempChd)>0;
    END WHILE;
    RETURN sTemp;
  END  //
  DELIMITER ;
  select *from folder where find_in_set(id, getChildList(10));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

节点新增（p节点添加子节点 w） INSERT INTO folder (folderName,parentId)VALUES ('w',10);
节点移动（p移动到b 节点下面，p 节点子孙节点跟随）

UPDATE folder f, ( SELECT * FROM folder WHERE folderName = 'b' ) temp 
SET f.parentId = temp.id 
WHERE f.id = 10;

1
2
3

节点删除(删除p节点，p节点子节点 u 跟进，为d的子节点)

update folder f,(select * from folder where folderName='p') temp
set f.parentId=temp.parentId
where f.parentId=10;
delete from folder where id=10;

1
2
3
4

获取整棵树结构(需要知道树层级结构)

SELECT t1.folderName AS lev1, t2.folderName as lev2, t3.folderName as lev3, t4.folderName as lev4,t5.folderName as lev5
FROM folder AS t1
LEFT JOIN folder AS t2 ON t2.parentId = t1.id
LEFT JOIN folder AS t3 ON t3.parentId = t2.id
LEFT JOIN folder AS t4 ON t4.parentId = t3.id
LEFT JOIN folder AS t5 ON t5.parentId = t4.id
WHERE t1.folderName = 'a';

1
2
3
4
5
6
7

邻接表树数据图

路径表（Path Enumeration）

每一条记录存整个tree path经过的node枚举

表结构：

CREATE TABLE `path_folder` (
  `id` INT(11) NOT NULL AUTO_INCREMENT COMMENT '主键id,自增',
  `folderName` VARCHAR(100) NOT NULL COMMENT '文件夹名称',
  `path` VARCHAR(200) NOT NULL COMMENT '路径',
  `parentId` INT(11) NOT NULL DEFAULT 0 COMMENT '父节点id'
  PRIMARY KEY (`id`))
ENGINE = InnoDB
DEFAULT CHARSET = utf8mb4
COMMENT = '路径文件夹表';

1
2
3
4
5
6
7
8
9

测试数据

    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (1,'a','/0',0); 
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (2,'b','/0',0);  
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (3,'c','/0',0);  
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (4,'d','/1',1);  
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (5,'e','/1',1);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (6,'f','/1',1);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (7,'x','/2',2);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (8,'y','/2',2);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (9,'z','/2',2);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (10,'p','/1/4',4);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (11,'q','/1/4',4);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (12,'r','/1/4',4);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (13,'t','/1/5',5);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (14,'u','/1/4/10',10);
    INSERT INTO `path_folder` (id,folderName,path,parentId)VALUES (15,'v','/1/4/10/14',14);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查询语句

p 节点的父节点

select * from path_folder where id=(select parentId from path_folder where id=10);

p 节点祖父节点

  SELECT *
  FROM path_folder
  WHERE id IN (
  	SELECT substring_index(substring_index(t.path, '/', b.help_topic_id + 1), '/', -1)
  	FROM path_folder t
  		JOIN mysql.help_topic b ON b.help_topic_id < LENGTH(t.path) - LENGTH(REPLACE(t.path, '/', '')) + 1
  	WHERE id = 10
  );

1
2
3
4
5
6
7
8

字符串切割参考文章

p 节点子节点

select * from path_folder where parentId=10;

p 节点子孙节点

SELECT * FROM path_folder
WHERE path LIKE '%/10%';

1
2

节点新增（p节点添加子节点 w）

INSERT INTO path_folder (folderName, path, parentId)
SELECT 'w', concat((
		SELECT path
		FROM path_folder
		WHERE id = 10
	), '/10'), 10;

1
2
3
4
5
6

节点移动（p移动到b 节点下面，p 节点子孙节点跟随）

UPDATE path_folder pf, (
		SELECT *
		FROM path_folder
		WHERE folderName = 'b'
	) b, (
		SELECT *
		FROM path_folder
		WHERE id = 10
	) p
SET pf.path = replace(pf.path, p.path, concat(if(b.path = '/0', '', b.path), '/', b.id))
WHERE pf.path LIKE concat('%', p.path, '/%')
	OR pf.id = 10;
	UPDATE path_folder f, ( SELECT * FROM path_folder WHERE folderName = 'b' ) temp 
    SET f.parentId = temp.id 
    WHERE f.id = 10;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

节点删除(删除p节点，p节点子节点 u 跟进，为d的子节点)

update path_folder f,(select * from path_folder where folderName='p') temp
set f.parentId=temp.parentId
where f.parentId=10;
update path_folder
set path=replace(path,'/10','')
where path like "%/10%";
delete from folder where id=10;

1
2
3
4
5
6
7

嵌套集（Nested Sets）

每一条记录存 nleft 和 nright 此处不适合当前业务，故不展开讨论，附相关博客地址，有需求可自行参考
树形结构的数据库表Schema设计
 基于左右值编码的树形数据库表结构设计
 在MySQL中存储树状结构

路径表（Closure Table）

维护一个表，所有的tree path作为记录进行保存

表结构

CREATE TABLE `closure_path` (
  `id` INT(11) NOT NULL AUTO_INCREMENT COMMENT '主键id,自增',
  `folderName` VARCHAR(100) NOT NULL COMMENT '文件夹名称',
  PRIMARY KEY (`id`))
ENGINE = InnoDB
DEFAULT CHARACTER SET = utf8mb4
COMMENT = '路径表';


CREATE TABLE `closure_path_relation` (
  `id` INT NOT NULL AUTO_INCREMENT COMMENT '主键id,自增',
  `ancestor` INT(1) NOT NULL COMMENT '祖先id',
  `descendant` INT(11) NOT NULL COMMENT '后裔',
  `isLeaf` TINYINT(11) NOT NULL COMMENT '是否为叶子节点',
  `depth` INT(6) NOT NULL DEFAULT 0 COMMENT '深度',
  PRIMARY KEY (`id`))
ENGINE = InnoDB
DEFAULT CHARACTER SET = utf8mb4
COMMENT = '路径关系表';

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

测试数据

    INSERT INTO `closure_path` (id,folderName)VALUES (1,'a'); 
    INSERT INTO `closure_path` (id,folderName)VALUES (2,'b');  
    INSERT INTO `closure_path` (id,folderName)VALUES (3,'c');  
    INSERT INTO `closure_path` (id,folderName)VALUES (4,'d');  
    INSERT INTO `closure_path` (id,folderName)VALUES (5,'e');
    INSERT INTO `closure_path` (id,folderName)VALUES (6,'f');
    INSERT INTO `closure_path` (id,folderName)VALUES (7,'x');
    INSERT INTO `closure_path` (id,folderName)VALUES (8,'y');
    INSERT INTO `closure_path` (id,folderName)VALUES (9,'z');
    INSERT INTO `closure_path` (id,folderName)VALUES (10,'p');
    INSERT INTO `closure_path` (id,folderName)VALUES (11,'q');
    INSERT INTO `closure_path` (id,folderName)VALUES (12,'r');
    INSERT INTO `closure_path` (id,folderName)VALUES (13,'t');
    INSERT INTO `closure_path` (id,folderName)VALUES (14,'u');
    INSERT INTO `closure_path` (id,folderName)VALUES (15,'v');
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,1,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (2,2,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (3,3,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (4,4,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (5,5,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (6,6,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (7,7,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (8,8,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (9,9,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (10,10,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (11,11,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (12,12,0,0);
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (13,13,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (14,14,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (15,15,0,0); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,4,0,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,5,0,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,6,1,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,10,0,2); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,11,0,2); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,12,0,2); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,13,1,2); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,14,0,3); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (1,15,1,4); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (2,7,1,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (2,8,1,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (2,9,1,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (5,13,1,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (4,10,0,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (4,11,1,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (4,12,1,1);
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (4,14,0,2); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (4,15,1,4);
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (10,14,0,1); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (10,15,1,2); 
    INSERT INTO `closure_path_relation` (ancestor,descendant,isLeaf,depth)VALUES (14,15,1,1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

查询语句

p 节点的父节点

select * from closure_path
where id in(
select ancestor from closure_path_relation
where descendant=10 and depth=1);

1
2
3
4

p 节点祖父节点

select * from closure_path
where id in(
select ancestor from closure_path_relation
where descendant=10 and depth!=0);

1
2
3
4

p 节点子节点

select * from closure_path
where id in(
select descendant from closure_path_relation
where ancestor=10 and depth=1);

1
2
3
4

p 节点子孙节点

select * from closure_path
where id in(
select descendant from closure_path_relation
where ancestor=10 and depth!=0);

1
2
3
4

节点新增（p节点添加子节点 w）

insert into closure_path(folderName) values('w');
insert into closure_path_relation(ancestor,descendant,isLeaf,depth)
select ancestor,(select id from closure_path where folderName ='w'),1,(depth+1) from closure_path_relation
where descendant=10;
insert into closure_path_relation(ancestor,descendant,isLeaf,depth)
select id,id,1,0 from closure_path
where folderName='w';

1
2
3
4
5
6
7

节点移动（p移动到b 节点下面,p 节点子孙节点跟随） // todo 待添加
节点删除(删除p节点，p节点子节点 u 跟进，为d的子节点)

update closure_path_relation
set depth=depth-1
where descendant in(select descendant from (select descendant from closure_path_relation
where ancestor=10)temp);
delete from closure_path_relation
where descendant=10 or ancestor=10;
delete from closure_path
where id=20;

1
2
3
4
5
6
7
8

advantage && disvantage

优缺点对比图

popo先生的博客

【Mysql】mysql 存储树形结构（非遍历方法查找树结构）

# 树结构如下：

# 原设计方案（Adjacency list 邻接表）：

# 路径表（Path Enumeration）

# 嵌套集（Nested Sets）

# 路径表（Closure Table）

# advantage && disvantage

树结构如下：

原设计方案（Adjacency list 邻接表）：

路径表（Path Enumeration）

嵌套集（Nested Sets）

路径表（Closure Table）

advantage && disvantage