  A $B$-tree is a type of search tree where every node (except possibly for the
root) contains between $m$ and $2m$ keys for some positive integer $m$, and all
leaves have the same distance to the root. We study sequences of $B$-trees that
can arise from successively inserting keys, and in particular present a
bijection between such sequences (which we call histories) and a special type
of increasing trees. We describe the set of permutations for the keys that
belong to a given history, and also show how to use this bijection to analyse
statistics associated with $B$-trees.
