There’s another solution that I don’t think I’ve seen here that doesn’t require a background job or reading through the entire data set, but it does involve doing multiple reads from the database’s data structures. But then as soon as your data are inserted, you can start querying your index, which might be a desirable property.
The basic idea is to persist a skip list in FDB. Each level of the skip list is kept as a contiguous range, and the keys in each level are the indexed values (probably serialized with, say FDB tuples) and the values are integers encoding how many elements are under that level of the skip list. To determine the rank of any single item, you scan through one level of the skip list, adding up sizes until you get to a sign-post key that is greater than the key you are looking for. Then you go down one level, starting from your previous key and query additional elements. So, to query, this requires one range-read per level in your skip list. To update, you find the right element to update in each level, and add 1 to the value associated with each key in the level. To do splits, you need to recalculate the number of items under that level, but that’s not so bad. So it ends up being one read and one write per level in the skip list (with some of those reads being range reads).
I think that makes sense. It’s not the most straightforward data structure to implement (and there are optimizations that can be made to increase its tolerance contention that are somewhat subtle as well as additional optimizations to make it more likely to hit the client-side cache). I believe that there is a C# implementation that @KrzysFR wrote up (BSD licensed) of something along the lines of what is outlined above, though I don’t know how up-to-date that is kept.