A Bijection for the Evolution of B-Trees

Fabian Burghart, Stephan Wagner

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publication35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
EditorsCécile Mailler, Sebastian Wild
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter10
Pages10:1-10:15
Number of pages15
ISBN (Electronic)978-3-95977-329-4
DOIs
Publication statusPublished - Jul 2024
Event35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) - University of Bath, Bath, United Kingdom
Duration: 17 Jun 202421 Jun 2024
Conference number: 35

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume302

Conference

Conference35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Abbreviated titleAofA
Country/TerritoryUnited Kingdom
CityBath
Period17/06/2421/06/24

Funding

Fabian Burghart: F. Burghart has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska-Curie Grant Agreement No 101034253. Stephan Wagner: Supported by the Swedish research council (VR), grant 2022-04030.

Keywords

  • B-trees
  • asymptotic enumeration
  • bijection
  • histories
  • increasing trees
  • tree statistics

Fingerprint

Dive into the research topics of 'A Bijection for the Evolution of B-Trees'. Together they form a unique fingerprint.

Cite this