突然发现自己以前常用的parent_id ,node_id这种简单直观的树形结构设计效率很低,数据量一大,就需要不停迭代寻找节点,于是这几天学习了新的数据结构(modified preorder tree traversal),在此做下笔记。
此数据结构的好处是查询非常快,当网站查询树形数据比修改多时使用此结构会比较好,一般用于电商网站的商品分类,查询仅仅需要判断left> ? right <?这样即可,缺点是修改节点表数据量大时很慢,而且操作复杂一点。
左右值数据结构网上教程很多,不再赘述,总结一下就是:要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小 。
直接上代码,上面有注释 ,说明了如何找子节点,如何找父节点、删除节点,同级平移,兄弟节点前插入等(基于postgreSQL数据库)。
表字段
CREATE TABLE "public"."t_test" (
"id" int4 NOT NULL DEFAULT nextval('"T_TEST_ID_seq"'::regclass),
"name" varchar(255) COLLATE "pg_catalog"."default",
"l" int4,
"r" int4,
"level" int4,
"other" varchar(255) COLLATE "pg_catalog"."default",
"status" int2 DEFAULT 0,
PRIMARY KEY ("id")
)
;
查询节点SQL
如下,比如点击一个节点要查询下面所有子节点时的查询方法:
--查询节点
--查询节点下全部子孙菜单不包括自身菜单 (查询“根菜单下的所有子节点”),子查询中id=1表示查询该父节点的left值和right值
SELECT * FROM t_test WHERE l > (SELECT l from t_test where id = 1) AND r < (SELECT r from t_test where id = 1);
--查询子孙总数=(右值-左值-1)/2
--查询某一节点的全部父祖节点
SELECT * FROM t_test WHERE l <(SELECT l from t_test where id = 4) AND r > (SELECT r from t_test where id = 4) order by l;
--判断某一节点是否是指定节点的字节点,判断条件是 子节点的Left > 父节点left , 子节点right < 父节点Right
--8 > 3 AND 9 <4 = false
--判断是否是指定节点的父节点同理,子节点的Left < 父节点left , 子节点right > 父节点Right
插入节点
values(里的参数分别是id,节点名称,left值,right值,level节点层级,说明)
第一条SQL插入的是根节点,因此是0
--ROOT 首先插入根节点,values中的1仅仅是自增id,没有其它意义
INSERT INTO T_TEST VALUES(1,'根菜单',1,2,0,'');
然后插入二级节点,节点插入时要重新计算受影响节点的左右值,所以可以看到有两条UPDATE语句
----------------以下是插入二级节点-----------------
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 1;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
--二级菜单,level = 父结点level+1 = 1,ID = PARENT ID +1 = 2
--重点,LEFT和RIGHT变量并不是二叉树的左结点和右结点ID值,仅仅是一个顺序标识,left = parent
---- left,right = parent right +1=3
INSERT INTO T_TEST VALUES(2,'计算机中心',parent_right,parent_right+1,1,
'我是二级菜单');
上面的INSERT语句中左节点为父节点的right值,右节点为父节点的right值+1,由于是二级菜单,因此level值是1
删除节点
以下是删除ID=4下面的所有子节点
--删除节点
--删除ID=4节点下的所有子节点,查出父节点的right值
SELECT l,r INTO parent_left,parent_right from t_test where id = 4;
--LEFT比父节点值大 且right比父节点值小,则表示是它的子节点,删除子节点
delete from t_test where l >=parent_left and r <=parent_right;
--修改受影响节点的值,left > 父节点left right > 父节点right,也就是修改其所有父节点的左右值
update t_test set l=l-(parent_right - parent_left + 1) where l > parent_left;
update t_test set r=r-(parent_right - parent_left + 1) where r > parent_right;
两条UPDATE语句的作用是重新计算受影响的节点值,左右节点的麻烦之处就在这,有一个节点变动,多数节点的左右值都需要重新计算。
移动节点
将id=10的节点移动到id=12的节点下面,使用成为id=12的子节点
--移动节点思路一,同节点平移可以直接交换左右值即可(应使用这个)
--节点同等级后移,id=12是移动到其节点后的目标节点
SELECT l, r into target_left,target_right FROM t_test WHERE id = 12;
--要移动的节点
SELECT l,r into source_left,source_right from t_test where id = 10;
--移动节点
UPDATE T_TEST SET l=target_left,r=target_right WHERE id=10;
UPDATE T_TEST SET l=source_left,r=source_right WHERE id=12;
节点的移动其实就是修改它的左右值
代码合集
以下是代码合集,比较乱,有耐心的可以看
CREATE OR REPLACE FUNCTION "public"."addNode"()
RETURNS "pg_catalog"."void" AS $BODY$
-- Routine body goes here...
DECLARE
--此方法为测试方法,可删除
parent_right integer;
parent_left integer;
--移动节点所用变量
count_level integer;
effect_value integer;
effect_left integer;
effect_right integer;
target_position integer;
--有很多用不上的变量
source_value integer;
source_left integer;
source_right integer;
target_left integer;
target_right integer;
position_temp integer;
source_ids integer;
my_cursor REFCURSOR;
--要移动的节点ID
source_id_v integer;
--移动到目标节点的ID
target_id_v integer;
BEGIN
--clear
delete from t_test;
--ROOT
INSERT INTO T_TEST VALUES(1,'根菜单',1,2,0,'');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 1;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
--二级菜单,level = 父结点level+1 = 1,ID = PARENT ID +1 = 2
--重点,LEFT和RIGHT并不是二叉树的左结点和右结点ID值,仅仅是一个顺序标识,left = parent left,right = parent right +1=3
INSERT INTO T_TEST VALUES(2,'计算机中心',parent_right,parent_right+1,1,
'三级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 2;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
INSERT INTO T_TEST VALUES(3,'设备管理',parent_right,parent_right+1,2,
'三级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 2;
--计算受影响结点的左右值
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
INSERT INTO T_TEST VALUES(4,'微信管理',parent_right,parent_right+1,2,
'三级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 4;
--计算受影响结点的左右值
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
INSERT INTO T_TEST VALUES(5,'服务号',parent_right,parent_right+1,3,
'四级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 4;
--计算受影响结点的左右值
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
INSERT INTO T_TEST VALUES(6,'企业号',parent_right,parent_right+1,3,
'四级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 1;
--计算受影响结点的左右值
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
INSERT INTO T_TEST VALUES(7,'行政中心',parent_right,parent_right+1,1,
'二级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 7;
--计算受影响结点的左右值
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
INSERT INTO T_TEST VALUES(8,'车辆管理',parent_right,parent_right+1,2,
'三级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 1;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
INSERT INTO T_TEST VALUES(9,'人力资源',parent_right,parent_right+1,1,
'二级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 9;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
INSERT INTO T_TEST VALUES(10,'组织结构',parent_right,parent_right+1,2,
'二级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 9;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
INSERT INTO T_TEST VALUES(11,'员工档案',parent_right,parent_right+1,2,
'二级菜单');
--查出父节点的right值
SELECT r INTO parent_right from t_test where id = 9;
--计算受影响结点的左右值 ,要保持父节点右值比所有子节点的右值大,左节点左值比所有子结点左值小
UPDATE T_TEST SET l=l+2 WHERE l >= parent_right;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_right;
INSERT INTO T_TEST VALUES(12,'合同管理',parent_right,parent_right+1,2,
'二级菜单');
--在设备管理前面添加一个节点作为其兄弟节点
--查出兄弟节点的right值
SELECT l,r INTO parent_left,parent_right from t_test where id = 3;
--计算受影响结点的左右值
UPDATE T_TEST SET l=l+2 WHERE l >= parent_left;
UPDATE T_TEST SET r=r+2 WHERE r >= parent_left;
INSERT INTO T_TEST VALUES(13,'设备管理前的兄弟节点',parent_left,parent_right,2,'我是新加入的兄弟节点');
--删除节点
--删除ID=4节点下的所有子节点,查出父节点的right值
SELECT l,r INTO parent_left,parent_right from t_test where id = 4;
--LEFT比父节点值大 且right比父节点值小,则表示是它的字节点,删除子节点
--delete from t_test where l >=parent_left and r <=parent_right;
--修改受影响节点的值,left > 父节点left right > 父节点right,也就是修改其所有父节点的左右值
--update t_test set l=l-(parent_right - parent_left + 1) where l > parent_left;
--update t_test set r=r-(parent_right - parent_left + 1) where r > parent_right;
--查询节点
--查询节点下全部子孙菜单不包括自身菜单 (查询“根菜单下的所有子节点”),子查询中id=1表示查询该父节点的left值和right值
--SELECT * FROM t_test WHERE l > (SELECT l from t_test where id = 1) AND r < (SELECT r from t_test where id = 1);
--查询子孙总数=(右值-左值-1)/2
--查询某一节点的全部父祖节点
--SELECT * FROM t_test WHERE l <(SELECT l from t_test where id = 4) AND r > (SELECT r from t_test where id = 4) order by l;
--判断某一节点是否是指定节点的字节点,判断条件是 子节点的Left > 父节点left , 子节点right < 父节点Right
--8 > 3 AND 9 <4 = false
--判断是否是指定节点的父节点同理,子节点的Left < 父节点left , 子节点right > 父节点Right
--移动节点,此移动方式操作多余
SELECT l, r into target_left,target_right FROM t_test WHERE id = 10;
--要移动的节点
SELECT l,r into source_left,source_right from t_test where id = 12;
UPDATE T_TEST SET l=l+2,r=r+2 WHERE l >= target_left and r <= source_right;
--UPDATE T_TEST SET r=r+2 WHERE ;
--移动节点 ,将合同管理移动到组织结构前面
UPDATE T_TEST SET l=target_left,r=target_right WHERE id=12;
--移动节点思路一,同节点平移可以直接交换左右值即可(应使用这个)
--节点同等级后移,id=11是移动到其节点后的目标节点
SELECT l, r into target_left,target_right FROM t_test WHERE id = 12;
--要移动的节点
SELECT l,r into source_left,source_right from t_test where id = 10;
--移动节点
UPDATE T_TEST SET l=target_left,r=target_right WHERE id=10;
UPDATE T_TEST SET l=source_left,r=source_right WHERE id=12;
RETURN;
END$BODY$
LANGUAGE plpgsql VOLATILE
COST 100
整理后的版本:https://reiner.host/posts/9340b114.html