I've run into this problem when keeping a single large (100000+) list sorted. In my case it was very important not to change the sort value on rows that didn't need to.
I had considered most of the solutions listed in the article except for the true fraction method. I believe that solution was explored by the author as they thought floating points were somehow solving a problem that couldn't be solved by integers. I settled on an approach that is essentially Solution 2 but using integers instead, each time bisecting the other two integers. The important aspect is that when inserting at the head or tail of the list, you bisect between MININT (-2^63) or MAXINT (2^63-1) respectively.
have you considered using a string and have them sort lexographically? To insert, you have to create a new string that sorts between the two, which this library proposes an algorithm for: https://github.com/fasiha/mudderjs
This was my thought, too. Use a point-based versioning-like scheme as a string (1.1.25, 1.1.26, 1.1.26.1, 1.2, etc). You will have to worry about adding prefixed 0s, though, as powers of ten are increased if you want it to sort correctly, and of course there is presumably a hard-limit on the size of the string.
It might be possible to have a table that keys to the first that has a level and a value. For 1.1.26.1 above, it would have the rows (1, 1), (2, 1), (3, 26), (4, 1) (with keys to the table rows). Not sure exactly how to write the sql to join it all together and sort it, but it seems possible, at least if you have some known maximum number of levels.
if you use the full unicode space as alphabets, you can probably get a lot of mileage out of just having a 255 char column (or bigger, if expecting a large number of items constantly changing). Most databases will have a inbuilt way to lexographically sort text, and so you won't have to do anything extra. The smarts is in the computation of the ordering string.
I had considered most of the solutions listed in the article except for the true fraction method. I believe that solution was explored by the author as they thought floating points were somehow solving a problem that couldn't be solved by integers. I settled on an approach that is essentially Solution 2 but using integers instead, each time bisecting the other two integers. The important aspect is that when inserting at the head or tail of the list, you bisect between MININT (-2^63) or MAXINT (2^63-1) respectively.