> It's a cool idea, but you have to keep in mind that binary searches are not optimal for b-tree nodes unless the node is really big. If you have a smaller node, < 32 or 64 elements, a simple linear search is faster. The reason has something to do with processor cache, branch mis-prediction, and pipelining.

I've heard that—and iirc Rust's BTreeMap type uses linear search—but does this depend on the type of key? Easy for me to see how that might be true for a BTreeMap<u64, V> but not a BTreeMap<String, V>. In the latter case, there's a pointer to chase for each comparison (and more/variable data to process; SIMD over multiple keys doesn't seem likely).