Mathematicians crack the code behind how databases organize data
Researchers have discovered a fundamental mathematical pattern that explains how B-trees—the data structures powering most databases—evolve as new information is added. The finding could help engineers optimize database performance and predict how systems will behave under real-world conditions, potentially reducing costly infrastructure upgrades.
Originaltitel: A Bijection for the Evolution of B-Trees
<p>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.</p>