The need for what is called Fractional Indexing arises if a list of items can be arbitrarily re-ordered and we want an item to have a key representing its position in the order.
The canonical example is a todo-list where a user may change the order (priority) of items at whim.
We start with giving each item a number as a key and use the following algorithm for a new or moved item:
Step two has a problem which cannot be avoided: each step moves the least significant bit to the right by one. As an example, consider repeatedly inserting between the first and second element of a list which starts with the keys 5 and 7. We get for the first two keys:
```
5 7 -> 5 6 -> 5 5+1/2 -> 5 5+1/4 -> 5 5+1/8 ...
``` The $1/{2^N}$ is coded by a 1-bit which moves ever further to the right.
If the insert position degenerates to be always the same for some unforseeable reason, you need n bits of precision after n insertions. Double values provided by most programming languages have a 52 bit mantissa, which means you get rounding errors the latest after 52 insertions. Which is not a lot.
Using infinite precision decimals does not make it much better because the key requires at least n/8 bytes after n insertions. After 1024 insertions which, by bad luck, happen on the same position, the key has a length of at least 128 bytes.
There is no remedy if the general case is considered. If users work with a list where the creation of each single item is a manual step, it is hard to imagine they have 1000 insertions at the same place. Yet if it is a todo-list maintained over a few years, the 52 bit mantissa of a double value may actually become a problem.
And it is a problem of the ugly kind. The program may actually work perfectly for months, even years. And when it starts to fail, the failure is subtle as items may or may not be sorted in the wrong place, depending on the "random" order how the comparison of identical keys spits them out.
I spend three days from noticing that I want a manually maintained sort key which does not require re-numbering whenever an item gets inserted between two others, over learning that it is called fractional indexing, reading about it, implementing it myself for the general case, to seeing live from test output how fast degenerate insertion gets bad to writing this piece, finally accepting defeat.
The original reason I wanted to avoid re-numbering is that it causes a brief but noticable data-reload in the app I am writing.
How to chose N? Using N=1 means any insert operation has to renumber all following items, the case I wanted to avoid in the first place. The larger the N gets, the longer it takes between re-numbering with pros and cons.
Hmmm?
The figma blog somewhat casually brushes over the index length problem saying:
The first drawback (index length) isn’t a concern for us since we don’t need to order huge numbers of elements. The number of reordering operations is bounded by user activity in practice, and normal usage patterns never generate prohibitively-large index lengths.While I tend to agree, this somewhat reminds me of the year 2000 problem or the year 2038 problem. In my case, the app shall operate on the same data structure potentially for years, and while arbitrary re-ordering is expected, new items tend to be added to the front, which will certainly grow the keys near the front of the list. Adding only a handful of items per day to the front over a year makes already 1825 insertions or, worst case over 200 bytes for the key.
Given modern hardware, these will be handled without problems for a long some time, until it suddenly wrecks somewhere. For my little app, used by only few people, this will not be the end of the world, but it is the general attitude towards good software which is not mine. I wish there were an efficient solution where I would not need to rely on the specific circumstances of the typical use of the app for it not to crash.