Solution: make index a string (because strings, in essence, have infinite “arbitrary precision”). Or if you use an int, increment index by 100 instead of 1.
The performance problem is this: there is no “in between” values between two sorted items.
item index
-----------------
gizmo 1
<<------ Oh no! no room between 1 and 2.
This requires incrementing _every_ item after it
gadget 2
gear 3
toolkit 4
box 5
Instead, do like this (better solution below):
item index
-----------------
gizmo 100
<<------ Sweet :). I can re-order 99 (!) items here
without having to change anything else
gadget 200
gear 300
toolkit 400
box 500
Even better: here is how Jira solves this problem. Their “rank” (what you call index) is a string value that allows a ton of breathing room in between ranked items.
Here is a real example of a jira database I work with
id | jira_rank
---------+------------
AP-2405 | 0|hzztxk:
ES-213 | 0|hzztxs:
AP-2660 | 0|hzztzc:
AP-2688 | 0|hzztzk:
AP-2643 | 0|hzztzs:
AP-2208 | 0|hzztzw:
AP-2700 | 0|hzztzy:
AP-2702 | 0|hzztzz:
AP-2411 | 0|hzztzz:i
AP-2440 | 0|hzztzz:r
Notice this example hzztzz:i. The advantage of a string rank is that you run out of room between two items, you still don’t have to re-rank anything else. You just start appending more characters to the string to narrow down focus.
EDIT: as mentioned in the comments, you can’t insert anything between 0|hzztzz: and 0|hzztzz:a. I guess that’s why I see jira’s database automatically append :i at the end regularly instead of :a to avoid that scenario. If you really want to prevent problems, then I think you can change your algorithm so that (for example) every time you would insert :a at the end, you instead insert :ai. This way you logically guarantee that no ranking will end with the letter a — which should mean that you will always have “room” to insert more items without having to re-order anything.