文章目录
1 基础数据
2 继承关系驱动的架构设计
2.1 表结构
2.2 方案的优点及缺点
3 基于左右值编码的架构设计
3.1 表结构
3.2 方案优缺点
4 基于继承关系及左右值编码的架构设计
4.1 表结构
4.2 CURD操作
4.2.1 create node
4.2.2 delete node
4.2.3 move node
4.2.4 select
5 总结
1、基础数据
我们以以下数据为例进行说明
2、继承关系驱动的架构设计
2.1表结构
2.2方案的优点及缺点
优点: 设计和实现简单, 直观
缺点: CURD操作是低效的, 主要归根于频繁的“递归”操作导致的IO开销
解决方案: 在数据规模较小的情况下可以通过缓存机制来优化
3、基于左右值编码的架构设计
3.1表结构
第一次看见这种表结构，相信大部分人都不清楚左值（left）和右值（right）是如何计算出来的，而且这种表设计似乎并没有保存父子节点的继承关系。但当你用手指指着表中的数字从1数到20，你应该会发现点什么吧。对，你手指移动的顺序就是对这棵树进行前序遍历的顺序，如下图所示。当我们从根节点A左侧开始，标记为1，并沿前序遍历的方向，依次在遍历的路径上标注数字，最后我们回到了根节点A，并在右边写上了20。
3.2 方案优缺点
优点:
可以方便的查询出某个节点的所有子孙节点
可以方便的获取某个节点的族谱路径(即所有的上级节点)
可已通过自身的left, right值计算出共有多少个子孙节点
缺点:
增删及移动节点操作比较复杂
无法简单的获取某个节点的子节点
4、基于继承关系及左右编码的架构设计
其实就是在第三节的基础上又加了一列parent_id, 目的是在保留上述优点的同时可以简单的获取某个节点的直属子节点
4.1表结构
4.2CURD操作
4.2.1 create note(创建节点)
# 为id为 id_ 的节点创建名为 name_ 的子节点 CREATE PROCEDURE `tree_create_node`(IN `id_` INT, IN `name_` VARCHAR(50)) LANGUAGE SQL NOT DETERMINISTIC CONTAINS SQL SQL SECURITY DEFINER COMMENT '创建节点' BEGIN declare right1 int; # 当 id_ 为 0 时表示创建根节点 if id_ = 0 then # 此处我限制了仅允许存在一个根节点, 当然这并不是必须的 if exists(select `id` from tree_table where `left` = 1) then SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '根节点已存在'; end if; insert into tree_table(`parent_id`, `name`, `left`, `right`) values(0, name_, 1, 2); commit; elseif exists(select `id` from tree_table where `parent_id` = id_ and `name` = name_) then # 禁止在同一级创建同名节点 SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '已存在同名兄弟节点'; elseif exists(select `id` from tree_table where `id` = id_) then start transaction; set right1=(select `right` from tree_table where `id` = id_); update tree_table set `right` = `right` + 2 where `right` >= right1; update tree_table set `left` = `left` + 2 where `left` >= right1; insert into tree_table(`parent_id`, `name`, `left`, `right`) values(id_, name_, right1, right1 + 1); commit; # 下面一行仅为了展示以下新插入记录的id, 并不是必须的 select LAST_INSERT_ID(); else SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '父节点不存在(未创建或被删除)'; end if; END
# 创建根节点(参数：0代表parentId,'A'代表name) call tree_create_node(0, 'A') # 为节点1创建名为AB的子节点 call tree_create_node(1, 'AB')
4.2.2 delete note(删除节点)
CREATE PROCEDURE `tree_delete_node`(IN `id_` INT) LANGUAGE SQL NOT DETERMINISTIC CONTAINS SQL SQL SECURITY DEFINER COMMENT '' BEGIN declare left1 int; declare right1 int; if exists(select id from tree_table where id = id_) then start transaction; select `left`, `right` into left1, right1 from tree_table where id = id_; delete from tree_table where `left` >= left1 and `right` <= right1; update tree_table set `left` = `left` - (right1-left1+1) where `left` > left1; update tree_table set `right` = `right` - (right1-left1+1) where `right` > right1; commit; end if; END
# 删除节点2, 节点2的子孙节点也会被删除(参数：2代表当前节点id)
call tree_delete_node(2)4.2.3 move note(移动节点)
move的原理是先删除再添加, 但涉及被移动的节点的left, right值不能乱所以需要使用临时表(由于在存储过程中无法创建临时表, 此处我使用了一张正常的表进行缓存, 欢迎提出更合理的方案)
# 此存储过程中涉及到is_delete字段, 表示数据是否被删除, 因为正式环境中删除操作一般都不会真的删除而是进行软删(即标记删除), 如果不需要此字段请自行对程序进行调整 CREATE PROCEDURE `tree_move_node`(IN `self_id` INT, IN `parent_id` INT , IN `sibling_id` INT) LANGUAGE SQL NOT DETERMINISTIC CONTAINS SQL SQL SECURITY DEFINER COMMENT '' BEGIN declare self_left int; declare self_right int; declare parent_left int; declare parent_right int; declare sibling_left int; declare sibling_right int; declare sibling_parent_id int; if exists(select id from tree_table where id = parent_id and is_delete = 0) then # 创建中间表 CREATE TABLE If Not Exists tree_table_self_ids (`id` int(10) unsigned NOT NULL); truncate tree_table_self_ids; start transaction; # 事务 # 获取移动对象的 left, right 值 select `left`, `right` into self_left, self_right from tree_table where id = self_id; # 将需要移动的记录的 id 存入临时表, 以保证操作 left, right 值变化时这些记录不受影响 insert into tree_table_self_ids(id) select id from tree_table where `left` >= self_left and `right` <= self_right; # 将被移动记录后面的记录往前移, 填充空缺位置 update tree_table set `left` = `left` - (self_right-self_left+1) where `left` > self_left and id not in (select id from tree_table_self_ids); update tree_table set `right` = `right` - (self_right-self_left+1) where `right` > self_right and id not in (select id from tree_table_self_ids); select `left`, `right` into parent_left, parent_right from tree_table where id = parent_id; if sibling_id = -1 then # 在末尾插入子节点 update tree_table set `right` = `right` + (self_right-self_left+1) where `right` >= parent_right and id not in (select id from tree_table_self_ids); update tree_table set `left` = `left` + (self_right-self_left+1) where `left` >= parent_right and id not in (select id from tree_table_self_ids); update tree_table set `right`=`right` + (parent_right-self_left), `left`=`left` + (parent_right-self_left) where id in (select id from tree_table_self_ids); elseif sibling_id = 0 then # 在开头插入子节点 update tree_table set `right` = `right` + (self_right-self_left+1) where `right` > parent_left and id not in (select id from tree_table_self_ids); update tree_table set `left` = `left` + (self_right-self_left+1) where `left` > parent_left and id not in (select id from tree_table_self_ids); update tree_table set `right`=`right` - (self_left-parent_left-1), `left`=`left` - (self_left-parent_left-1) where id in (select id from tree_table_self_ids); else # 插入指定节点之后 select `left`, `right`, `parent_id` into sibling_left, sibling_right, sibling_parent_id from tree_table where id = sibling_id; if parent_id != sibling_parent_id then SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '指定的兄弟节点不在指定的父节点中'; end if; update tree_table set `right` = `right` + (self_right-self_left+1) where `right` > sibling_right and id not in (select id from ctree_table_self_ids); update tree_table set `left` = `left` + (self_right-self_left+1) where `left` > sibling_right and id not in (select id from tree_table_self_ids); update tree_table set `right`=`right` - (self_left-sibling_right-1), `left`=`left` - (self_left-sibling_right-1) where id in (select id from tree_table_self_ids); end if; update tree_table set `parent_id`=parent_id where `id` = self_id; commit; else SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '父节点不存在(未创建或被删除)'; end if; END
# 将节点2移动到节点1下面开头的位置 call tree_move_node(2, 1, 0) # 将节点2移动到节点1下面末尾的位置 call tree_move_node(2, 1, -1) # 将节点2移动到节点1下面且跟在节点3后面的位置 call tree_move_node(2, 1, 3)
4.2.4 select(查询节点以及子节点)
# 以下sql中需要传的值全用???表示(正常写代码使用#{}传值) # 根据节点id获取此节点所有子孙节点 select * from tree_table where `left` > (select `left` from tree_table where id=???) and `right` < (select `right` from tree_table where id=???) # 根据节点id获取此节点的所有子孙节点(包含自己) select * from tree_table where `left` >= (select `left` from tree_table where id=???) and `right` <= (select `righ`t from tree_table where id=???) # 根据节点id获取此节点的所有上级节点 select * from tree_table where `left` < (select `left` from tree_table where id=???) and `right` > (select `right` from tree_table where id=???) # 根据节点id获取此节点的所有上级节点(包括自己) select * from tree_table where `left` <= (select `left` from tree_table where id=???) and `right` >= (select `right` from tree_table where id=???)
注意：上述字段设计使用到了left和right，这属于关键字，在写sql语句时需要加上``符号。
5、总结
上述多数内容属于函数的存储过程，只需要在数据库表建好之后执行即可。正常添加、删除、移动节点只需要执行call.....这个函数即可。
代码编写中，可以如下：
/** * 添加节点内容 * @param parentId * @param name */ @Insert("call tree_create_node(#{parentId}, #{name})") void saveStructureTree(Long parentId, String name); /** * 删除当前节点以及子节点信息 * @param id */ @Delete("call tree_delete_node(#{id})") void deleteStructureTree(@Param("id")Long id);