树形结构数据的拖动排序

实现如下结构的数据，用户可进行拖拽排序

• #folder-1
  • #table-1-1
  • #folder-1-2
    • #table-1-2-1
  • #folder-1-3
    • #table-3(插入位置）
  • #table-1-1
• #folder-2
• #table-3

需求描述：

1. 实现上面结构的数据，目录节点可以嵌套子节点，表节点则只能是叶子节点（即不可嵌套子节点）
2. 用户可自由拖拽节点到任意位置，例如：将 #table-3 拖动到 #folder-1-3 下面。

表设计

我们从数据库设计开始，首先需要表示节点间层级关系，因此需要一个 parentId 来记录当前节点的父节点ID，parentId 为空时表示当前节点是最外层节点。

字段名	说明
id	主键
parent_id	父节点ID
node_name	节点名称
node_type	节点类型（0:目录，1:表）

节点层级关系表述完了，接下来需要思考如何排序。

通过 Sort 字段排序

首先想到的是添加 sort 字段进行排序。查询数据时按照 sort 的大小进行排列。

字段名	说明
id	主键
parent_id	父节点ID
sort	排序值
node_name	节点名称
node_type	节点类型（0:目录，1:表）

SELECT * FROM nodes ORDER BY sort ASC；

通过添加sort 字段，在SQL查询阶段就可以对数据排序了。但是这种做法有个问题：

每当拖拽一条记录，需要前端吧排序好后的ID数组给到后端，后端根据ID数组更新多条数据的排序值

如果数据量不大，我一般会对所有数据的sort值都更新一遍，简单粗暴。

当然也可以通过拖拽后和拖拽前的位置计算需要修改的数据范围，从而减少需要更新的数据数量。

这种做法本质上是通过「数组」的数据结构来更新数据，相当于把数组的一个位置的数据插入到另一个位置，从而使得插入位置后的数据都需要整体往后移动。

那么有没有办法减少每次拖动带来的多条数据更新呢？

通过链表排序

准确来说是通过单链表进行排序，在数据表中添加 prev_id 字段，这个字段用于记录**当前节点的前一个节点的id 。**通过下面的数据来具体说明：

id	parent_id	prev_id	node_name	node_type
1			folder-1	0
2		1	folder-2	0
3		2	table-3	1
4	1		table-1-1	1
5	1	4	folder-1-3	0

根据 parent_id 和 prev_id 的规则，得到如下结构的数据

如何排？

定义的这种结构的数据，不能在通过SQL查询直接将数据排序了，则需要先从数据库把数据都取出，通过程序代码进行排序。以 Golang 为例代码如下：

func (b *projectNodeBiz) GetProjectNodeList(ctx fiber.Ctx, projectId string) ([]*res.ProjectNodeItem, error) {
	// 1. 从数据库读取数据
	list, err := b.Queries.GetProjectNodeList(ctx.Context(), projectId)
	if err != nil {
		log.Errorf("[biz] select project node list error: %v", err)
		return nil, errors.New("internal server error")
	}
  // 2.生成数据
	resList := genProjectNodeTree(list, "")

	return resList, nil
}

// 递归生成树
func genProjectNodeTree(list []repository.ProjectNode, parentId string) []*res.ProjectNodeItem {
	resList := []*res.ProjectNodeItem{}

	for _, node := range list {
		if node.ParentID.String == parentId {
			resList = append(resList, &res.ProjectNodeItem{
				ID:          node.ID,
				ParentID:    node.ParentID.String,
				PrevID:      node.PrevID.String,
				ProjectID:   node.ProjectID,
				NodeType:    node.NodeType,
				Children:    []*res.ProjectNodeItem{},
			})
		}
	}

	for _, node := range resList {
	 // 递归调用
		node.Children = genProjectNodeTree(list, node.ID)
	}
  // 根据prevId进行排序
	resList = sortChildren(resList)
	return resList
}

/**
* 根据prevId排序 prevId为空则认为是当前层级内的根节点，prevId 表示当前节点的上一个节点
 */
func sortChildren(list []*res.ProjectNodeItem) []*res.ProjectNodeItem {
	var current *res.ProjectNodeItem
	sortMap := make(map[string]*res.ProjectNodeItem)
  
  // 把数据根据 prevID 放到一个map上面。这里有个隐藏的约束就是，当前层级的prevId 不会重复。 
	for _, child := range list {
		if child.PrevID == "" {
			current = child
		} else {
			sortMap[child.PrevID] = child
		}
	}
	var result []*res.ProjectNodeItem

	for current != nil {
		result = append(result, current)
		current = sortMap[current.ID]
	}

	return result
}

