Optimal algorithm for task list (priority queue). How to add an entry to the middle of the queue without shifting it?

Question

PHP

Greetings colleagues, the other day, when developing a todo list, a problem arose that has not yet been resolved. Task:
There is a list of numbered entries (actually there are several of them, but for simplicity we will take one), the numbering determines the priority of tasks. Suppose we have an array of 5 tasks [0, 1, 2, 3, 4], we need to add one more task to the 2nd most important place, as a result, everything that started with the 1st is shifted by +1. The problem begins with the fact that we must immediately write data to the database, in this case, only 1 action will make 1 insert and 5 updates. Now let's say we have a list of 100 entries and 2000 active customers. One move of a task via drag'n'drop entails several tens of rewrites in the database, if not thousands.
There would be no problem if the application was spinning on the client and by clicking "Save" there would be some kind of optimized rewriting, but the application should be native, without any extra buttons, you need to write directly to the database.
Crutches-options:
1) The new index will be the average value between the inserted numbers (between 3 and 4, 3.5 will be inserted. And between 3 and 3.5 -> 3.25, etc.). When requesting an array, there will be ranking in ascending order, but such floats (56.21875) will heavily clog the base and you will have to write a crutch to overwrite these indices once a day with normal ones
2) The index will be of the "I follow" type. We issue arbitrary id's to records, then we say with a separate parameter after whom this record should go. In this case, by "injecting" a record into the middle of a queue of million records, we will make only 2 changes to the database - the one who was inserted, and the one who needs to update the link. But here, again, you have to write some kind of crutch solution to build these relationships during rendering, to generate ID hashes, which is no better than floats.
3) Do 50, 100, etc. update'ov in the database

Answer 1

0) I correctly understood that in the first table we store ordinary records with id. In the second, for each client, we store an array according to the table of the form

array(
  'priority0' => 'id345',
  'priority1' => 'id63452',
  'priority2' => 'id23',
  'priority3' => 'id9123'
)

And when changing the priority of any of the tasks, we overwrite this entire array? From the point of view of ease of code, a good option, but the arrays will be quite large, because in a real situation there are several tables, the number of tasks for each person can reach several hundred. It's easy to write, but I think there will be performance problems. I'm wondering, after all, this task was solved in the same Asana, and, in principle, in any tasktracker service. It seems to me that there is some kind of mathematical model that just solves this problem.
thirteen ---
2. In words, the option is beautiful, but the implementation in the code is not yet clear. Apparently it should be foreach which will form a new ordered array. Given that we have 500 tasks, this will be 500 cycles, while it is difficult to say exactly how the matching will go, there are some doubts that it will be super fast. I think how competitive it is in terms of performance with other options.

Answer 2

can change the data structure - store a record-key in one table, and store a matrix or dictionary with key-priority pairs in another table for each client (the key is unique for the task, which means we will get a comparison of the task with the priority). Each addition of a record/task entails adding a record to table 1 and changing a record in table 2. Changing the priority of a task entails only one change in a record in table 2. Sorting and matching takes place on the client side, a ready-made new dictionary is sent to the server. Each request will weigh more, but what do we need 1 request of 15 key-priority pairs for the average user?
1 your option, IMHO, a spherical crutch, preserved in a liquid vacuum
2 option is beautiful, but it needs to be worked out and calculated
Option 3 is not an option at all)

Answer 3

Set priorities as (0,100,200,300,400). If you need to insert a task between two others, set its priority as the average, rounded up to an integer. If there are a lot of records and the resulting number coincides with one of the neighboring ones, recalculate the priorities.

Answer 4

https://jsfiddle.net/8yz4ub61/1/

Answer 5

https://jsfiddle.net/xwe6h94p/