最近遇到业务的一个类似文件系统的存储需求,对于如何在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反模式》,如果有兴趣的读者可以去研读一下。