background

When developing an administrative backend at work, there will always be a need for “drag-and-sort”, such as having a list of resources that can be dragged and dropped at the front to change the order of resources. A knowledge base similar to a finch supports drag-and-drop sorting of documents, as shown below:

The implementation scheme of this function in our project is as follows: the resource table has a position field, and the position values of other resources in the table can be changed during dragging and dropping.

One day it occurred to me that if there are a lot of resources involved, you need to UPDATE a lot of resources, but in reality we are only changing the location of one resource. Is there a better way? Here are two ways to think about it.

Technical solution

Option 1- Array

The resource table has a field position to indicate the location of the resource, DDL:

CREATE TABLE `activity` ( `id` int(11) NOT NULL AUTO_INCREMENT COMMENT 'ID', 'position' int(11) DEFAULT '0' COMMENT ', PRIMARY KEY (' id ')) ENGINE=InnoDB DEFAULT CHARSET= utf8MB4;Copy the code

When querying the list, sort by position ASC or desc:

 SELECT * FROM activity ORDER BY position ASC;
Copy the code

Drag a resource and the front end passes in the resource’s ID and a new location value, new_position. The back end queries the original position value (OLd_position) of the resource based on the ID and compares old_position and new_position. The value can be divided into the following three situations:

1, old_position == new_position

Remain the same

2. Old_position < new_position or old_position > new_position

For all resources where position >= new_position, the position value is increased by 1. The SQL statement is as follows:

 UPDATE activity SET position = position + 1 WHERE position >= #{new_position}
Copy the code

defects

Each drag changes a lot of data. If you drag a resource to the first row of a list, you change position for all data in the table. Such updates to range data can be coupled with table locks, resulting in reduced concurrency performance.

This happens because when you drag and drop data to update a position value, you insert an element into an array. The nature of the array structure is that when you insert a new element, you move all subsequent elements. As shown below, when inserting element 10 into position 2, move the elements in position 2 and beyond:

Option 2- Bidirectional linked lists

We know that linked lists are better for inserting elements than arrays. To insert an element in a linked list, we simply move the pointer to the preceding and following elements, as shown below:

Therefore, we can store resource data in the form of a linked list, DDL:

CREATE TABLE `activity` ( `id` int(11) NOT NULL AUTO_INCREMENT COMMENT 'ID', 'prev_id' int(11) DEFAULT NULL COMMENT 'prev_id' int(11) DEFAULT NULL COMMENT 'prev_id ',' sibling_id 'int(11) DEFAULT NULL COMMENT' prev_id ', 'position' FLOAT(6,2) DEFAULT '0.0' COMMENT 'DEFAULT ', PRIMARY KEY (' id'), KEY 'idx_prev_id' (' prev_id '), KEY `idx_sibling_id` (`prev_id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;Copy the code

moveAfter

Drag a resource to a resource, and the front end passes in the resource’s ID and its new Prev_id (the id of the previous resource). The back end updates the data based on the ID and prev_id as follows:

1. Query the current resource data (curActivity) based on the id

 curActivity : SELECT * FROM activity WHERE id = #{id};
Copy the code

Update resource Pointers before and after curActivity

 UPDATE activity SET prev_id = #{curActivity.prev_id} WHERE id = #{curActivity.sibling_id};
 UPDATE activity SET sibling_id = #{curActivity.sibling_id} WHERE id = #{curActivity.prev_id};
Copy the code

PrevActivity = prevActivity; prev_id = prevActivity; prevActivity = prevActivity

 prevActivity : SELECT * FROM activity WHERE id = #{prev_id};
Copy the code

4. Set the prevActivity pointer and subsequent data pointer

 UPDATE activity SET prev_id = #{id} WHERE id = #{prevActivity.slibling_id};
 UPDATE activity SET sibling_id = #{prevActivity.slibling_id} WHERE id = #{id};
 ​
 UPDATE activity SET prev_id = #{prev_id} WHERE id = #{id};
 UPDATE activity SET sibling_id = #{id} WHERE id = #{prev_id};
Copy the code

moveBefore

Drag a resource to the top of the list, and the front end passes in the resource’s ID and its sibling_id. The back-end updates data based on the ID and sibling_id as follows:

1. Query the current resource data (curActivity) based on the id

curActivity : SELECT * FROM activity WHERE id = #{id};
Copy the code

Update resource Pointers before and after curActivity

UPDATE activity SET prev_id = #{curActivity.prev_id} WHERE id = #{curActivity.sibling_id};
UPDATE activity SET sibling_id = #{curActivity.sibling_id} WHERE id = #{curActivity.prev_id};
Copy the code

Update the prev_id of the next resource based on sibling_id

UPDATE activity SET prev_id = #{id} WHERE id = #{slibling_id};
Copy the code

Update curActivity’s slibling_id

UPDATE activity SET slibling_id = #{slibling_id} WHERE id = #{id};
Copy the code

As you can see, before and after Pointers only require a maximum of six UPDATE statements per UPDATE, and are row locks that have less impact on table performance than “Scenario 1” table locks.

defects

The problem with using a linked list pointer is that it is only suitable for “full query” scenarios and cannot be paginated like position. If you want to paginated query, you need to continuously query the subsequent data in the database.

To improve the

Is there a way to make double-pointer lists support sort paging?

There is a crude solution: use a floating-point field position, update position to = (position of the previous data + position of the next data) / 2 as you move data, and do floating-point division. In this way, the query can still be sorted by the position field.

The finch’s plan – guess

We look at the interface of the finch and find that the interface is called when the document order is adjusted:

PUT /api/catalog_nodes

The parameters passed in are as follows:

{
    "book_id":10922139,
    "format":"list",
    "action":"moveAfter",
    "target_uuid":"88bJcaqwdyEx2_KN",
    "node_uuid":"yJAhTFEUOfOVEFOo"
}
Copy the code

Action; target_uuid; node_uuid; prev_id; prev_id; Prev_uuid and sibling_uuid are also returned, as shown in the following figure:

As you can see, the order of the data returned by the interface is the same as the order displayed on our page.

As we know from the previous, linked list storage data, not suitable for paging query, so the language sparrow using the scenario is “query all documents”, personal guess is sorted in memory and returned to the front end.

conclusion

Two back-end implementations of drag sort are introduced:

1. Array structure scheme: Poor insert and update performance, high query performance

2, bidirectional linked list scheme: insert, update performance is high, query to do extra processing