Logo des Repositoriums
 
Textdokument

B²-Tree

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2021

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Quelle

Verlag

Gesellschaft für Informatik, Bonn

Zusammenfassung

Recently proposed index structures, that combine trie-based and comparison-based search mechanisms, considerably improve retrieval throughput for in-memory database systems. However, most of these index structures allocate small memory chunks when required. This stands in contrast to block-based index structures, that are necessary for disk-accesses of beyond main-memory database systems such as Umbra. We therefore present the B²-tree. The outer structure is identical to that of an ordinary B+-tree. It still stores elements in a dense array in sorted order, enabling efficient range scan operations. However, B²-tree is composed of multiple trees, each page integrates another trie-based search tree, which is used to determine a small memory region where a sought entry may be found. An embedded tree thereby consists of decision nodes, which operate on a single byte at a time, and span nodes, which are used to store common prefixes. This architecture usually accesses fewer cache lines than a vanilla B+-tree as our performance evaluation proved. As a result, the B²-tree is able to answer point queries considerably faster.

Beschreibung

Schmeißer, Josef; Schüle, Maximilian E.; Leis, Viktor; Neumann, Thomas; Kemper, Alfons (2021): B²-Tree. BTW 2021. DOI: 10.18420/btw2021-02. Gesellschaft für Informatik, Bonn. PISSN: 1617-5468. ISBN: 978-3-88579-705-0. pp. 39-58. Database Technology. Dresden. 13.-17. September 2021

Zitierform

Tags