Best representation of an ordered list in a database?

Question

I know that this sort of goes against the principles of a relational database but let me describe the situation.

I have a page where the user will place a number of items.

 ________________
| -Item1         |
| -Item2         |
| -Item3         |
| -Item4         |
|________________|

These items have must stay in a the order the user gives them. However this order may be changed an arbitrary number of times by the user.

 ________________
| -Item1         |
| -Item4         |
| -Item2         |
| -Item3         |
|________________|

Approach 1

My original thought was to give the items an index to represent thier place in the list

Page           Item
-----------    ---------------
FK | pid       FK | pid 
   | name      PK | iid 
                  | index
                  | content 

With this solution you can select items where pid = Page.pid and order by index which is convenient. However every time you change the order you have to change anywhere between one other item (best case) and all the other items (worst case).

Approach 2

I also considered making a "linked list" like data structure where each item points to the next item in the list.

Page           Item
-----------    ---------------
FK | pid       FK | pid 
   | name      PK | iid 
                  | next
                  | content 

This potentially makes changing the order less expensive but we would have to rely on front end programming to extract the order.

Is there an approach that I haven't thought of? Please let me know.

Answer 1

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.