How bbtree, a drop-in replacement for std's BTreeMap, cuts cache misses, instructions and cache coherence traffic, and how it is kept correct.