Hands-On Data Structures and Algorithms with Rust

BTreeMap and BTreeSet

Talking about B-Trees in Chapter 5, Robust Trees, their purpose is storing key-value pairs—ideal for a map-type data structure. Their ability to find and retrieve these pairs is achieved by effectively minimizing the number of comparisons required to get to (or rule out) a key. Additionally, a tree keeps the keys in order, which means iteration is going to be implicitly ordered. Compared to HashMap, this can be an advantage since it skips a potentially expensive step.

Since—just like HashSet—BTreeSet simply uses BTreeMap with an empty value (only the key) underneath, only the latter is discussed in this section since the working is assumed to be the same. Again, let's start with the architecture.