Mysql之运用预排序树算法

先阅读预排序算法

首先创建表结构：

SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;

-- ----------------------------
-- Table structure for test
-- ----------------------------
DROP TABLE IF EXISTS `test`;
CREATE TABLE `test` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(255) DEFAULT NULL,
`lft` int(11) DEFAULT NULL,
`rgt` int(11) DEFAULT NULL,
`content` varchar(255) DEFAULT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

SET FOREIGN_KEY_CHECKS = 1;

预先塞入一条数据:

WechatIMG401.jpeg

现在我们需要新增一条归属第一代下id为1的子孙节点

select id,lft,rgt from test where lft>1 and rgt<2

该result结果集为空,就意味着该节点下没有任何子节点
现在我们需要给父节点的右值进行+2为子孙节点让出位置

update test set rgt = rgt+2 where rgt>1

新增子孙节点

insert into test (name,lft,rgt,content) values('b',2,3,'我是第二代')

WechatIMG402.jpeg

现在我们假定又有一条基于第一代的子孙节点需要加入：

select id,lft,rgt from test where lft>1 and rgt<4

现在结果集不为空
对于该新子孙节点的兄弟节点左值为2 右值为3
那么还是需要给新节点腾出位置
变更所有的受影响的节点,给新节点腾出空位子，所有左节点比该子孙节点大的，都增加2
所有右节点比该子孙节点大的，都增加2

update test set lft = rgt+2 where lft>2
update test set rgt = rgt+2 where rgt>3

新增子孙节点

insert into test (name,lft,rgt,content) values('c',4,5,'我也是第二代')

WechatIMG403.jpeg

算法说明：
新增无兄弟节点的节点，需要变更所有比父级节点左值大的左右值+2，节点自身左值等于父级左值N+1,右值等于(N+1)+1
新增 有兄弟节点的需要变更所有比父级左值大的+2，右值大的+2,腾出空间，节点自身左值等于兄弟右值N+1,右值等于(N+1)+1