Title :
The adaptive radix tree: ARTful indexing for main-memory databases
Author :
Leis, V. ; Kemper, Alfons ; Neumann, Tobias
Author_Institution :
Fak. fur Inf., Tech. Univ. Munchen, Garching, Germany
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.
Keywords :
cache storage; database indexing; table lookup; tree data structures; tree searching; ART performance; ARTful indexing; RAM; adaptive radix tree; balanced binary search tree; deletion; hash table; in-memory data structure; index structure performance; insertion; internal node; lookup performance; main memory index; main-memory database system; min memory capacity; on-CPU cache utilization; point query; prefix lookup; range scan; read-only search tree; sorted order data; worst-case space consumption; Arrays; Indexing; Subspace constraints; Vegetation;
Conference_Titel :
Data Engineering (ICDE), 2013 IEEE 29th International Conference on
Conference_Location :
Brisbane, QLD
Print_ISBN :
978-1-4673-4909-3
Electronic_ISBN :
1063-6382
DOI :
10.1109/ICDE.2013.6544812