树形结构先序遍历树实践(MPTT)

树形结构先序遍历树实践

公司项目中经常使用到树形结构功能,如机械部件的维护等,当数据量达到一定级别会有性能问题:

1. 查询效率低,无论是在数据库中做递归还是在代码中递归都会浪费计算性能
2. 如果一次性查给前台,数据量大的情况话下浏览器会卡顿
3. 当查询加入其他业务逻辑的时候会导致代码复杂度增加

Modified Preorder Tree Traversal (改进先序遍历树）

网上查找方案的时候看到这种解决方案, 该方案可以快速查找子孙节点。

原理

1. 设节点有left,right, parentId三个字段,根节点left=1, right=2;
2. 节点插入子节点的时候, 令新节点的left=parent.right,right=left+1;
3. 找出所有节点满足left,right大于新增点的left,right, 另这些节点的left和right值加2;

如此我们能得到类似下面的结构

跟二叉树的先序遍历很像

如此，当我们需要查询江苏下面所有的子孙节点的时候, 可以用以下sql去查询
SELECT * FROM table_name where lft > 2 and rgt < 11;

插入删除节点

这种结构对于增删操作效率较低, 需要更改大量节点的左右值, 可以写成存储过程

• 插入: 节点插入子节点的时候, 令新节点的left=parent.right,right=left+1;
• 删除: 每删一个节点, 相当于减少了right-left+1个子节点, 对于parent.right>left和parent.left >left的情况, 减去delta即可

实现

• 表结构

CREATE TABLE `nested_category` (
  `category_id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) CHARACTER SET utf8mb4 NOT NULL,
  `parent_id` int(255) NOT NULL DEFAULT '0',
  `lft` int(255) NOT NULL,
  `rgt` int(255) NOT NULL,
  `deleted` tinyint(255) NOT NULL DEFAULT '0',
  PRIMARY KEY (`category_id`)
) ENGINE=InnoDB AUTO_INCREMENT=19 DEFAULT CHARSET=latin1

• 插入存储过程

CREATE DEFINER=`root`@`%` PROCEDURE `insert_node_into_nested_category`(IN `nodeId` int,IN `namee` varchar(255))
BEGIN
    #Routine body goes here...
    DECLARE lftt int(255);
    DECLARE rgtt int(255);
    DECLARE parentId int;
    SELECT category_id, rgt, rgt+1 INTO parentId, lftt, rgtt FROM nested_category WHERE category_id = nodeId;
    # SELECT parentId,lftt,rgtt,nodeId,namee;
    UPDATE nested_category SET lft=lft+2 WHERE lft > lftt;
    UPDATE nested_category SET rgt=rgt+2 WHERE rgt >= lftt;
    INSERT into nested_category (name,lft,rgt,parent_id) VALUES (namee,lftt,rgtt,parentId);
END

• 删除存储过程

CREATE DEFINER=`root`@`%` PROCEDURE `del_node_from_nested_category`(IN `nodeId` int)
BEGIN
    #Routine body goes here...
    DECLARE lftt,rgtt,delta int;
    SELECT lft, rgt, rgt-lft+1
        INTO lftt, rgtt, delta FROM nested_category WHERE category_id=nodeId;
    # select lftt,rgtt,delta;
    UPDATE nested_category SET lft=lft-delta where lft > rgtt;
    UPDATE nested_category set rgt=rgt-delta WHERE rgt > rgtt;
    DELETE from nested_category WHERE category_id=nodeId or parent_id=nodeId;
END

测试

执行插入存储过程

SET @id=5;
SEt @pk='浦口区';
set @jn='江宁区';
set @yh='雨花台区';
set @xw='玄武区';
set @gl='鼓楼区';
set @qh='秦淮区';
set @jy='建邺区';
set @qx='栖霞区';

CALL insert_node_into_nested_category(@id,@pk);
CALL insert_node_into_nested_category(@id,@jn);
CALL insert_node_into_nested_category(@id,@yh);
CALL insert_node_into_nested_category(@id,@xw);
CALL insert_node_into_nested_category(@id,@gl);
CALL insert_node_into_nested_category(@id,@qh);
CALL insert_node_into_nested_category(@id,@jy);
CALL insert_node_into_nested_category(@id,@qx);

执行删除存储过程
CALL del_node_from_nested_category(5)

总结

该方案对于查询频繁的场景和很适合使用, 如果增删频繁则不建议使用, 如果有更好的方案欢迎讨论。

由于作者水平有限, 如果文中有错误还望指正哦O(∩_∩)O。