Show simple item record

dc.contributor.authorSchmeißer, Josef
dc.contributor.authorSchüle, Maximilian E.
dc.contributor.authorLeis, Viktor
dc.contributor.authorNeumann, Thomas
dc.contributor.authorKemper, Alfons
dc.contributor.editorKai-Uwe Sattler
dc.contributor.editorMelanie Herschel
dc.contributor.editorWolfgang Lehner
dc.date.accessioned2021-03-16T07:57:11Z
dc.date.available2021-03-16T07:57:11Z
dc.date.issued2021
dc.identifier.isbn978-3-88579-705-0
dc.identifier.issn1617-5468
dc.identifier.urihttp://dl.gi.de/handle/20.500.12116/35803
dc.description.abstractRecently 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.en
dc.language.isoen
dc.publisherGesellschaft für Informatik, Bonn
dc.relation.ispartofBTW 2021
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-311
dc.subjectIndexing
dc.subjectB-tree
dc.subjectString
dc.titleB²-Treeen
mci.reference.pages39-58
mci.conference.sessiontitleDatabase Technology
mci.conference.locationDresden
mci.conference.date13.-17. September 2021
dc.identifier.doi10.18420/btw2021-02
dc.title.subtitleCache-Friendly String Indexing within B-Treesen


Files in this item

Thumbnail

Show simple item record