Language and content

The fringe of a B-tree with parameter m is considered as a particular Pólya urn with m colors. More precisely, the asymptotic behaviour of this fringe, when the number of stored keys tends to infinity, is studied through the composition vector of the fringe nodes. We establish its typical behaviour together with the fluctuations around it. The well known phase transition in Pólya urns has the following effect on B-trees: for m ≤ 59, the fluctuations are asymptotically Gaussian, though for m ≥ 60, the composition vector is oscillating; after scaling, the fluctuations of such an urn strongly converge to a random variable W. This limit is C-valued and it does not seem to follow a classical law. Several properties of W are shown: existence of exponential moments, characterization of its distribution as the solution of a smoothing equation, existence of a density relatively to the Lebesgue measure on C, support of W