关于树形结构:树形结构先序遍历树实践MPTT

公司我的项目中常常应用到树形构造性能, 如机械部件的保护等, 当数据量达到肯定级别会有性能问题:

查问效率低, 无论是在数据库中做递归还是在代码中递归都会节约计算性能
如果一次性查给前台, 数据量大的状况话下浏览器会卡顿
当查问退出其余业务逻辑的时候会导致代码复杂度减少

网上查找计划的时候看到这种解决方案, 该计划能够疾速查找子孙节点。

设节点有 left,right, parentId 三个字段, 根节点 left=1, right=2;
节点插入子节点的时候, 令新节点的 left=parent.right,right=left+1;
找出所有节点满足 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。

关于树形结构:树形结构先序遍历树实践MPTT

树形构造先序遍历树实际

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

原理

插入删除节点

实现

测试

总结