This stuff is fun to play with. I implemented a Rust version of fractional indexing based on another of Evan’s blog posts.
Explanation here: https://news.ycombinator.com/item?id=33764956. Thanks!
When I read about the problem, I imagined using the mediant to calculate “between”. I think that mediant of $value and 1/1 would work for “after” and mediant of $value and 0/1 would work for “before”.
There must be a requirement I’m missing, though!
mediant: https://en.wikipedia.org/wiki/Mediant_(mathematics)
In general some approaches should be better than others depending on how inserts are distributed — I think my approach is optimal when inserts are made at random (I haven’t proved this), but in practice it may be common for a bunch of things to be inserted in sequence for some applications. In those cases, there are more space-optimal approaches.