简单解释下上面代码做了哪些

1. 首先从数据库读取节点数据
2. 通过递归将数据组合成树形结构的数组数据。
3. 在递归的同时对children的数据进行排序，通过 prevId 排序。

通过链表方式进行排序的好处就是，他减少了需要更新数据的数量。其本质是对链表进行插入排序等操作。

结合上面的示例数据，我们将 #table-3 拖中到 #folder-1-3 下面。需要做如下步骤：

1. 将**#table-3**从链表 folder-1 —> folder-2 —> table-3 中取下来。
2. 此时需要判断下**#table-3** 后面是否还有节点，如果有则将其的下一个节点的prev_id 改成当前节点的 prev_id 的值。其实也就是从链表取下一个节点后，再把链表连接起来。
3. 找到需要插入的节点位置，此时需要插入的节点位置是**#folder-1-3** 的第一个节点位置，这意味着插入的位置没有上一个节点，因此可以将当前节点的prev_id 设置为空，parent_id 设置为**#folder-1-3** 的ID。其实就是将其设置为#folder-1-3 children链表的头节点。
4. 同样的，需要判断当前插入节点位置后面有没有下一个节点，如果有，则需要将其prev_id 设置成当前节点的ID。同样是为了将链表连接起来。

这种做法避免了更新多条数据的排序值。最多需要更改三条数据的值，即：

