在基于数据库的一般应用中,查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程,基于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