B-Trees are awesome. They are widely used in real-world applications, their implementation in Rust is not all that complex, and they maintain a great performance regardless of insertion order. Furthermore, the tree's order can dramatically improve performance by decreasing the tree's height. It is recommended to estimate the number of key-value pairs beforehand and adjust the order accordingly.
As a benchmark, let's evaluate the trees by inserting 100,000 unsorted, unique elements, and retrieving them using find(). Dot size represents the variance, while the values shown along the y axis are nanoseconds:
The chart output of Unsorted ...
