B²-Tree
| dc.contributor.author | Schmeißer, Josef | |
| dc.contributor.author | Schüle, Maximilian E. | |
| dc.contributor.author | Leis, Viktor | |
| dc.contributor.author | Neumann, Thomas | |
| dc.contributor.author | Kemper, Alfons | |
| dc.contributor.editor | Kai-Uwe Sattler | |
| dc.contributor.editor | Melanie Herschel | |
| dc.contributor.editor | Wolfgang Lehner | |
| dc.date.accessioned | 2021-03-16T07:57:11Z | |
| dc.date.available | 2021-03-16T07:57:11Z | |
| dc.date.issued | 2021 | |
| dc.description.abstract | 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. | en |
| dc.identifier.doi | 10.18420/btw2021-02 | |
| dc.identifier.isbn | 978-3-88579-705-0 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/35803 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik, Bonn | |
| dc.relation.ispartof | BTW 2021 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-311 | |
| dc.subject | Indexing | |
| dc.subject | B-tree | |
| dc.subject | String | |
| dc.title | B²-Tree | en |
| dc.title.subtitle | Cache-Friendly String Indexing within B-Trees | en |
| gi.citation.endPage | 58 | |
| gi.citation.startPage | 39 | |
| gi.conference.date | 13.-17. September 2021 | |
| gi.conference.location | Dresden | |
| gi.conference.sessiontitle | Database Technology |
Dateien
Originalbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
- Name:
- A1-2.pdf
- Größe:
- 613.22 KB
- Format:
- Adobe Portable Document Format