There is no problem with the interpolated rank approach. Simply define your own numbering system based on variable length bit vectors representing binary fractions between 0 and 1 without trailing zeros. The binary point is to the left of the first digit.
The only inconvenience of this system is that the minimum possible key is 0, given by an empty bit vector. Therefore, you only use this if you are sure that the related item will forever be the first item in the list. As a rule, just give the first element of the key 1. This is equivalent to 1/2, so random inserts in the range (0..1) will tend to minimize the use of bits. To interpolate an element before and after,
01 < newly interpolated = 1/4 1 11 < newly interpolated = 3/4
To interpolate again:
001 < newly interpolated = 1/8 01 011 < newly interpolated = 3/8 1 101 < newly interpolated = 5/8 11 111 < newly interpolated = 7/8
Note that if you want, you can omit saving the final 1! All keys (except 0, which you usually don’t use) end with 1, so saving is invalid.
Comparing binary fractions is very similar to a lexical comparison: 0 <1, and the first bit difference in scan mode from left to right indicates that it is less. If there are no differences, i.e. One vector is a strict prefix of the other, the shorter it is smaller.
Using these rules, it’s quite simple to come up with an algorithm that takes two bit vectors and calculates a result that is roughly (or precisely in some cases) between them. Just add bit strings and shift 1 to the right, discard unnecessary trailing bits, i.e. Take the middle of the two to break the range between.
In the above example, if the deletion remains with us:
01 111
and we need to interpolate them, add 01(0) and and 111 to get 1.001 , then go to get 1001 . This works great as an interpolator. But note that the final 1 unnecessarily makes it longer than any of the operands. An easy optimization is to reset the final bit 1 along with trailing zeros to get just 1 . Of course, 1 is about halfway between what we hope.
Of course, if you make many inserts in one place (for example, sequential inserts at the beginning of the list, for example), the bit vectors will be long. This is the same phenomenon as inserting at the same point in a binary tree. It grows long and tough. To fix this, you must “rebalance” during synchronization by renumbering with the shortest possible bit vectors, for example. for 14 you would use the above sequence.
Adding
Although I have not tried, for the keys that I described, enough for the row type of the Postgres column. I have to check that the sort order is correct.
Also, the same reasoning works fine with base-k numbers for any k>=2 . The first item gets the key k/2 . There is also a simple optimization that prevents the very common cases of adding and adding elements at the end and front, respectively, because they call keys of length O (n). It supports O (log n) for these cases (although when inserted into the same place, they can still internally create O (p) keys after p inserts). I will let you do it. With k = 256, you can use infinite lengths of byte strings. In SQL, I believe you need varbinary(max) . SQL provides the correct lexicographic sort order. Implementing interpolation operations is easy if you have a BigInteger package similar to Java. If you like human-readable data, you can convert byte strings, for example. hexadecimal strings (0-9a-f) and save them. Then the correct sort order of the UTF8 string is correct.