Hands-On Data Structures and Algorithms with Rust

Wrap up

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 ...