Indexing: Order Statistic Tree / SkipList with span counts

[Angramme]

Summary

A concurrent data structure like SkipList that can also be accessed by index (a method to get i-th smallest key) would prove very useful in many scenarios.

Motivation

In many cases it is very useful to be able to access the i-th smallest element of the SkipList. For instance in a GUI where we want to display the skiplist as a table, we need the ability to index by row.
Many applications such as Order Book tracking in trading systems benefit from the ability to access the i-th smallest key in a data structure for pricing and execution algorithms.

Detailed design

Disclaimer: I do not know the codebase in detail :)

Basic idea revolves around adding an additional counter for each Atomic Pointer in the Tower data structure

#[repr(C)]
struct TowerCounted<K, V> {
    pointers: [(Atomic<Node<K, V>>, AtomicUsize); 0],
}

This counter would keep track of the count of nodes that are located between this tower's node and the node it points to (excluding that node). Each non-updating insertion or deletion in the data structure would then require an update of the O(log n) counters. To be able to track down the counters to update in each level, the search_position function could be extended to provide a trace of the exact pointers used at each level. Most probably this would involve storing around O(log n) Node Atomic pointers, we could then retrieve the counter by accessing the corresponding pointers tower at the correct level. We could then update the counters depending on the scenario. Exact implementation TBD.

Avoiding Overhead

One could extend the SkipList structure with a const generic bool INDEXED. The motivation for doing so would be to allow users who do not need the indexing feature to opt out of it, reducing the overhead. One could define type SkipList = SkipListGeneric<false> and SkipListIndexed = SkipListGeneric<true> .

Example usage:

scope(|s| {
    // Insert entries into the map from multiple threads.

    s.insert(135, 22);
    s.insert(146, 47);
    s.insert(1000005 234);

    assert_eq!(s.get(146).unwrap().value(), &22);
    
    assert_eq!(s.get_index(1).unwrap().key(), &146);
}).unwrap();

Drawbacks

• Extra implementation complexity

Alternatives

One additional possibility is to create a new structure akin to a Order Statistic Tree. This would involve more work and would result in some code duplication.

Unresolved questions

• Exact implementation of tracking the counters to update.
• Exact implementation of the opt-in opt-out generic.
• Everything else, this proposal is very rough.