树形结构数据存储方案（三）：闭包表

2017 年 9 月 1 日 数据库开发

（点击上方公众号，可快速关注）

来源：标点符

www.biaodianfu.com/closure-table.html

如有好文章投稿，请点击 → 这里了解详情

将Closure Table翻译成闭包表不知道是否合适，闭包表的思路和物化路径差不多，都是空间换时间，Closure Table，一种更为彻底的全路径结构，分别记录路径上相关结点的全展开形式。能明晰任意两结点关系而无须多余查询，级联删除和结点移动也很方便。但是它的存储开销会大一些，除了表示结点的Meta信息，还需要一张专用的关系表。

以下图举例数据举例：

创建主表：

CREATE TABLE nodeInfo (

node_id INT NOT NULL AUTO_INCREMENT,

node_name VARCHAR (255),

PRIMARY KEY (`node_id`)

) DEFAULT CHARSET = utf8;

创建关系表：

CREATE TABLE nodeRelationship (

ancestor INT NOT NULL,

descendant INT NOT NULL,

distance INT NOT NULL,

PRIMARY KEY (ancestor, descendant)

) DEFAULT CHARSET = utf8;

其中

Ancestor代表祖先节点
Descendant代表后代节点
Distance 祖先距离后代的距离

添加数据（创建存储过程）

CREATE DEFINER = `root`@`localhost` PROCEDURE `AddNode`(`_parent_name` varchar(255),`_node_name` varchar(255))

BEGIN

DECLARE _ancestor INT;

DECLARE _descendant INT;

DECLARE _parent INT;

IF NOT EXISTS(SELECT node_id From nodeinfo WHERE node_name = _node_name)

THEN

INSERT INTO nodeinfo (node_name) VALUES(_node_name);

SET _descendant = (SELECT node_id FROM nodeinfo WHERE node_name = _node_name);

INSERT INTO noderelationship (ancestor,descendant,distance) VALUES(_descendant,_descendant,0);

IF EXISTS (SELECT node_id FROM nodeinfo WHERE node_name = _parent_name)

THEN

SET _parent = (SELECT node_id FROM nodeinfo WHERE node_name = _parent_name);

INSERT INTO noderelationship (ancestor,descendant,distance) SELECT ancestor,_descendant,distance+1 from noderelationship where descendant = _parent;

END IF;

END IF;

END;

完成后2张表的数据大致是这样的：（注意：每个节点都有一条到其本身的记录。）

查询Fruit下所有的子节点：

SELECT

n3.node_name

FROM

nodeinfo n1

INNER JOIN noderelationship n2 ON n1.node_id = n2.ancestor

INNER JOIN nodeinfo n3 ON n2.descendant = n3.node_id

WHERE

n1.node_name = 'Fruit'

AND n2.distance != 0

查询Fruit下直属子节点：

SELECT

n3.node_name

FROM

nodeinfo n1

INNER JOIN noderelationship n2 ON n1.node_id = n2.ancestor

INNER JOIN nodeinfo n3 ON n2.descendant = n3.node_id

WHERE

n1.node_name = 'Fruit'

AND n2.distance = 1

查询Fruit所处的层级：

SELECT

n2.*, n3.node_name

FROM

nodeinfo n1

INNER JOIN noderelationship n2 ON n1.node_id = n2.descendant

INNER JOIN nodeinfo n3 ON n2.ancestor = n3.node_id

WHERE

n1.node_name = 'Fruit'

ORDER BY

n2.distance DESC