1. 当前数据的prev_id 和 parent_id
2. 当前移除位置的下一个节点的prev_id (如果有）
3. 当前插入位置的下一个节点的prev_id (如果有)

以下是代码示例：

func (b *projectNodeBiz) MoveProjectNode(ctx fiber.Ctx, updatedBy string, req *req.MoveProjectNodeReq) error {
	tx, err := b.Queries.NewDB().Begin(ctx.Context())
	if err != nil {
		log.Errorf("[biz] begin transaction error: %v", err)
		return errors.New("internal server error")
	}
	defer tx.Rollback(ctx.Context())
	qtx := b.Queries.WithTx(tx)

	currentNode, err := qtx.GetProjectNode(ctx.Context(), req.NodeId)
	if err != nil {
		log.Errorf("[biz] select project node by id error: %v", err)
		return errors.New("internal server error")
	}

	// 1.如果有下一个兄弟节点，则将下一个兄弟节点的prevId设置为当前节点的prevId
	currentNodeNextSibling, err := qtx.GetProjectNodeByPrevId(ctx.Context(), pgtype.Text{String: req.NodeId, Valid: true})
	if err == nil && currentNodeNextSibling.ID != "" {
		if err := qtx.MoveProjectNode(ctx.Context(), repository.MoveProjectNodeParams{
			ID:        currentNodeNextSibling.ID,
			PrevID:    pgtype.Text{String: currentNode.PrevID.String, Valid: true},
			ParentID:  pgtype.Text{String: currentNodeNextSibling.ParentID.String, Valid: true},
			UpdatedBy: pgtype.Text{String: updatedBy, Valid: true},
			UpdatedAt: pgtype.Timestamp{Time: time.Now(), Valid: true},
		}); err != nil {
			log.Errorf("[biz] move next sibling node error: %v", err)
			return errors.New("internal server error")
		}
	}

	if req.PreNodeId == "" {
		// 2.如果preNodeId为空，则将当前节点设置为parentId的第一个子节点
		firstChild, err := qtx.GetProjectNodeByPrevIdAndParentId(ctx.Context(), repository.GetProjectNodeByPrevIdAndParentIdParams{
			ParentID: pgtype.Text{String: req.ParentId, Valid: true},
			PrevID:   pgtype.Text{String: "", Valid: true},
		})
		if err == nil && firstChild.ID != "" {
			if err := qtx.MoveProjectNode(ctx.Context(), repository.MoveProjectNodeParams{
				ID:        firstChild.ID,
				PrevID:    pgtype.Text{String: currentNode.ID, Valid: true},
				ParentID:  pgtype.Text{String: firstChild.ParentID.String, Valid: true},
				UpdatedBy: pgtype.Text{String: updatedBy, Valid: true},
				UpdatedAt: pgtype.Timestamp{Time: time.Now(), Valid: true},
			}); err != nil {
				log.Errorf("[biz] move current node error: %v", err)
				return errors.New("internal server error")
			}
		}

		if err := qtx.MoveProjectNode(ctx.Context(), repository.MoveProjectNodeParams{
			ID:        currentNode.ID,
			PrevID:    pgtype.Text{String: "", Valid: true},
			ParentID:  pgtype.Text{String: req.ParentId, Valid: true},
			UpdatedBy: pgtype.Text{String: updatedBy, Valid: true},
			UpdatedAt: pgtype.Timestamp{Time: time.Now(), Valid: true},
		}); err != nil {
			log.Errorf("[biz] move current node error: %v", err)
			return errors.New("internal server error")
		}
	} else {
		// 3.如果preNodeId不为空，则将当前节点设置为preNode的下一个兄弟节点

		preNode, err := qtx.GetProjectNode(ctx.Context(), req.PreNodeId)
		if err != nil {
			log.Errorf("[biz] select project node by id error: %v", err)
			return errors.New("internal server error")
		}

		preNodeNextSibling, err := qtx.GetProjectNodeByPrevId(ctx.Context(), pgtype.Text{String: preNode.ID, Valid: true})
		if err == nil && preNodeNextSibling.ID != "" {
			// 3.1 如果preNode有下一个兄弟节点，则将下一个兄弟节点的prevId设置为当前节点的Id
			if err := qtx.MoveProjectNode(ctx.Context(), repository.MoveProjectNodeParams{
				ID:        preNodeNextSibling.ID,
				PrevID:    pgtype.Text{String: currentNode.ID, Valid: true},
				ParentID:  pgtype.Text{String: preNodeNextSibling.ParentID.String, Valid: true},
				UpdatedBy: pgtype.Text{String: updatedBy, Valid: true},
				UpdatedAt: pgtype.Timestamp{Time: time.Now(), Valid: true},
			}); err != nil {
				log.Errorf("[biz] move next sibling node error: %v", err)
				return errors.New("internal server error")
			}
		}

		if err := qtx.MoveProjectNode(ctx.Context(), repository.MoveProjectNodeParams{
			ID:        currentNode.ID,
			PrevID:    pgtype.Text{String: preNode.ID, Valid: true},
			ParentID:  pgtype.Text{String: preNode.ParentID.String, Valid: true},
			UpdatedBy: pgtype.Text{String: updatedBy, Valid: true},
			UpdatedAt: pgtype.Timestamp{Time: time.Now(), Valid: true},
		}); err != nil {
			log.Errorf("[biz] move current node error: %v", err)
			return errors.New("internal server error")
		}
	}

	return tx.Commit(ctx.Context())
}

其实从上面的代码可以看出，我们复杂化了查询列表和移动节点的代码，为了是减少排序时需要修改的数据量。除了这两个业务代码修改了以外，删除节点的操作同样需要修改，需要修改的地方是：删除当前节点后，需要将链表再连接起来。

总结

链表排序的优点如下：

• 移动节点操作效率高 - 只需要修改指针（PrevID）
• 适合频繁的插入和删除操作
• 维护顺序的成本低 - 不需要重新排序整个数组
• 空间复杂度低 - 只需要存储节点间的引用关系

缺点：

• 不支持随机访问 - 必须从头遍历
• 如果链表断裂（数据不完整），可能会丢失部分数据
• 遍历性能较差 - O(n)的时间复杂度

Sort排序方式的优点如下：

• 实现简单直观
• 支持多种排序条件
• 支持随机访问
• 不需要维护额外的节点关系

缺点：

• 每次修改都需要重新排序，时间复杂度 O(nlogn)
• 对于频繁的插入删除操作，性能较差
• 批量更新排序字段比较麻烦

所以具体使用那种排序方式，取决于业务的侧重点以及数据量。如果排序操作频繁可以考虑使用链表排序。如果数据不大，考虑到代码维护成本，那么sort排序是个不错的选择。

我比较侧重于链表排序，因为我写出来了🤭。同时考虑到递归的次数，我可能会限制目录文件夹可嵌套的层数来减少递归次数，如果用户需要更多层的嵌套，得加钱😂

完。