Closure Table-多级关系设计

在系统设计中 , 总会碰到上下级的概念 . 不同场景中 , 层级关系可能会比较复杂 , 这个时候 , 如何设计就非常重要了

场景介绍

很多系统都会给用户设计一个层级的关系 , 邀请或者代理即可享受下级带来的红利 , 以达到运营产生裂变的效果 .

这里简单说下常用的数据库设计

方案一: 直接记录父级
id name parent
1 Arthas 0
2 Bill 1
3 Catherine 2
4 Damon 3
5 Finn 3
6 Grabby 3

优点 :

  • 可以很方便地找到用户的上级
  • 可以很方便地找到用户的一层下级

缺点:

  • 查找多层上下级很难处理

方案二: 记录路径
id name Path
1 Arthas 0
2 Bill 0-1
3 Catherine 0-1-2
4 Damon 0-1-2-3
5 Finn 0-1-2-3
6 Grabby 0-1-2-3

总结:

这种设计比较常用 , 但在查询多层时还是比较麻烦

方案三: CLOSURE TABLE

常规的用户表

id name parent
1 Arthas 0
2 Bill 1
3 Catherine 2
4 Damon 3
5 Finn 3
6 Grabby 3

关系表 category_tree

ancestor descendant distance
1 1 0
1 2 1
2 2 0
1 3 2
2 3 1
3 3 0
1 4 3
2 4 2
3 4 1
4 4 0
1 5 3
2 5 2
3 5 1
5 5 0
1 6 3
2 6 2
3 6 1
6 6 0
  • ancestor 祖先: 上级的id
  • descendant 子代: 下级的id
  • distance 距离: 子代到祖先中间隔了几级

这三个字段的组合是唯一的 . 因为在树中 , 一条路径可以标识一个节点 , 所以可以直接把它们组合作为主键 . 以表为例 ,节点 6 到它的上级节点 3 的距离为1 在数据库中存储为 ancestor=3,descentant=6,distance=1 到上两级的节点 2 的距离为 2 于是有 ancestor=2,descentant=6,distance=2 .

对于这样的树结构常用的查询都能够很方便的处理 .

相关用法

1. 子节点查询
1
2
3
4
5
# 查询id为5的节点的直属子节点:
SELECT descendant FROM category_tree WHERE ancestor=5 AND distance=1

# 查询所有子节点:
SELECT descendant FROM category_tree WHERE ancestor=5 AND distance>0

查询某个上级节点的子节点,换句话说就是查询具有指定上级节点的节点,也就是ancestor字段等于上级节点id即可,第二个距离distance决定了查询的对象是由上级往下那一层的,等于1就是往下一层(直属子节点),大于0就是所有子节点。这两个查询都是一句完成。

2. 路径查询
1
2
3
4
5
6
7
# 查询由根节点到id为10的节点之间的所有节点,按照层级由小到大排序
SELECT ancestor FROM category_tree WHERE descendant=10 ORDER BY distance DESC

# 查询id10的节点(含)到id3的节点(不含)之间的所有节点,按照层级由小到大排序
SELECT ancestor FROM category_tree WHERE descendant=10 AND
distance<(SELECT distance FROM category_tree WHERE descendant=10 AND ancestor=3)
ORDER BY distance DESC

查询路径,只需要知道descendant即可,因为descendant字段所在的行就是记录这个节点与其上级节点的关系。如果要过滤掉一些则可以限制distance的值。

3. 查询节点所在的层级(深度)
1
2
3
4
5
# 查询id为5的节点是第几级的
SELECT distance FROM category_tree WHERE descendant=5 AND ancestor=0

# 查询id5的节点是id10的节点往下第几级
SELECT distance FROM category_tree WHERE descendant=5 AND ancestor=10

查询层级(深度)非常简单,因为distance字段就是。直接以上下级的节点id为条件,查询距离即可。

4. 查询某一层所有节点
1
2
# 查询所有第三层的节点
SELECT descendant FROM category_tree WHERE ancestor=0 AND distance=3
5. 插入

插入和移动就不是那么方便了,当一个节点插入到某个父节点下方时,它将具有与父节点相似的路径,然后再加上一个自身连接即可。

所以插入操作需要两条语句,第一条复制父节点的所有记录,并把这些记录的distance加一,因为子节点到每个上级节点的距离都比它的父节点多一。当然descendant也要改成自己的。

1
2
3
4
5
# 例如把id为10的节点插入到id为5的节点下方(这里用了Mysql的方言)
INSERT INTO category_tree(ancestor,descendant,distance) (SELECT ancestor,10,distance+1 FROM category_tree WHERE descendant=5)

# 然后就是加入自身连接的记录。
INSERT INTO category_tree(ancestor,descendant,distance) VALUES(10,10,0)
6. 删除
1
2
# 删除
DELETE FROM category_tree WHERE descendant = 6 AND distance != 0

参考链接

0%