Researchers crack the mathematical code behind database tree structures
Computer scientists have discovered a new way to understand how B-trees—the fundamental data structures powering most databases—evolve as data is added. The breakthrough could help engineers optimize database performance and design more efficient storage systems for the massive datasets that power modern AI and cloud computing.
Originaltitel: 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.