树形结构数据存储方案（四）：左右值编码

栏目: 数据库 · 发布时间: 6年前

内容简介：在基于数据库的一般应用中，查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数据。

在基于数据库的一般应用中，查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数据。

树形结构数据存储方案（四）：左右值编码

第一次看见这种表结构，相信大部分人都不清楚左值（Lft）和右值（Rgt）是如何计算出来的，而且这种表设计似乎并没有保存父子节点的继承关系。但当你用手指指着表中的数字从1数到18，你应该会发现点什么吧。对，你手指移动的顺序就是对这棵树进行前序遍历的顺序，如下图所示。当我们从根节点Food左侧开始，标记为1，并沿前序遍历的方向，依次在遍历的路径上标注数字，最后我们回到了根节点Food，并在右边写上了18。

树形结构数据存储方案（四）：左右值编码

依据此设计，我们可以推断出所有左值大于2，并且右值小于11的节点都是Fruit的后续节点，整棵树的结构通过左值和右值存储了下来。然而，这还不够，我们的目的是能够对树进行CRUD操作，即需要构造出与之配套的相关算法。按照深度优先，由左到右的原则遍历整个树，从1开始给每个节点标注上left值和right值，并将这两个值存入对应的name之中。

如何查询？

1、获取某个节点下的所有子孙节点，以Fruit为例：

SELECT * FROM Tree WHERE Lft > 2 AND Lft < 11 ORDER BY Lft ASC

1	SELECT * FROM Tree WHERE Lft > 2 AND Lft < 11 ORDER BY Lft ASC

2、获取子孙节点总数

子孙总数 = (右值–左值–1)/2，以Fruit为例，其子孙总数为：(11–2–1)/2 = 4

3、获取节点在树中所处的层数，以Fruit为例：

SELECT COUNT(*) FROM Tree WHERE Lft <= 2 AND Rgt >=11

1	SELECT COUNT(*) FROM Tree WHERE Lft <= 2 AND Rgt >=11

4、获取当前节点所在路径，以Fruit为例：

SELECT * FROM Tree WHERE Lft <= 2 AND Rgt >=11 ORDER BY Lft ASC

1	SELECT * FROM Tree WHERE Lft <= 2 AND Rgt >=11 ORDER BY Lft ASC

在日常的处理中我们经常还会遇到的需要获取某一个节点的直属上级、同级、直属下级。为了更好的描述层级关系，我们可以为Tree建立一个视图，添加一个层次列，该列数值可以编写一个自定义函数来计算：

CREATE FUNCTION `CountLayer`(`_node_id` int)
 RETURNS int(11)
BEGIN
	DECLARE _result INT;
	DECLARE _lft INT;
	DECLARE _rgt INT;
	IF EXISTS(SELECT Node_id FROM Tree WHERE Node_id = _node_id)
	THEN
		SELECT Lft,Rgt FROM Tree WHERE Node_id = _node_id INTO _lft,_rgt;
		SET _result = (SELECT COUNT(1) FROM Tree WHERE Lft <= _lft AND Rgt >= _rgt);	
		RETURN _result;
	ELSE
		RETURN 0;
	END IF;
END;

CREATE FUNCTION `CountLayer`(`_node_id` int)

RETURNS int(11)

BEGIN

DECLARE _result INT;

DECLARE _lft INT;

DECLARE _rgt INT;

IF EXISTS(SELECT Node_id FROM Tree WHERE Node_id = _node_id)

THEN

SELECT Lft,Rgt FROM Tree WHERE Node_id = _node_id INTO _lft,_rgt;

SET _result = (SELECT COUNT(1) FROM Tree WHERE Lft <= _lft AND Rgt >= _rgt);

RETURN _result;

ELSE

RETURN 0;

END IF;

END;

在添加完函数以后，我们创建一个a视图，添加新的层次列：

CREATE VIEW `NewView`AS 
SELECT Node_id, Name, Lft, Rgt, CountLayer(Node_id) AS Layer FROM Tree ORDER BY Lft ;

