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

关注

发布于: 1 小时前

方法一父节点表示法

每一个节点持有父节点的引用。为了更好的处理森林，抽象一个不存在的 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

发布于: 1 小时前阅读数: 6

原文链接:【http://xie.infoq.cn/article/af8417e463d041740fab02f9d】。文章转载请联系作者。

王博

关注

我是一名后端，写代码的憨憨 2018.12.29 加入

还未添加个人简介

发布

暂无评论

创作场景

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

方法一 父节点表示法

方法二 路径表示法

查询数据

查询森林的根节点

查询节点 A 的所有子孙节点

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

方法 3 前序遍历法

王博

评论

方法一父节点表示法

方法二路径表示法