数据存储方案-左右值编码-阿里云开发者社区

数据存储方案-左右值编码

2017-10-25 1164

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 在基于数据库的一般应用中，查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数据。优点是查询非常的方便，缺点就是每次插入删除数据涉及到的更新内容太多，如果树非常大，插入一条数据可能花很长的时间。

在基于数据库的一般应用中，查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案，来保存该树的数据。优点是查询非常的方便，缺点就是每次插入删除数据涉及到的更新内容太多，如果树非常大，插入一条数据可能花很长的时间。

但当你用手指指着表中的数字从1数到18，你手指移动的顺序就是对这棵树进行前序遍历的顺序。

如下图所示。当我们从根节点Food左侧开始，标记为1，并沿前序遍历的方向，依次在遍历的路径上标注数字，最后我们回到了根节点Food，并在右边写上了18。

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

如何初始化数据？

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;

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;

如需在末尾追加就需要以下方式进行（以在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;

在节点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;

插入非末端节点,流程分为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 , @Left := lft , @Right := 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 = @Left + lft - @myLeft + 1, rgt = @Left + 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 @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;

如何查询？

1、获取某个节点下的所有子孙节点，以Fruit为例： 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

4、获取当前节点所在路径，以Fruit为例：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 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

6、获取所有直属子节点，以Fruit为例：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

8、返回所有叶子节点 SELECT * FROM Tree WHERE Rgt = Lft + 1

数据存储方案-左右值编码

如何初始化数据？

如何查询？

热门文章

最新文章

相关电子书