首页 >数据库 >mysql教程 >如何使用mysql存储树形关系_MySQL

如何使用mysql存储树形关系_MySQL

WBOY
WBOY原创
2016-06-01 13:17:201205浏览

最近遇到业务的一个类似文件系统的存储需求,对于如何在mysql中存储一颗树进行了一些讨论,分享一下,看看有没有更优的解决方案。

 

一、现有情况

首先,先假设有这么一颗树,一共9个节点,1是root节点,一共深3层。(当然实际业务不会这么简单)

原有的表结构如下:

id parents_id name full_path
1 0 a /a
2 1 b /a/b
3 1 c /a/c
4 1 d /a/d
5 4 e /a/d/e
6 4 f /a/d/f
7 5 g /a/d/e/g
8 5 h /a/d/e/h
9 5 i /a/d/e/i

 

 

 

 

 

 

 

 

 

 

 

需要满足的几个基本需求为:

1、从上到下逐层展开目录层级

2、知道某一个目录反查其全路径

3、rename某一个路径的名字

4、将某一个目录挪到其他目录下

 

现有的表结构可以满足以上的需求:

1、select id from table where parents_id=$id;(可以查出所有直接子节点)2、select full_path from table where id=$id;(通过全路径字段获取)3、update table set name=$newname where id=$id;(将需要修改的id的name字段修改)4、update table set parents_id=$new_parents_id,full_path=$new_full_path where id=$id;(修改父子关系到新的关系上)

 

但是现有的表结构会遇到的问题就是,第3和第4个需求,其并不是只更新一行即可,由于有full_path的存在,所有被修改的节点,其下面的所有节点的full_path都需要修改。这就无形之间增加了很多写操作,如果这颗树比较深,比如有100层,那么修改第3层的数据,那么就意味着其下面97层的所有数据都需要被修改,这个产生的写操作就有些恐怖了。

以列子所示,如果4的name被修改,都会影响4,5,6,7,8,9一共6行数据的更新,这个写逻辑放大的有点厉害。

update table set name=x,full_path='/a/x' where id=4;update table set full_path='/a/x/e' where id=5;update table set full_path='/a/x/f' where id=6;update table set full_path='/a/x/e/g' where id=7;update table set full_path='/a/x/e/h' where id=8;update table set full_path='/a/x/e/i' where id=9;

那么如何解决这个问题呢?

 

二、优化方案

1、去除full_path字段

上面所述问题最严重的就是写逻辑放大的问题,采用去除full_path字段后,6条update就变成1条update的了。

这个优化看起来完美解决写逻辑放大问题,但是引入了另一个问题,那就是需求2的满足费劲了。

原有SQL是:

select full_path from table where id=$id;

但是去除full_path字段之后,变为:

select parents_id from table where id =$id;select parents_id from table where id = $parents_id;

以示例来说,如果要得到9的全路径,那么就需要如下SQL

select parents_id,name from table where id = 9;select parents_id,name from table where id = 5;select parents_id,name from table where id = 4;select parents_id,name from table where id = 1;

当最后判断到parents_id=0的时候结束,然后将所有name聚合在一起。

如果所有操作都需要前端实现,那么就需要前端和DB交互4次,这期间消耗的链接成本会极大的延长总体的响应时间,基本是不可接收的。

如果要采用这种方案,目前看来只有使用存储过程,将所有计算都在本地完成之后在返回给端,保证一次请求,一次返回,这样才最效率,但是mysql的存储过程个人不太建议使用,风险较大。

 

2、产品规范

我们的问题会发生在树的层级特别多的情况下,那么可以通过产品规范来进行限制,比如最深只能有4层,这样就将问题遏制在发生之前了。(当然,有些时候这种最有效的优化方案是最不可能实现的,产品不会那么容易妥协)

 

3、增加cache

问题既然是写逻辑放大,那么如果我们将优化思路从降低写入次数,改为提高写入性能呢?

我们引入redis这种nosql存储,将id和full_path存放在redis中,每次更新数据库之后在更新redis,redis的写入性能远高于mysql,这样问题也可以得到解决。

只不过由于更新不是同步的,采用异步更新之后,数据会最终一致,但是在某一个特殊时间点可能会存在不一致。

