A bijection for the evolution of $B$-trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914830758182912 |
|---|---|
| author | Burghart, Fabian Wagner, Stephan |
| author_facet | Burghart, Fabian Wagner, Stephan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_06359 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A bijection for the evolution of $B$-trees Burghart, Fabian Wagner, Stephan Combinatorics Data Structures and Algorithms Probability 05A19 (Primary), 68P10, 60C05, 05A05, 05A16 (Secondary) 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. |
| title | A bijection for the evolution of $B$-trees |
| topic | Combinatorics Data Structures and Algorithms Probability 05A19 (Primary), 68P10, 60C05, 05A05, 05A16 (Secondary) |
| url | https://arxiv.org/abs/2406.06359 |