Storing an ordered list in database

To store an ordered list in database, the simplest way is to assign a number to each row. However, that means reordering requires updating multiple rows.

name  | order
alice | 1
          <------------- set to 2
bob   | 2 <- set to 3   |
chris | 3  -------------

A solution would be leaving “spaces” between numbers,

name  | order
alice | 100
          <------- set to 150
bob   | 200       |
chris | 300  -----

but it does not solve the problem when you insert a row between 99 and 100. Another solution would be using floating point, but that has precision problem.

Sort using string

Sorting by string solves the problem. The idea is, there can be infinity number of “gap” between strings, because the length of string is infinity (or as long as your data type support). For example, between “a” and “b” there is “aa”.

name  | order
alice | a
          <----- set to "aa"
bob   | b       |
chris | c  -----

I made a little library to create strings for sorting like this, Sortee. It’s written in Haskell but porting it to any other language shouldn’t be that difficult.

Asking for a string between strings is simple:

>:t between
between :: Maybe Sortee -> Maybe Sortee -> Maybe Sortee
> between (Just $ Sortee "a") (Just $ Sortee "c")
Just (Sortee "b")
-- There are IsString instances for convenience:
> between "a" "c"
Just (Sortee "b")
> between "a" "b"
Just (Sortee "aU")

If you do not have upper / lower reference, it’s possible to pass Nothing:

> between Nothing "a"
Just (Sortee "I")
> between "a" Nothing
Just (Sortee "n")
> between Nothing Nothing
Just (Sortee "U")

The limitation with this approach is, not every string is valid, for example there isn’t any space between “a” and “a0”. between never returns strings that cannot be further processed, and it fails if you have such string.

> between Nothing "1"
Just (Sortee "0U")
> between "b" "b1"
Just (Sortee "b0U")
> between "b" "b0"