1 2	CREATE VIEW `NewView`AS SELECT Node_id, Name, Lft, Rgt, CountLayer(Node_id) AS Layer FROM Tree ORDER BY Lft ;

5、获取当前节点父节点,以Fruit为例：

SELECT * FROM treeview WHERE Lft <= 2 AND Rgt >=11 AND Layer=1

1	SELECT * FROM treeview WHERE Lft <= 2 AND Rgt >=11 AND Layer=1

6、获取所有直属子节点，以Fruit为例：

SELECT * FROM treeview WHERE Lft BETWEEN 2 AND 11 AND Layer=3

1	SELECT * FROM treeview WHERE Lft BETWEEN 2 AND 11 AND Layer=3

7、获取所有兄弟节点，以Fruit为例：

SELECT * FROM treeview WHERE Rgt > 11 AND Rgt < (SELECT Rgt FROM treeview WHERE Lft <= 2 AND Rgt >=11 AND Layer=1) AND Layer=2

1	SELECT * FROM treeview WHERE Rgt > 11 AND Rgt < (SELECT Rgt FROM treeview WHERE Lft <= 2 AND Rgt >=11 AND Layer=1) AND Layer=2

8、返回所有叶子节点

SELECT * FROM Tree WHERE Rgt = Lft + 1

1	SELECT * FROM Tree WHERE Rgt = Lft + 1

如何创建树？如何新增数据？

上面已经介绍了如何检索结果，那么如何才能增加新的节点呢？Nested set 最重要是一定要有一个根节点作为所有节点的起点，而且通常这个节点是不被使用的。为了便于控制查询级别，在建表的时候建议添加parent_id配合之联结列表方式一起使用。

CREATE TABLE IF NOT EXISTS `Tree` (
  `node_id` int(11) NOT NULL AUTO_INCREMENT,
  `parent_id` int(10) UNSIGNED NOT NULL DEFAULT '0',
  `name` varchar(255) NOT NULL,
  `lft` int(11) NOT NULL DEFAULT '0',
  `rgt` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY (`node_id`),
  KEY `idx_left_right` (`lft`,`rgt`)
) DEFAULT CHARSET=utf8;

CREATE TABLE IF NOT EXISTS `Tree` (

`node_id` int(11) NOT NULL AUTO_INCREMENT,

`parent_id` int(10) UNSIGNED NOT NULL DEFAULT '0',

`name` varchar(255) NOT NULL,

`lft` int(11) NOT NULL DEFAULT '0',

`rgt` int(11) NOT NULL DEFAULT '0',

PRIMARY KEY (`node_id`),

KEY `idx_left_right` (`lft`,`rgt`)

) DEFAULT CHARSET=utf8;

INSERT INTO `Tree` (parent_id,name,lft,rgt) VALUES ( 0,'Food',1,2)

1	INSERT INTO `Tree` (parent_id,name,lft,rgt) VALUES ( 0,'Food',1,2)

添加子节点（子节点起始处），以在Food下添加子节点Fruit为例：

LOCK TABLE Tree WRITE;
SELECT @parent_id := node_id, @myLeft := lft FROM Tree WHERE name = 'Food';
UPDATE Tree SET rgt = rgt + 2 WHERE rgt > @myLeft;
UPDATE Tree SET lft = lft + 2 WHERE lft > @myLeft;
INSERT INTO Tree(parent_id, name, lft, rgt) VALUES(@parent_id, 'Fruit', @myLeft + 1, @myLeft + 2);
UNLOCK TABLES;

LOCK TABLE Tree WRITE;

SELECT @parent_id := node_id, @myLeft := lft FROM Tree WHERE name = 'Food';

UPDATE Tree SET rgt = rgt + 2 WHERE rgt > @myLeft;

UPDATE Tree SET lft = lft + 2 WHERE lft > @myLeft;

