On the histories of B-trees
Abstract
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.
Fields of Study & Subjects
Advanced Combinatorial Mathematics
Algorithms and Data Compression
semigroups and automata theory
Publication details
- Journal / source
- Theoretical Computer Science
- Volume
- 1070
- Pages
- 115821–115821
- Publication date
- 18 February 2026
- Language
- EN