The adaptive radix tree: ARTful indexing for main-memory databases

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

343 Scopus citations

Abstract

Main memory capacities have grown up to a point where most databases fit into RAM. For main-memory database systems, index structure performance is a critical bottleneck. Traditional in-memory data structures like balanced binary search trees are not efficient on modern hardware, because they do not optimally utilize on-CPU caches. Hash tables, also often used for main-memory indexes, are fast but only support point queries. To overcome these shortcomings, we present ART, an adaptive radix tree (trie) for efficient indexing in main memory. Its lookup performance surpasses highly tuned, read-only search trees, while supporting very efficient insertions and deletions as well. At the same time, ART is very space efficient and solves the problem of excessive worst-case space consumption, which plagues most radix trees, by adaptively choosing compact and efficient data structures for internal nodes. Even though ART's performance is comparable to hash tables, it maintains the data in sorted order, which enables additional operations like range scan and prefix lookup.

Original languageEnglish
Title of host publicationICDE 2013 - 29th International Conference on Data Engineering
Pages38-49
Number of pages12
DOIs
StatePublished - 2013
Event29th International Conference on Data Engineering, ICDE 2013 - Brisbane, QLD, Australia
Duration: 8 Apr 201311 Apr 2013

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Conference

Conference29th International Conference on Data Engineering, ICDE 2013
Country/TerritoryAustralia
CityBrisbane, QLD
Period8/04/1311/04/13

Fingerprint

Dive into the research topics of 'The adaptive radix tree: ARTful indexing for main-memory databases'. Together they form a unique fingerprint.

Cite this