闭包表

  1. 1. 闭包表
    1. 1.1. 闭包

闭包表

在数据库中存储树的方式

本文代码中的数据库中表的创建省略部分信息

设想,比如你正在搭建一个网站,它有一个评论功能。用户可以相互评论乃至相互回复。则评论的结构,毫无疑问,会是一棵树。同时,这棵树必然会在某些时候存在极大的深度。

此时,就必须用一种高效的方式,用于存储可能拥有极大深度的树。且便于快速的查找、删除某一子树。

此处,我们采用闭包表的方式。

一言以蔽之,闭包表是一种以空间换时间的存储方式,且删除通常采用类似懒惰删除的方式。

闭包

首先,我们简要介绍下几个概念。

  • 有向图

粗略来说,图就是由结点和边组成的有序二元组。如下图:

graph TB;
A((A1)) --- A2((A2));
A((A1)) --- A3((A2));

而有向图,顾名思义,由两结点构成的边为一有序对偶,即非\(A1\)\(A2\)双向可达,而是只能由\(A1\)\(A2\)

graph TB;
A((A1)) --> A2((A2));
A((A1)) --> A3((A2));
  • 传递性

若存在某关系\(R\),若\(a \ R \ b, b\ R \ c, 则 a \ R \ c\)

  • 闭包

数学中,若对某个集合的成员进行一种运算,生成的仍然是这个集合的成员,则该集合被称为在这个运算下闭合。当一个集合 S 在某个运算下不闭合的时候,我们通常可以找到包含 S 的最小的闭合集合。这个最小闭合集合被称为 S 的(关于这个运算的)闭包

以上描述摘自维基百科


概念介绍完毕,可能有些难懂,但是接下来我们结合闭包表这一实例,就比较好理解了。

考虑评论的结构:

CommentTree

则我们可以将评论抽象为一棵有向树(有向图的一种特殊情况)

取两结点间的父子关系为\(R\)。此时我们构建这个关系\(R\)的闭包。即文章评论1是直接的父子关系,评论1评论1的评论是直接的父子关系。则在构造出的闭包中,文章评论1的评论也应该是直接的父子关系。

同时,便于查找操作,我们在此关系中加入自环(即指向自己)

那么这张树此时的形态如下:

commentTreePaths

明白了如何去构造一个闭包,接下来的存储就变得比较容易。

正如本文开始说的那样,闭包表的存储是用空间换时间。它实际上的存储是单独开了一张表用于存储结点间的关系。

1
2
3
4
5
6
7
8
9
10
CREATE TABLE Comments{
comment_id SERIAL PRIMARY KEY,
comment_content TEXT NOT NULL,
comment_author BIGINT
}

CREATE TABLES CommentTreePaths{
ancestor BIGINT,
descendant BIGINT,
}

Comment表中,我们仅存储评论的具体信息,而在CommentTreePaths表中,我们存储结点的祖先—后代关系。

本例中CommentTreePaths的部分存储内容如下:

ancestor descendant
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 2
2 3

此时对这棵树的增删改查操作就变得比较容易。

  • 增加

比如B评论A

则首先插入B的一条自环关系,而后搜索所有CommentTreePaths表中descendant为A的结点,增加他们与B的一条祖先—后代关系

  • 删除

如删除评论A及其全部子评论

删除CommentTreePaths中所有后代为A的记录,以及那些以A的后代为后代的记录。

此处我们可以看出,所谓的删除并非删除该记录,而是删除所有包涵该记录的边。从而使其离开这棵树。

  • 查找

如获取评论A及其子树

CommentTreePaths中搜索所有祖先是评论A的记录即可

如获取评论A的所有祖先

CommentTreePaths中搜索所有后代是评论A的记录即可


闭包表的实现能够快速的查询给定结点的祖先及其后代,且十分简单的维护分层关系。

参考文献:

  • 《SQL反模式》