The mutable inverted index currently uses a Vec as a container for ids, this means that, while it is expensive to keep adding random values to it, it is still good to binary-search over it.

From the history, we can see that it was switched from BTreeSet to Vec in the past. However, indexing with Vec means that we have to shift elements all over the place every time we insert a new id which is lower than the max in the list. This creates a bottleneck directly on ingestion, not during optimization, which "breaks" the mental model of ingestion being separated from optimization because it's supposed to be quick.

Since changing the container is a small (but big impact) change, I've ran the following experiment:

// For upsert
bfb -n 5000000 --text-payloads --text-payload-length 100 --vectors-per-point 0 --max-id 2000000

// For queries
bfb -n 100000 --text-payloads --text-payload-length 100 --vectors-per-point 0 --skip-create --skip-upload --scroll

These were the results: