The adaptive radix tree: ARTful indexing for main-memory databases
Leis V, Kemper A, Neumann T (2013)
Publication Type: Conference contribution
Publication year: 2013
Pages Range: 38-49
Conference Proceedings Title: Proceedings - International Conference on Data Engineering
ISBN: 9781467349086
DOI: 10.1109/ICDE.2013.6544812
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. © 2013 IEEE.
Authors with CRIS profile
Involved external institutions
Germany (DE)How to cite
APA:
Leis, V., Kemper, A., & Neumann, T. (2013). The adaptive radix tree: ARTful indexing for main-memory databases. In Proceedings - International Conference on Data Engineering (pp. 38-49).
MLA:
Leis, Viktor, Alfons Kemper, and Thomas Neumann. "The adaptive radix tree: ARTful indexing for main-memory databases." Proceedings of the 29th International Conference on Data Engineering, ICDE 2013 2013. 38-49.
BibTeX: Download