A Bijection for the Evolution of B-Trees

Fabian Burghart; Stephan Wagner

doi:10.4230/LIPICS.AOFA.2024.10

A Bijection for the Evolution of B-Trees

Fabian Burghart, Stephan Wagner

Probability

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Editors	Cécile Mailler, Sebastian Wild
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter	10
Pages	10:1-10:15
Number of pages	15
ISBN (Electronic)	978-3-95977-329-4
DOIs	https://doi.org/10.4230/LIPICS.AOFA.2024.10
Publication status	Published - Jul 2024
Event	35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) - University of Bath, Bath, United Kingdom Duration: 17 Jun 2024 → 21 Jun 2024 Conference number: 35

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Volume	302

Conference

Conference	35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Abbreviated title	AofA
Country/Territory	United Kingdom
City	Bath
Period	17/06/24 → 21/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

Access to Document

10.4230/LIPICS.AOFA.2024.10

pdfFinal published version, 825 KBLicence: CC BY

Cite this

Burghart, F., & Wagner, S. (2024). A Bijection for the Evolution of B-Trees. In C. Mailler, & S. Wild (Eds.), 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) (pp. 10:1-10:15). Article 10 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 302). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.AOFA.2024.10

Burghart, Fabian ; Wagner, Stephan. / A Bijection for the Evolution of B-Trees. 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). editor / Cécile Mailler ; Sebastian Wild. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. pp. 10:1-10:15 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{8a31705eeba545379eb4465e3dde34be,

title = "A Bijection for the Evolution 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 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.",

keywords = "B-trees, asymptotic enumeration, bijection, histories, increasing trees, tree statistics",

author = "Fabian Burghart and Stephan Wagner",

year = "2024",

month = jul,

doi = "10.4230/LIPICS.AOFA.2024.10",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "10:1--10:15",

editor = "C{\'e}cile Mailler and Sebastian Wild",

booktitle = "35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)",

note = "35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), AofA ; Conference date: 17-06-2024 Through 21-06-2024",

}

Burghart, F & Wagner, S 2024, A Bijection for the Evolution of B-Trees. in C Mailler & S Wild (eds), 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)., 10, Leibniz International Proceedings in Informatics (LIPIcs), vol. 302, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 10:1-10:15, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), Bath, United Kingdom, 17/06/24. https://doi.org/10.4230/LIPICS.AOFA.2024.10

A Bijection for the Evolution of B-Trees. / Burghart, Fabian; Wagner, Stephan.
35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). ed. / Cécile Mailler; Sebastian Wild. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. p. 10:1-10:15 10 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 302).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A Bijection for the Evolution of B-Trees

AU - Burghart, Fabian

AU - Wagner, Stephan

N1 - Conference code: 35

PY - 2024/7

Y1 - 2024/7

N2 - 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.

AB - 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.

KW - B-trees

KW - asymptotic enumeration

KW - bijection

KW - histories

KW - increasing trees

KW - tree statistics

UR - http://www.scopus.com/inward/record.url?scp=85199600824&partnerID=8YFLogxK

U2 - 10.4230/LIPICS.AOFA.2024.10

DO - 10.4230/LIPICS.AOFA.2024.10

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 10:1-10:15

BT - 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

A2 - Mailler, Cécile

A2 - Wild, Sebastian

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Y2 - 17 June 2024 through 21 June 2024

ER -

Burghart F, Wagner S. A Bijection for the Evolution of B-Trees. In Mailler C, Wild S, editors, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2024. p. 10:1-10:15. 10. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPICS.AOFA.2024.10

A Bijection for the Evolution of B-Trees

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this