B2-Tree: Page-Based String Indexing in Concurrent Environments

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

Full description

Saved in:
Bibliographic Details
Published in:Datenbank-Spektrum : Zeitschrift für Datenbanktechnologie : Organ der Fachgruppe Datenbanken der Gesellschaft für Informatik e.V 2022, Vol.22 (1), p.11-22
Main Authors: Schmeißer, Josef, Schüle, Maximilian E., Leis, Viktor, Neumann, Thomas, Kemper, Alfons
Format: Article
Language:English
Subjects:
Computer Science
Computer Systems Organization and Communication Networks
Data Mining and Knowledge Discovery
Data Structures and Information Theory
Database Management
Information Storage and Retrieval
IT in Business
Nodes
Performance evaluation
Schwerpunktbeitrag
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 2 -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 2 -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 shown in our performance evaluation. As a result, the B 2 -tree answers point queries considerably faster. Concurrent access to B 2 -tree pages are managed by an optimistic locking protocol which results in high utilization of the available hardware resources. Our evaluation of read-write workloads attests more than competitive performance for the B 2 -tree compared to a traditional B+-tree.
ISSN:1618-2162
1610-1995
DOI:10.1007/s13222-022-00409-y