On the histories of B-trees

A B -tree is a type of search tree where every node (except possibly for the root) contains between m and 2 m 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.