A bijection for the evolution of $B$-trees
<|reference_start|>A bijection for the evolution of $B$-trees: 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.<|reference_end|>
@article{burghart2024a,
    title={A bijection for the evolution of $B$-trees},
    author={Fabian Burghart, Stephan Wagner},
    journal={arXiv preprint arXiv:2406.06359},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.06359},
    primaryClass={math.CO cs.DS math.PR}
}