Storing Hierarchical data by 【Path Enumerations】

如何在数据库中存储层次结构

常见场景

公司：公司 - 部门 - 子部门
人员：领导 - 员工
文件：根目录 - 文件夹 - 文件
关系：group - child

实例

转成树型

Path Enumerations

每条记录存整个tree path经过的node枚举

id	name	path
1	DIR_A	/DIR_A
2	DIR_B	/DIR_A/DIR_B
3	DIR_C	/DIR_A/DIR_C
4	file_x	/DIR_A/file_x
5	file_y	/DIR_A/file_y
6	file_z	/DIR_A/file_z
7	DIR_D	/DIR_A/DIR_B/DIR_D
8	file_o	/DIR_A/DIR_B/file_o
9	file_p	/DIR_A/DIR_B/file_p
10	DIR_E	/DIR_A/DIR_C/DIR_E
11	file_m	/DIR_A/DIR_C/file_m
12	file_n	/DIR_A/DIR_C/file_n
13	file_l	/DIR_A/DIR_B/DIR_D/file_l
14	file_j	/DIR_A/DIR_C/DIR_E/file_j
15	file_k	/DIR_A/DIR_C/DIR_E/file_k

各种情况的处理代价

增

代价：-> O(1)
输入：name, path
执行：

1
insert into table(name, path) values($name, $path);

id	name	path
13	file_l	/DIR_A/DIR_B/DIR_D/file_l
14	file_j	/DIR_A/DIR_C/DIR_E/file_j
15	file_k	/DIR_A/DIR_C/DIR_E/file_k
16(add)	file_ADD	/DIR_A/DIR_C/DIR_E/file_ADD

删

代价：-> O(n)
输入：path
执行：

1
delete from table where path like CONCAT($path, '%') ;

改

代价：-> O(n)
输入：path, other info
执行：

1
2
3
4
5
6
7
8
9
pre: 
需要分割、拼接拿到old_path和new_path
mysql 5.7:
update table set info where path = $path
update table set path = REPLACE(
    CONCAT('^', path), 
    CONCAT('^', $old_path), 
    $new_path) 
where path like CONCAT($old_path, '%')

查

查自己

代价：-> O(1)
输入：path
执行：

1
select * from table where path = $path

查下一级

代价：-> O(n)
输入：id
执行：

1
select * from table where path regexp CONCAT('^', $path, '/.+', '((?!/).)')

查所有子集

代价：-> O(n)
输入：path
执行：

1
select * from table where path like CONCAT($path, '/%')

移动

代价：-> O(n)
输入：path, new_path
执行：

1
2
3
pre: 
old_path和new_path
UPDATE # 执行上面的改操作

总结

可以和邻接表同时使用
优点 : 增加、查询、修改方便
缺点 : 需要大量用到正则、模糊匹配；需要控制层级深度(致命)
适用 : 对层级深度有一定限制，并且需求对所有子集进行操作的场景