How to store a sorted list in Google Firestore

Question

How would you store an ordered list of N items in Google Firestore?

For example, a todo list. I had a couple of ideas but neither seem that smart.

You could put a 'position' key on the item but that would require updating all of the items' position value when one changes.

You could store them in a sorted array and do some splicing to resort before persisting.

I'd be keen to hear what is the recommend approach.

Answer 1

The approach I use works without updating all the documents, but only the one you are ordering using a position property (This is the way Trello lists work I believe)

Suppose you have a list with 5 elements:

- A (position: 1)
- B (position: 2)
- C (position: 3)
- D (position: 4)
- E (position: 5)

Let's say you drag C between A and B, (this is the easiest calculation) you would get:

- A (position: 1)
- C (old position: 3, new?) <---- you need to calculate this new position
- B (position: 2)
- D (position: 4)
- E (position: 5)

At this point, you just need to know the previous element position and the next element position:

(A + B) / 2 = 1.5

1.5 is the new position for "C"

- A (position: 1)
- C (position: 1.5) <--- update only this doc in your db
- B (position: 2)
- D (position: 4)
- E (position: 5)

Let's move C again, to the latest position. You don't have a next element, in this case you do last + 0.5:

- A (position: 1)
- B (position: 2)
- D (position: 4)
- E (position: 5)
- C (new position: 5.5)

Last, if you don't have a previous element... first you check if you have a next element, in that case you do: next / 2 otherwise, set it to 0.5.

Let's move C to the top:

- C (new position: A / 2 = 0.5)
- A (position: 1)
- B (position: 2)
- D (position: 4)
- E (position: 5)

Eventually, you would divide float numbers, but it's not a problem because they are nearly infinite. (depending on the language you use).