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

树结构如下：

测试数据树结构图

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

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

每一条记录存parent_id

1. 表结构：
   <pre>
   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 = '文件夹表';
   </pre>
2. 测试数据
   <pre>
   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);
   </pre>
3. 查询语句

• p 节点的父节点
  <pre>
  select * from folder where id=(select parentId from folder where id=10);
  </pre>

• p 节点 祖父节点
  <pre>
  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))
  </pre>

• p 节点 子节点
  <pre>
  select * from folder where parentId=10;
  </pre>

• p 节点 子孙节点
  <pre>
  DROP FUNCTION IF EXISTSgetChildList; DELIMITER // CREATE FUNCTIONgetChildList`(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));
  </pre>

• 节点新增（p节点添加子节点 w）
  INSERT INTO folder (folderName,parentId)VALUES ('w',10);

• 节点移动（p移动到b 节点下面，p 节点子孙节点跟随）
  <pre>
  UPDATE folder f, ( SELECT * FROM folder WHERE folderName = 'b' ) temp
  SET f.parentId = temp.id
  WHERE f.id = 10;
  </pre>

• 节点删除(删除p节点，p节点子节点 u 跟进，为d的子节点)
  <pre>
  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;
  </pre>

• 获取整棵树结构(需要知道 树 层级结构)
  <pre>
  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';
  </pre>

  
  邻接表树数据图

路径表（Path Enumeration）

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

1. 表结构：
   <pre>
   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 = '路径文件夹表';
   </pre>
2. 测试数据
   <pre>
   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);
   </pre>
3. 查询语句

• p 节点的父节点
  <pre>
  select * from path_folder where id=(select parentId from path_folder where id=10);
  </pre>
• p 节点 祖父节点
  <pre>
  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
  );
  </pre>

字符串切割参考文章

• p 节点 子节点
  <pre>
  select * from path_folder where parentId=10;
  </pre>

• p 节点 子孙节点
  <pre>
  SELECT * FROM path_folder
  WHERE path LIKE '%/10%';
  </pre>

• 节点新增（p节点添加子节点 w）
  <pre>
  INSERT INTO path_folder (folderName, path, parentId)
  SELECT 'w', concat((
  SELECT path
  FROM path_folder
  WHERE id = 10
  ), '/10'), 10;
  </pre>

• 节点移动（p移动到b 节点下面，p 节点子孙节点跟随）
  <pre>
  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;
  </pre>

• 节点删除(删除p节点，p节点子节点 u 跟进，为d的子节点)
  <pre>
  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;
  </pre>

嵌套集（Nested Sets）

每一条记录存 nleft 和 nright
此处不适合当前业务，故不展开讨论，附相关博客地址，有需求可自行参考


树形结构的数据库表Schema设计


基于左右值编码的树形数据库表结构设计


在MySQL中存储树状结构

路径表（Closure Table）

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

1. 表结构
   <pre>
   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 = '路径表';
   </pre>
   <pre>
   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 = '路径关系表';
   </pre>

2. 测试数据
   <pre>
   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);
   </pre>

3. 查询语句

• p 节点的父节点
  <pre>
  select * from closure_path
  where id in(
  select ancestor from closure_path_relation
  where descendant=10 and depth=1);
  </pre>

• p 节点 祖父节点
  <pre>
  select * from closure_path
  where id in(
  select ancestor from closure_path_relation
  where descendant=10 and depth!=0);
  </pre>

• p 节点 子节点
  <pre>
  select * from closure_path
  where id in(
  select descendant from closure_path_relation
  where ancestor=10 and depth=1);
  </pre>

• p 节点 子孙节点
  <pre>
  select * from closure_path
  where id in(
  select descendant from closure_path_relation
  where ancestor=10 and depth!=0);
  </pre>

• 节点新增（p节点添加子节点 w）
  <pre>
  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';
  </pre>

• 节点移动（p移动到b 节点下面,p 节点子孙节点跟随）
  // todo 待添加

• 节点删除(删除p节点，p节点子节点 u 跟进，为d的子节点)
  <pre>
  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;
  </pre>

advantage && disvantage

优缺点对比图

---

popo先生的博客

---