BTreeSet in Rust
Problem: Binary Search Trees (BST) are theoretically optimal for sorted maps, but they're inefficient in practice. This is mainly due to each element being in its own heap-allocated node, leading to a heap allocation at every insertion and potential cache miss at every comparison.
Solution: B-Trees hold B-1 to 2B-1 elements within a contiguous array in each node. This decreases allocations by a factor of B and increases cache efficiency in searches, but results in a higher average number of comparisons.
Current Implementation: Simple linear search, suitable for small nodes of elements. Future work will further explore selecting the optimal search strategy based on the choice of B, and possibly other factors.
Key Modification: It's a logic error if a key's ordering changes while it's in the map. This error could lead to unspecified behavior, including panic, incorrect results, aborts, memory leaks, and non-termination.
Iterators and Ordering: Iterators obtained from
BTreeMap::iter
, `BTreeMap::values`, orBTreeMap::keys
produce items in key order and take logarithmic time per item returned.