[loumf]

Here is the answer for Trello: each card and list has a field called “pos” which is a number. The initial values are spread out (e.g. 1000, 2000, 3000) and then when you move a card, it takes on the average of the two adjacent cards.

So, if I move the 3rd card to the 2nd position, its “pos” becomes 1500. This means it doesn’t have to constantly renumber the cards -- but, every once and a while, the server does reorder the “pos” fields for a whole list and send the new values down the socket.

[somat]

I was going to guess linked lists/graphs as that is my goto for extremely flexible local structure. But the sparse array is probably better, relational databases hate linked lists.

[GlacierFox]

Thank you for this, that's so simple and I'd never stumble on that solution which is embarrassing haha. How do you know the Trello internals by the way? You work there?

[loumf]

Yes. I worked there. But it’s described in the API

[neucoas]

This concept is called "lexorank"

[GlacierFox]

Well, not quite. Although lexorank is similar, the mothod described above is not lexorank. Lexorank uses strings and buckets and a completely different set of math to work it out.