并且由于存储架构变化,需要代码方面做出一定的妥协,无论是读操作还是写操作。

 

4、整体改变存储结构

以上方案都是在不大改现有表结构的基础上做出的,那么有没有可能修改表结构之后情况会不一样呢?

我们对所示例子的存储结构引入层级的概念,去除full_path,看看是否可以解决问题。

新的表结构如下:

id_name(id和name映射关系)

id name
1 a
2 b
3 c
4 d
5 e
6 f
7 g
8 h
9 i

 

 

 

 

 

 

 

 

 

 

relation(父子关系)

id chailds depth
1 1 0
1 2 1
1 3 1
1 4 1
1 5 2
1 6 2
1 7 3
1 8 3
1 9 3
2 2 0
3 3 0
4 4 0
4 5 1
4 7 2
4 8 2
4 9 2
5 5 0
5 7 1
5 8 1
5 9 1
6 6 0
7 7 0
8 8 0
9 9 0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

这两张新表第一张不用解释了,第二张id字段存放节点id,chailds字段存放其所有子节点(并不是直接chaild,而是不论层级都存放),depth字段存放其子节点和本节点的层级关系。

我们看下这么设计是否可以满足最初的4个需求:

需求1:逐层展开目录

select id,depth from table2 where id=$id;select name from table1 where id=$id;

由于每个id都存放了其所有的子节点,所以如果查询4的所有下属目录,直接select id,depth from table2 where id = 4;一条SQL即可获得所有结果,只要前端在处理一下即可。

id chailds depth
4 4 0
4 5 1
4 6 1
4 7 2
4 8 2
4 9 2

 

 

 

 

 

 

 

 

需求2:根据某一个目录获知其全路径

select id,depth from table2 where chailds = $id;

由于每个id都存放了所有子节点,所以反差也是一条sql的事情。比如查询9的全路径,那么select id,depth from table2 where chailds=9;得到的结果应该是

id chailds depth
9 9 0
5 9 1
4 9 2
1 9 3

 

 

 

 

 

通过上述结果,前端进行计算处理就可以得到9的全路径了,并且是一条sql获得,不需要前端和db多次交互,也不需要引入存储过程。

 

需求3:更改目录名称

update table1 set name = $new_name where id = $id ;

这个最简单了,只需要更改映射表即可。

 

需求4:更改节点的父子关系

select id from table2 where id=$id and depth > 0;delete from table2 where id = $sql1_id;select id from table2 where id = $new_father_id;inset into table2 values ($sql2_id,$id,$depth+1);

这个需求目前看来最麻烦,我们以示例所示,如果将5挪到3下面需要经过哪些操作?

I:先查出来5都属于哪些节点的子节点。

select id from table 2 where id=5 and depth > 0;

id

chailds depth
1 5 2
4 5 1

 

 

 

 

II:删除这些记录。

delete from table2 where id=1 and chailds=5;

delete from table2 where id=4 and chailds=5;

III:查出新父节点是哪些节点的子节点。

select id,depth from table where chailds=3 and depth > 0 ;

id chailds depth
1 3 1

 

 

IIII:

根据III的结果插入新的关系。

insert into table2 values (1,5,2);

由于新父节点只是1的子节点,故只需要在增加5和1个关系既可,同时由于3是5的新父节点,那么5和1的深度关系应该比3的关系“+1”。

而所有5下面的节点都不需要更改,因为这么设计所有节点都是自己子节点的root,所以只要修改5的关系即可。

但是这个解决方案明显可以看出来,需要存储的关系比原有情况多了很多倍,尤其是关系层级深的情况下。

 

三、总结

方案1:解决写逻辑放大问题,但是引入了读逻辑放大问题,并需要引入存储过程解决。

方案2:产品规范解决,最彻底的解决方法,但需要和PM沟通确认,业务很难妥协。

方案3:引入cache解决写入性能,但是需要代码进行修改,并存在数据不一致的风险。

方案4:解决写逻辑放大问题,也没有引入读逻辑放大问题,仅仅只是在更改目录的时候稍微麻烦一些,但是引入了初始存储容量暴增的问题。

目前看来,并没有什么特别优秀的方案,都需要付出一定的代价。

 

ps:本文的思路参考了《SQL反模式》,如果有兴趣的读者可以去研读一下。

 

 

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn