无线层级递归解决方案：”左右植”树结构算法

这是我参与更文挑战的第5天，活动详情查看： 更文挑战

hello 艾瑞巴得，大家有没有遇到过一种需求，例如无限层级的标签，可自由创建子标签，子子标签，或者A用户邀请B用户，B用户邀请了C用户。。。。需要保存这类用户的关系链等类型的需求，查询的时候苦于递归查询，层级较少的时候还行，多了的话不光业务复杂还极其影响性能，今天，解决方案它来了：看”左右植”树结构算法！是如何解决无限层级递归；

需求背景：

小编之前工作中遇到了一个这样的需求，是一个无限层级的标签系统，比如：1级标签：音乐，用户可以在音乐下自由创建子标签，子子标签。。。如子标签：乐器，子子标签：吉他，子子子标签：民谣吉他，同级标签：电吉他等等；

解决方案：

“左右植”树 的模型

如上所示我们把每一个节点，都假想他有一个左值，一个右值，把每个节点左右都当成两个连接点，从根菜单左边开始，沿着整个树的节点外围连接，一直连回到根菜单的右边，所经过节点的顺序就是节点的左右值了。

规律：

我们拿一个实例来看一下它的规律是这样的，请沿着某公司的左边开始数起（1），往技术部的左边（2），再到前端开发部左边（3），前端开发部右边（4），后端开发部左边（5），Java开发部左边（6）。。。走完后端开发部所有节点然后走到销售部左边（12）然后继续往下走。。。一直到回到跟节点莫公司右边（22）

技术方案设计：

表结构：

核心字段：左序列数（left_num），右序列数（right_num），菜单层级（level），父节点Id（parent_id）

如果查询频繁的话我们也可以在这些字段上建立索引

#左右植树表结构：
CREATE TABLE `cascading_menu` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增主键Id',
  `menu_name` varchar(32) NOT NULL DEFAULT '' COMMENT '菜单名称',
  `left_num` tinyint(2) NOT NULL DEFAULT '1' COMMENT '左序列数',
  `right_num` tinyint(2) NOT NULL DEFAULT '1' COMMENT '右序列数',
  `level` tinyint(2) NOT NULL DEFAULT '1' COMMENT '菜单层级',
  `icon` varchar(1024) DEFAULT NULL COMMENT '菜单介绍',
  `parent_id` bigint(20) DEFAULT NULL COMMENT '父节点Id',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=utf8mb4 ROW_FORMAT=COMPACT COMMENT='左右植树算法测试表';
复制代码

你当这样就完了吗？阿芙卡丝闹特！！！

有了表结构以后，我们在来看一下，如何使用

使用方法sql：

查询：

查询当前父节点下的所有子节点

SELECT * FROM cascading_menu WHERE left_num >1 AND right_num <24 ;
复制代码

查询某一级所有节点

SELECT * FROM cascading_menu WHERE level = 3;
复制代码

查询当前子节点上的所有父节点

SELECT id FROM cascading_menu WHERE left_num <= 3 AND right_num >= 4 ;
复制代码

查询节点下全部子孙菜单不包括自身菜单

SELECT * FROM menu WHERE left_num > 2  AND  right_num < 11
复制代码

计算某一节点下有多少个子孙节点：

例如想查询第一张图上的计算机中心这个菜单底下有多少个子菜单
技术部的左值为2 右值为11。

子菜单数量（不包括自身节点）
( 右值 – 左值 – 1 ) / 2  => ( 11 – 2 – 1 ) / 2 = 4
子菜单数量（包括自身节点）
( 右值 – 左值 + 1 ) / 2  => ( 11 – 2 + 1) / 2 = 5
复制代码

节点排序：

当你在 sql 查询时排序条件加上 order by left_num 的话，你会发现，返回的节点是按节点全部展开后由上往下的顺序，这个非常有用，在下面的 菜单跟树表格中非常关键。

SELECT * FROM cascading_menu WHERE left_num >1AND right_num <16 order BY left_num;
复制代码

插入（分3步）：

1. 腾位：大于当前节点的所有节点左右树的值都加2

UPDATE cascading_menu
SET left_num = left_num+2,right_num = right_num+2
WHERE left_num>(父右节点-1)
复制代码

2. 入位：插入节点

INSERT INTO cascading_menu (menu_name,left_num,right_num,`level`)
VALUES ('孙节点2',父右节点,父右节点+1,2);
复制代码

3. 查询插入的节点的所有父节点

SELECT id FROM cascading_menu WHERE left_num < 插入节点左树 AND right_num >= 插入节点左树;
复制代码

4. 修改查询到的节点的所有右树值+2

UPDATE cascading_menu SET right_num = right_num+2 WHERE id in ([第3步的 结果集])
复制代码

ok！文章到此就结束了，希望可以对大家有帮助，有不对的地方希望大家可以提出来的，共同成长;

整洁成就卓越代码，细节之中只有天地