聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

树形结构数据存储方案(三):闭包表

2016-07-17 14:45 浏览: 1673615 次 我要评论(0 条) 字号:

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

以下图举例数据举例:

tree

创建主表:

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张表的数据大致是这样的:(注意:每个节点都有一条到其本身的记录。)

Closure-Table-1

Closure-Table-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

另外要删除节点也非常的简单,这里就不再做过多的阐述。

参考链接:

  • https://coderwall.com/p/lixing/closure-tables-for-browsing-trees-in-sql


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复