Data storage practice based on left-order traversal

参考文章

超赞 ! A foreigner's design and implementation of a tree data table that avoids recursively querying all sub-departments！

But when it comes to practice,Found an error somewhere in this article：

It is updated first and then deleted,It is found that the update will also update the node rvalue of the node to be deleted.
所以正确的做法是：
删除对应的Sql:

SET @lft := 7;/*要删除的节点左值*/
SET @rgt := 8;/*要删除的节点右值*/
begin;

/*先删除节点*/
DELETE FROM department WHERE lft=@lft AND rgt=@rgt;

/*再更新节点 */
UPDATE department SET lft=lft-2 WHERE lft > @lft;
UPDATE department SET rgt=rgt-2 WHERE rgt > @lft;

/*删除影响行数为0时,必须回滚*/
commit;
/*rollback*/

实践

The technical background used

This paper is used in practicego语言1.18.1+gormv1.23.6+sqlitev1.3.5
This practice is to do a cloud configuration function.The order of nodes is as follows：
客户 -> 项目 -> stop -> 电脑
The effect displayed by the client is as follows：

The purpose of implementation is to store the software configuration of each computer according to the above nodes.

节点模型

type NodeInfo struct {
    
	Id    uint   `gorm:"primary_key;Column:Id"`
	Name  string `gorm:"column:Name"`
	Level uint   `gorm:"column:Level"`
	Left  uint   `gorm:"column:Left"`
	Right uint   `gorm:"column:Right"`
}

对于Level的定义：

• 1：客户
• 2：项目
• 3：stop
• 4：电脑

查询

Customer names are unique,不能重复,Other nodes can repeat.

Query customer node information by customer name：

func getCustomer(customer string) (*models.NodeInfo, error) {
    
	info := &models.NodeInfo{
    }
	if err := databases.DB.Where("Name=? and Level=1", customer).First(info).Error; err != nil {
    
		return nil, err
	} else {
    
		return info, nil
	}
}

查询所有的客户节点：只需要查询Level=1即可

func getCustomers() ([]models.NodeInfo, error) {
    
	infos := make([]models.NodeInfo, 0)
	if err := databases.DB.Where("Level=1").Find(&infos).Error; err != nil {
    
		return nil, err
	} else {
    
		return infos, nil
	}
}

查询指定客户名称All project nodes under ：

Get the client node first,Get the client's lvalue and rvalue,Then get all by lvalue and rvalue项目子节点

func getProjects(customer string) ([]models.NodeInfo, error) {
    
	customerModel := &models.NodeInfo{
    }
	var err error
	if customerModel, err = getCustomer(customer); err != nil {
    
		return nil, err
	}

	infos := make([]models.NodeInfo, 0)
	if err := databases.DB.Where("Level=2 and Left>? and Right<?", customerModel.Left, customerModel.Right).Find(&infos).Error; err != nil {
    
		return nil, err
	}
	return infos, nil
}

查询stop、电脑与以上类似.

插入一个节点

func insertNode(name string, level uint, left uint) (*models.NodeInfo, error) {
    

	model := &models.NodeInfo{
    
		Name:  name,
		Level: level,
		Left:  uint(left),
		Right: left + 1,
	}
	if err := databases.DB.Transaction(func(tx *gorm.DB) error {
    
		if err := tx.Exec("update NodeInfo set Right=Right+2 where Right>=?", left).Error; err != nil {
    
			return err
		}
		if err := tx.Exec("update NodeInfo set Left=Left+2 where Left>?", left).Error; err != nil {
    
			return err
		}

		if err := tx.Create(model).Error; err != nil {
    
			return err
		}
		return nil
	}); err != nil {
    
		return nil, err
	}
	return model, nil
}

步骤是：Update other nodes first,再插入节点
其中:
nameis the name of the node to be inserted
levelis the level at which to insert the node,This determines whether to insert parallel nodes or child nodes,
leftis the lvalue of the node to be inserted,通常为父节点或者左节点的右值+1
For example, when there is no node at all,To insert a customer name as AAA的节点：

insertNode("AAA",1,1)

比如在客户名称为 AAA,左值为1,右值为2Add a project name under the node of PPP的节点：

//项目节点：level为2,The left value is the client node“AAA”的右值+1
insertNode("PPP",2,3)

删除一个节点

func removeNode(model *models.NodeInfo) error {
    
	return databases.DB.Transaction(func(tx *gorm.DB) error {
    
		if err := tx.Delete(models.NodeInfo{
    }, "Left=? and Right=?", model.Left, model.Right).Error; err != nil {
    
			return err
		}
		if err := tx.Exec("update NodeInfo Set Left=Left-2 where Left>?", model.Left).Error; err != nil {
    
			return err
		}
		if err := tx.Exec("update NodeInfo set Right=Right-2 where Right>?", model.Right).Error; err != nil {
    
			return err
		}
		return nil
	})

}

步骤是：先删除节点,Then update other nodes,Opposite of adding node operation,The delete node on the WeChat article is wrong！！！

注意：This function can only delete a single node with no children

批量删除节点

func removeNodes(ms []models.NodeInfo) error {
    
	return databases.DB.Transaction(func(tx *gorm.DB) error {
    
		for _, model := range ms {
    
			if err := tx.Delete(models.NodeInfo{
    }, "Left=? and Right=?", model.Left, model.Right).Error; err != nil {
    
				return err
			}
		}
		for _, model := range ms {
    
			if err := tx.Exec("update NodeInfo Set Left=Left-2 where Left>?", model.Left).Error; err != nil {
    
				return err
			}
			if err := tx.Exec("update NodeInfo set Right=Right-2 where Right>?", model.Left).Error; err != nil {
    
				return err
			}
		}

		return nil
	})
}

注意：This function can delete nodes in batches though,但是要注意使用场景：When a parent node is selected,All child nodes under the parent node will be deleted,传入时,需要按照LevelFields are passed in descending order,否则会出错！
如下图所示：

When deleting a client node,All child nodes under the client node will be queried,Then follow the child nodesLevelSort incoming in descending order.
The code to delete the client node is as follows：

func removeCustomer(customer string) error {
    
	info := &models.NodeInfo{
    }
	var err error
	if info, err = getCustomer(customer); err != nil {
    
		return err
	}

	//查询customerThe descendant node below,然后全部移除,Also remove the folder
	infos := make([]models.NodeInfo, 0)
	if err = databases.DB.Where("Left>=? and Left<=?", info.Left, info.Right).Find(&infos).Error; err != nil {
    
		return err
	}

	//排序,Remove the bottom node first,Then remove the above node
	linq.From(infos).OrderByDescending(func(i interface{
    }) interface{
    } {
     return i.(models.NodeInfo).Level }).ToSlice(&infos)

	if err = removeNodes(infos); err != nil {
    
		return err
	}
	return nil
}

步骤是：Get the client node information first,Query all child nodes under the client node（包含自己）,Then sort the nodes in descending order,调用removeNodes方法

总结

以上实践,It is indeed better than the traditional pass in terms of queryParentIdMuch better to relate,Avoid recursive queries,But inserting and deleting can be a little trickier,各有利弊,But left-order traversal is an innovative approach,It takes a lot of practice to feel its benefits