树形构造先序遍历树实际

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

  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。