INSERT INTO Tree(parent_id, name, lft, rgt) VALUES(@parent_id, 'Fruit', @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;

如需在末尾追加就需要以下方式进行（以在Red下添加Apple为例）：

LOCK TABLE Tree WRITE;
SELECT @parent_id := node_id , @myRight := rgt FROM Tree WHERE name = 'Red';
UPDATE Tree SET rgt = rgt + 2 WHERE rgt >= @myRight;
UPDATE Tree SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO Tree(parent_id, name, lft, rgt) VALUES(@parent_id, 'Apple', @myRight, @myRight + 1);
UNLOCK TABLES;

LOCK TABLE Tree WRITE;

SELECT @parent_id := node_id , @myRight := rgt FROM Tree WHERE name = 'Red';

UPDATE Tree SET rgt = rgt + 2 WHERE rgt >= @myRight;

UPDATE Tree SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO Tree(parent_id, name, lft, rgt) VALUES(@parent_id, 'Apple', @myRight, @myRight + 1);

UNLOCK TABLES;

在节点A后面添加同级节点（以在Yellow后面添加Green为例）

LOCK TABLE Tree WRITE;
SELECT @parent_id := parent_id , @myRight := rgt FROM Tree WHERE name = 'Yellow';
UPDATE Tree SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE Tree SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO Tree(parent_id, name, lft, rgt) VALUES(@parent_id, 'Green', @myRight+1, @myRight+2);
UNLOCK TABLES;

LOCK TABLE Tree WRITE;

SELECT @parent_id := parent_id , @myRight := rgt FROM Tree WHERE name = 'Yellow';

UPDATE Tree SET rgt = rgt + 2 WHERE rgt > @myRight;

UPDATE Tree SET lft = lft + 2 WHERE lft > @myRight;

INSERT INTO Tree(parent_id, name, lft, rgt) VALUES(@parent_id, 'Green', @myRight+1, @myRight+2);

UNLOCK TABLES;

以上讨论的添加节点指的都是添加末端节点，即插入的这个节点不是当前已存在节点的父节点。如果需要插入非末端节点要怎么办呢？

这个过程可以将流程分为2步，首先新增节点，接下里再将需要的节点移到新增的节点下级。节点移动方法(以将Apple移到Yellow中为例)：

LOCK TABLE Tree WRITE;
SELECT @nodeId := node_id , @myLeft := lft , @myRight := rgt FROM Tree WHERE name = 'Apple';
UPDATE Tree SET lft = lft - (@myRight - @myLeft) - 1 WHERE lft > @myRight;
UPDATE Tree SET rgt = rgt - (@myRight - @myLeft) - 1 WHERE rgt > @myRight;
SELECT @parent_id := node_id , <a rel="nofollow" href="http://www.jobbole.com/members/wx1863158684">@Left</a> := lft , <a rel="nofollow" href="http://www.jobbole.com/members/wx3757768826">@Right</a> := rgt FROM Tree WHERE name = 'Yellow';
UPDATE Tree SET lft = lft + (@myRight - @myLeft) + 1 WHERE lft > @Left;
UPDATE Tree SET rgt = rgt + (@myRight - @myLeft) + 1 WHERE lft > @Left;
UPDATE Tree SET parent_id = @parent_id WHERE name = node_id = @nodeId;
UPDATE Tree SET lft = <a rel="nofollow" href="http://www.jobbole.com/members/wx1863158684">@Left</a> + lft - @myLeft + 1, rgt = <a rel="nofollow" href="http://www.jobbole.com/members/wx1863158684">@Left</a> + lft - @myLeft + 1  + (@myRight - @myLeft) WHERE lft >= @myLeft AND rgt <= @myRight;
UNLOCK TABLES;

LOCK TABLE Tree WRITE;

SELECT @nodeId := node_id , @myLeft := lft , @myRight := rgt FROM Tree WHERE name = 'Apple';

UPDATE Tree SET lft = lft - (@myRight - @myLeft) - 1 WHERE lft > @myRight;

UPDATE Tree SET rgt = rgt - (@myRight - @myLeft) - 1 WHERE rgt > @myRight;

SELECT @parent_id := node_id , <a href="http://www.jobbole.com/members/wx1863158684">@Left</a> := lft , <a href="http://www.jobbole.com/members/wx3757768826">@Right</a> := rgt FROM Tree WHERE name = 'Yellow';

UPDATE Tree SET lft = lft + (@myRight - @myLeft) + 1 WHERE lft > @Left;

UPDATE Tree SET rgt = rgt + (@myRight - @myLeft) + 1 WHERE lft > @Left;

UPDATE Tree SET parent_id = @parent_id WHERE name = node_id = @nodeId;

UPDATE Tree SET lft = <a href="http://www.jobbole.com/members/wx1863158684">@Left</a> + lft - @myLeft + 1, rgt = <a href="http://www.jobbole.com/members/wx1863158684">@Left</a> + lft - @myLeft + 1 + (@myRight - @myLeft) WHERE lft >= @myLeft AND rgt <= @myRight;

UNLOCK TABLES;

删除节点（包含子节点）

LOCK TABLE Tree WRITE;
SELECT @myLeft := lft , @myRight := rgt FROM Tree WHERE name = 'Apple';
DELETE Tree WHERE lft >= @myLeft AND rgt <= @myRight;
UPDATE Tree SET lft = lft - (@myRight - @myLeft) - 1 WHERE lft > @myRight;
UPDATE Tree SET rgt = rgt - (@myRight - @myLeft) - 1 WHERE rgt > @myRight;
UNLOCK TABLES;

LOCK TABLE Tree WRITE;

SELECT @myLeft := lft , @myRight := rgt FROM Tree WHERE name = 'Apple';

DELETE Tree WHERE lft >= @myLeft AND rgt <= @myRight;

UPDATE Tree SET lft = lft - (@myRight - @myLeft) - 1 WHERE lft > @myRight;

UPDATE Tree SET rgt = rgt - (@myRight - @myLeft) - 1 WHERE rgt > @myRight;

UNLOCK TABLES;

如果需要只删除该节点，子节点自动上移一级如何处理？

LOCK TABLE Tree WRITE;
SELECT @parent_id := parent_id , @node_id :=node_id , @myLeft := lft , @myRight := rgt FROM Tree WHERE name = 'Red';
UPDATE Tree SET parent_id = @parent_id WHERE  parent_id = @node_id
DELETE Tree WHERE lft = @myLeft;
UPDATE Tree SET lft = lft - 1,rgt = rgt-1 Where lft > @myLeft AND @rgt < @myRight
UPDATE Tree SET lft = lft - 2,rgt = rgt-2 Where lft > @rgt > @myRight
UNLOCK TABLES;

LOCK TABLE Tree WRITE;

SELECT @parent_id := parent_id , @node_id :=node_id , @myLeft := lft , @myRight := rgt FROM Tree WHERE name = 'Red';

UPDATE Tree SET parent_id = @parent_id WHERE parent_id = @node_id

DELETE Tree WHERE lft = @myLeft;

UPDATE Tree SET lft = lft - 1,rgt = rgt-1 Where lft > @myLeft AND @rgt < @myRight

UPDATE Tree SET lft = lft - 2,rgt = rgt-2 Where lft > @rgt > @myRight

UNLOCK TABLES;

以上为Nested Set的CURD操作，具体在使用时建议结合事务和存储过程一起使用。本方案的优点时查询非常的方便，缺点就是每次插入删除数据涉及到的更新内容太多，如果树非常大，插入一条数据可能花很长的时间。

参考链接：

原文出处：标点符

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Open Data Structures

Pat Morin / AU Press / 2013-6 / USD 29.66

Offered as an introduction to the field of data structures and algorithms, Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues......一起来看看《Open Data Structures》这本书的介绍吧!

码农工具

树形结构数据存储方案（四）：左右值编码

Open Data Structures

JSON 在线解析

XML、JSON 在线转换

RGB HSV 转换