层级数据设计及存储

Qter

在数据库中存储层次数据
http://www.360doc.com/content/05/1215/11/3500_44502.shtml
https://blog.csdn.net/SunnyYoona/article/details/84603823
邻接列表模型（“递归方法”）的缺点在哪里呢？在大多数编程语言中，他运行很慢，效率很差。这主要是“递归”造成的。

改进前序遍历树
现在，让我们看另一种存储树的方法。递归可能会很慢，所以我们就尽量不使用递归函数。我们也想尽量减少数据库查询的次数。最好是每次只需要查询一次。

Qter

2019-07-15 数据库无限层级分类设计
https://cloud.tencent.com/developer/article/1464513


起步

在大多数的系统中，对内容进行分类是必要的。比如电商的商品分类；论坛的板块等。

需求分析

分类之间的关系是怎样的？ 很明显，一个分类下面可以是多个下级分类。反过来呢，一个下级分类能够属于几个上级分类呢？这个并不确定，得看具体的业务需求。如果是多个实现上会更加复杂，为了讨论层级设计，这里先限定每个分类仅有一个上级分类。

对于某个分类，需要支持的操作如下：

• 对单个分类的 CURD；
• 查询该分类的直属下级或所有下级分类；
• 查询该分类的上级分类至顶级分类中的所有分类，并且是有序的；
• 移动该分类，就是将节点移动到另一个节点下面，这是当分类结构不合理时，允许修改时使用；
• 查询某一级的所有分类（很少会用到）。
  

从使用频率来看，查询是大多数，毕竟分类也不会改来改去。所以性能考虑以查询操作优先，特别是操作2 和操作 3。

方案一：记录父分类的引用

这是一种比较常见且维护的一个方案，添加一个 pid 指向父分类的 id ：

20190523135518.png

表中 pid 即直属上级分类的 id，顶级分类设为 0.这种方案简单易懂，仅用一个字典，没有冗余信息，存储空间占用极小，在数据库层面是一个很好的设计。（本博客系统的分类就是采用这种结构）

对于分类的移动也非常友好，只要修改 pid 即可。而删除分类也只需将其直属子分类的 pid 改成该分类的 pid即可。但对于查询该分类的所有上级至顶级分类或查询就不友好了，需要进行递归。

查找所有父分类至顶级分类

SELECT    ID.LEVEL,    t.*FROM    (        SELECT            @id AS _id,            ( SELECT @id := pid FROM lab_goods WHERE id = @id) AS _pid,            @l := @l + 1 AS LEVEL        FROM            lab_goods,            (SELECT @id := 100, @l := 0) as b        WHERE            @id > 0    ) as ID,    lab_goods as tWHERE    ID._id = t.idORDER BY `LEVEL`;

经实验该语句可用，但当表中数据有一万条，当查询的层级有1000时，耗时 2 秒。也就是当分类的数量很多的时候，这个方案的性能并不好，但真实业务上会有这么多的分类吗？

查询某分类的所有下级分类为：

SELECT    ID. LEVEL,    DATA .*FROM    (        SELECT            @ids AS _ids,            (                SELECT @ids := GROUP_CONCAT(id) FROM lab_goods WHERE FIND_IN_SET(pid, @ids)            ) AS cids,            @l := @l + 1 AS LEVEL        FROM            lab_goods,            (SELECT @ids := 10000, @l := 0) b        WHERE            @ids IS NOT NULL    ) id,    lab_goods DATAWHERE    FIND_IN_SET(DATA .id, ID._ids)ORDER BY `LEVEL`, id

当层级太多的时候性能是不佳的。而对于查询某一级的所有分类，这个设计简直是灾难。

其实这个方案也是一开始就能想到的，在层级不深的情况下，这个方案不失为一个好的选择。

方案二：添加路径列表

针对方案一的短板，我们表中不仅仅记录父分类id，还将它到顶级分类所有分类的id都保存下来。

id

name

pid

path

1

家用电器

0

-

2

电脑办公

0

-

3

大家电

1

1

4

生活电器

1

1

5

电风扇

4

1,4

6

电脑整机

2

1,2

每个分类都保存从顶级分类到父分类的所有id。查询某某分下的所有下级就可以用 like 进行匹配：

SELECT id,name FROM pathlist WHERE path LIKE '1,%'

查询某个分类的所有下级：

SELECT id,name FROM pathlist WHERE path LIKE '%2'

这个方案在各个方面都具有可以接受的性能，在上述例子中 1w 的数据，1k 的层级，仅耗时 0.0009s 。

但具有两点不足：1. 不遵守数据库范式，DBA看了想打人；2. 就是字段长度是有限的，但 longtext 最大能存储 4G 的文本，我想没有这么变态的层级数。所以这个分类在许多系统中使用。

方案三：基于ClosureTable的无限级分类存储

另建一张表存储节点之间的关系，其中包含了任何两个有关系的节点的关联信息：

2696840886-5acc5fd7a44f3.png

定义关系表 CategoryTree，其包含3个字段：

• ancestor 祖先：上级节点的id
• descendant 子代：下级节点的id
• distance 距离：子代到祖先中间隔了几级
  

这三个字段的组合是唯一的，因为在树中，一条路径可以标识一个节点，所以可以直接把它们的组合作为主键。以图为例，节点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)删除

如果删除分类同时也删除其所有下级分类那好办，先找出该节点所有子级节点逐个删除：

DELETE FROM CategoryTree WHERE descendant in (select descendant from CategoryTree where ancestor=4)...

而如果节点删除后是需要将所有下级分类都划分到该节点的直系上级。比如删除节点4，那么需要把4 的所有子节点都归到该节点的直接上级：

select descendant from CategoryTree where ancestor=4 // 查询4的所有子节点// 当子节点的父节点中超过该节点到 4节点距离时，距离- 1update CategoryTree set distance = distance-1 where descendant=6 and distance > (select b.distance from (select * from CategoryTree where ancestor=4 and descendant=6 ) b);...DELETE FROM CategoryTree WHERE ancestor=4 // 待下级节点的距离都修复完毕后删除节点与下级节点的联系DELETE FROM CategoryTree WHERE descendant=4 // 删除4节点本身移动

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

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

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

DELETE FROM CategoryTree WHERE descendant=5

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

总结

ClosureTable是一种比较完美的解决方案，对于无限分层有很好的适应性，比较适用于大型系统。