樹結(jié)構如下：

測試數(shù)據(jù)樹結(jié)構圖

查詢節(jié)點為 p,已知 p 節(jié)點id,探究 分別 查詢 p 節(jié)點的 父節(jié)點，祖父節(jié)點箫措，子節(jié)點衬潦，子孫節(jié)點的 復雜程度,
以及節(jié)點移動（p移動到b 節(jié)點下面）镀岛、節(jié)點刪除(刪除p節(jié)點，p節(jié)點子節(jié)點跟進驾锰，為d的子節(jié)點)走越、節(jié)點新增（p節(jié)點添加子節(jié)點 w）

原設計方案（Adjacency list 鄰接表）：

每一條記錄存parent_id

1. 表結(jié)構：
   <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 '父節(jié)點id',
   PRIMARY KEY (id),
   INDEX idx_parent_id (parentId ASC)
   ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT = '文件夾表';
   </pre>
2. 測試數(shù)據(jù)
   <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 節(jié)點的父節(jié)點
  <pre>
  select * from folder where id=(select parentId from folder where id=10);
  </pre>

• p 節(jié)點 祖父節(jié)點
  <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 節(jié)點 子節(jié)點
  <pre>
  select * from folder where parentId=10;
  </pre>

• p 節(jié)點 子孫節(jié)點
  <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>

• 節(jié)點新增（p節(jié)點添加子節(jié)點 w）
  INSERT INTO folder (folderName,parentId)VALUES ('w',10);

• 節(jié)點移動（p移動到b 節(jié)點下面裸扶，p 節(jié)點子孫節(jié)點跟隨）
  <pre>
  UPDATE folder f, ( SELECT * FROM folder WHERE folderName = 'b' ) temp
  SET f.parentId = temp.id
  WHERE f.id = 10;
  </pre>

• 節(jié)點刪除(刪除p節(jié)點，p節(jié)點子節(jié)點 u 跟進瞬项，為d的子節(jié)點)
  <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>

• 獲取整棵樹結(jié)構(需要知道 樹 層級結(jié)構)
  <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>

  
  
  鄰接表樹數(shù)據(jù)圖

路徑表（Path Enumeration）

每一條記錄存整個tree path經(jīng)過的node枚舉

1. 表結(jié)構：
   <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 '父節(jié)點id'
   PRIMARY KEY (id))
   ENGINE = InnoDB
   DEFAULT CHARSET = utf8mb4
   COMMENT = '路徑文件夾表';
   </pre>
2. 測試數(shù)據(jù)
   <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 節(jié)點的父節(jié)點
  <pre>
  select * from path_folder where id=(select parentId from path_folder where id=10);
  </pre>
• p 節(jié)點 祖父節(jié)點
  <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 節(jié)點 子節(jié)點
  <pre>
  select * from path_folder where parentId=10;
  </pre>

• p 節(jié)點 子孫節(jié)點
  <pre>
  SELECT * FROM path_folder
  WHERE path LIKE '%/10%';
  </pre>

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

• 節(jié)點移動（p移動到b 節(jié)點下面餐塘，p 節(jié)點子孫節(jié)點跟隨）
  <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>

• 節(jié)點刪除(刪除p節(jié)點皂吮，p節(jié)點子節(jié)點 u 跟進蜂筹，為d的子節(jié)點)
  <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
此處不適合當前業(yè)務，故不展開討論不翩，附相關博客地址麻裳，有需求可自行參考


樹形結(jié)構的數(shù)據(jù)庫表Schema設計


基于左右值編碼的樹形數(shù)據(jù)庫表結(jié)構設計


在MySQL中存儲樹狀結(jié)構

路徑表（Closure Table）

維護一個表津坑，所有的tree path作為記錄進行保存

1. 表結(jié)構
   <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 '是否為葉子節(jié)點',
   depth INT(6) NOT NULL DEFAULT 0 COMMENT '深度',
   PRIMARY KEY (id))
   ENGINE = InnoDB
   DEFAULT CHARACTER SET = utf8mb4
   COMMENT = '路徑關系表';
   </pre>

2. 測試數(shù)據(jù)
   <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 節(jié)點的父節(jié)點
  <pre>
  select * from closure_path
  where id in(
  select ancestor from closure_path_relation
  where descendant=10 and depth=1);
  </pre>

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

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

• p 節(jié)點 子孫節(jié)點
  <pre>
  select * from closure_path
  where id in(
  select descendant from closure_path_relation
  where ancestor=10 and depth!=0);
  </pre>

• 節(jié)點新增（p節(jié)點添加子節(jié)點 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>

• 節(jié)點移動（p移動到b 節(jié)點下面,p 節(jié)點子孫節(jié)點跟隨）
  // todo 待添加

• 節(jié)點刪除(刪除p節(jié)點穆役，p節(jié)點子節(jié)點 u 跟進孵睬，為d的子節(jié)點)
  <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

優(yōu)缺點對比圖

popo先生的博客