关系型数据库如何存储树形结构？

方法一 父节点表示法

每一个节点持有父节点的引用。为了更好的处理森林，抽象一个不存在的0节点，森林中所有树挂在改节点下，将森林转换为一颗树来处理。

CREATE TABLE node1 (
  id INT AUTO_INCREMENT PRIMARY KEY ,
  name VARCHAR(12) NOT NULL,
  num INT NOT NULL DEFAULT 0 COMMENT '节点下叶子的数量',
  p_id INT NOT NULL DEFAULT 0 COMMENT '0表示根节点'
 );

此方法结构简单，更新也简单，但是在查询子孙节点时，效率低下.

方法二 路径表示法

在方法一的基础上，添加path_key（search_key）字段，该字段存储从根节点到节点的标识路径，这里依然抽象一个不存在的0节点。

CREATE TABLE node2 (
  id INT AUTO_INCREMENT PRIMARY KEY ,
  name VARCHAR(12) NOT NULL ,
  num INT NOT NULL DEFAULT 0 COMMENT '节点下叶子的数量',
  p_id INT NOT NULL DEFAULT 0 COMMENT '0表示根节点',
  search_key VARCHAR(128)  DEFAULT '' COMMENT '用来快速搜索子孙的key，存储根节点到该节点的路径',
  level INT DEFAULT 0 COMMENT '层级'
);

插入数据

INSERT INTO node2(id,name, num, p_id,search_key) VALUES
  (1,'A',10,0,'0-1'),
  (2,'B',7,1,'0-1-2'),
  (3,'C',3,1,'0-1-3'),
  (4,'D',1,3,'0-1-3-4'),
  (5,'E',2,3,'0-1-3-5'),
  (6,'F',2,0,'0-6'),
  (7,'G',2,6,'0-6-7');

查询数据

# 查询森林的根节点
SELECT * FROM node2 WHERE p_id = 0 AND search_key LIKE '0-%' AND level = 0;

# 查询节点A的所有子孙节点
#####  SELECT * FROM node2 WHERE search_key LIKE '{A.search_key}%';
SELECT * FROM node2 WHERE search_key LIKE '0-1-%';

更新数据（当插入一定量叶子结点时）

# 例如，更新节点C的权重
UPDATE node2,(SELECT sum(num) AS sum FROM node2 WHERE search_key LIKE '0-1-3-%') rt SET num = rt.sum WHERE id=3;

有节点权重累加时，将所有父辈权重再加1，只需要将该节点的search_key以'-' 切分，得到的就是所有父辈的id（0除外）。例如，将节点D的权重+1，这里使用where locate，实际更好是先将search_key split之后使用where in查询

UPDATE node2,(SELECT search_key FROM node2 WHERE id = 4) rt SET num=num+1 WHERE locate(id,rt.search_key);

删除某个节点，比如删除B节点

假设删除节点子孙全部清理

DELETE FROM node2 WHERE search_key LIKE '0-1-2%';

方法3 前序遍历法

给节点分配左右值，第一次到达该节点时，设置左值，第二次到达该节点，设置右值，每走一步，序号加1

CREATE TABLE node3 (
   id INT AUTO_INCREMENT PRIMARY KEY ,
   tree_id INT NOT NULL COMMENT '为保证对某一棵的操作不影响森林中的其他书',
   name VARCHAR(12) NOT NULL ,
   num INT NOT NULL DEFAULT 0 COMMENT '节点下叶子的数量、节点权重（可认为分类下产品数量）',
   lft INT NOT NULL ,
   rgt INT NOT NULL ,
   level INT DEFAULT 0
 );
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'B',7,2,3,2);
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'D',1,5,6,3);
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'E',2,7,8,3);
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'C',3,4,9,2);
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (1,'A',10,1,10,1);
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (2,'G',2,2,3,2);
insert into node3 (tree_id, name, num, lft, rgt, level) VALUE (2,'F',2,1,4,1);

这里加入了一个tree_id字段，用来保证对一棵树内的更新操作，不会影响到别的树，有利于提高效率。

插入数据(用tree_id判断是否同一棵树)

仔细看可以发现，在已有一个节点下append一个节点M的话，M的左右值应该连续的，按照先序遍历的顺序，只需要将走在其后的节点的左右值分别+2，并且M节点的父节点的右值必然也要+2。

查询数据

# 查询子节点
select * from node3 where lft >lft && rgt < rgt

# 查询父节点
select * from node3 where lft < lft && rgt >rgt