Storing Hierarchical data by 【Closure Table】

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

常见场景

  1. 公司:公司 - 部门 - 子部门
  2. 人员:领导 - 员工
  3. 文件:根目录 - 文件夹 - 文件
  4. 关系:group - child

实例

转成树型

Closure Table

维护一个表,所有的tree path作为记录进行保存。

idname
1DIR_A
2DIR_B
3DIR_C
4file_x
5file_y
6file_z
7DIR_E
8file_o
9file_p
10DIR_D
11file_m
12file_n
13file_l
14file_j
15file_k
current_idancestor_iddistance
211
712
721
1313
1322
1371

各种情况的处理代价

代价:-> O(n) 如果层级非常深,代价 -> ∞
输入:name, parent_id
执行:添加到 DIR_D 下

1
2
3
4
5
6
7
8
9
insert into node(name) values($name);
## 查所有父节点,建立关系
ids[] = {$parent_id}
ids[] += select id from node where current_id=$parent_id; 
distance = ids.length;
for (ancestor_id : ids) {
    insert into relation(current_id, ancestor_id, distance) values ($id, $ancestor_id, $distance);
    distance--;
}
idname
13file_l
14file_j
15file_k
16(add)file_ADD
current_idancestor_iddistance
1614
1633
16102
16131

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

1
2
3
4
ids[] = {$id}
ids += $(select id from relation where ancestor_id = ${id})
delete from relation where ancestor_id in ${ids} or current_id in ${ids}
delete from node where id in ${ids}

代价:-> O(1)
输入:id, other info
执行:

1
update node set info where id = $id

查自己

代价:-> O(1)
输入:id
执行:

1
select * from node where id = $id
查下一级

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

1
2
3
select * from relation
left join node on node.id = relation.current_id
where relation.ancestor_id = $id and distance = 1
查所有子集

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

1
2
3
select * from relation
left join node on node.id = relation.current_id
where relation.ancestor_id = $id

移动

代价:-> O(n) 输入:id, new_parent_id 执行:

1
2
3
4
5
6
7
8
old_parent_id = select ancestor_id from relation where current_id = $id and distance = 1;
DEL # 执行上面的删除操作

objects = ${object(id)}
objects += $(select current_id, distance from relation where ancestor = $id)
for (object : $objects) {
    INSERT  # 执行上面的插入操作
}

总结

优点 : 修改、查询简便,效率高;
缺点 : 空间换时间;进行删除、移动代价较大;层级深度很大的时候空间消耗巨大
适用 : 有固定的层级深度,并且层级不多的场景

comments powered by Disqus