Closure Table无限极目录树关系设计详解

流氓凡 技术分享 2021-04-01 1.43 K 0

ClosureTable是以一张表存储节点之间的关系、其中包含了任何两个有关系(上下级)节点的关联信息。因此可以很方便的进行查询、插入、删除、移动节点及对应的子节点。

而且,还有好心人直接放出扩展包基于(ThinkPHP和Laravel框架) https://github.com/jiaxincui/closure-table 只需按照他说明的表设计即可。

如果,还有时间和想法可以研究下 neo4j 这个库,它可以更加方便的存储树结构。

ClosureTable演示结构图表示:

image.png

其中定义的关系表字段仅需三个字段就完全满足需求:

字段值类型说明
ancestorint(11)0祖先:上级节点的id
descendantint(11)0子代:下级节点的id (也包括自己)
distanceint(11)0距离:子代到祖先中间隔了几级

在实际插入数据的过程中,其实不仅仅插入了一条,而是包含所有上级节点信息的多条。

这三个字段的组合是唯一的,因为在树中,一条路径可以标识一个节点,所以可以直接把它们的组合作为主键。以图为例,节点6到它上一级的节点(节点4)距离为1在数据库中存储为ancestor=4,descendant=6,distance=1,到上两级的节点(节点1)距离为2,于是有ancestor=1,descendant=6,distance=2,到根节点的距离为3也是如此,最后还要包含一个到自己的连接,当然距离就是0了。

这样一来,不尽表中包含了所有的路径信息,还在带上了路径中每个节点的位置(距离),对于树结构常用的查询都能够很方便的处理。下面看看如何用用它来实现我们的需求。

子节点查询:

查询id为5的节点的直属子节点:

SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance=1

查询所有子节点:

SELECT descendant FROM CategoryTree WHERE ancestor=5 AND distance>0

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

大于0就是所有子节点。这两个查询都是一句完成。

路径查询

查询由根节点到id为10的节点之间的所有节点,按照层级由小到大排序

SELECT ancestor FROM CategoryTree WHERE descendant=10 ORDER BY distance DESC

查询id为10的节点(含)到id为3的节点(不含)之间的所有节点,按照层级由小到大排序

SELECT ancestor FROM CategoryTree WHERE descendant=10 AND 

distance<(SELECT distance FROM CategoryTree WHERE descendant=10 AND ancestor=3) 

ORDER BY distance DESC

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

查询节点所在的层级(深度)

查询id为5的节点是第几级的

SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=0

查询id为5的节点是id为10的节点往下第几级

SELECT distance FROM CategoryTree WHERE descendant=5 AND ancestor=10

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

查询某一层的所有节点

查询所有第三层的节点

SELECT descendant FROM CategoryTree WHERE ancestor=0 AND distance=3

插入节点

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

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

例如把id为10的节点插入到id为5的节点下方(这里用了Mysql的方言)

INSERT INTO CategoryTree(ancestor,descendant,distance) (SELECT ancestor,10,distance+1 FROM CategoryTree WHERE descendant=5)

然后就是加入自身连接的记录。

INSERT INTO CategoryTree(ancestor,descendant,distance) VALUES(10,10,0)

移动节点

节点的移动没有很好的解决方法,因为新位置所在的深度、路径都可能不一样,这就导致移动操作不是仅靠UPDATE语句能完成的,这里选择删除+插入实现移动。

另外,在有子树的情况下,上级节点的移动还将导致下级节点的路径改变,所以移动上级节点之后还需要修复下级节点的记录,这就需要递归所有下级节点。

删除id=5节点的所有记录

DELETE FROM CategoryTree WHERE descendant=5

然后配合上面一节的插入操作实现移动。

如何设计三三矩阵分销落点实现后续更根据此篇更新基于php的一个示例demo。


评论