indexset: BTreeSet and BTreeMap replacement with O(1) get by position and faster iteration

91 points brurucy

I often got frustrated by how not-as-fast-I-thought iterating through the standard library BTree is, and how extremely slow it is to get the i-th element.

So, after a month of work, I'd like to showcase an alternative to the standard library BTree that is:

  1. Twice as fast to iterate
  2. 3400x times faster to get the i-th element
  3. Approximately 10% faster for lookups

https://github.com/brurucy/indexset

But of course, it is not an improvement in all fronts. Insertions are approximately two times slower.

All in all, if your usage of BTrees is more read-heavy, you might get some good speed gains from my crate.