Cuckoo Trie
- 26 October 2021
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM
Abstract
We present the Cuckoo Trie, a fast, memory-efficient ordered index structure. The Cuckoo Trie is designed to have memory-level parallelism---which a modern out-of-order processor can exploit to execute DRAM accesses in parallel--- without sacrificing memory efficiency. The Cuckoo Trie thus breaks a fundamental performance barrier faced by current indexes, whose bottleneck is a series of dependent pointer-chasing DRAM accesses---e.g., traversing a search tree path--- which the processor cannot parallelize. Our evaluation shows that the Cuckoo Trie outperforms state-of-the-art-indexes by up to 20%-360% on a variety of datasets and workloads, typically with a smaller or comparable memory footprint.Keywords
Funding Information
- Israel Science Foundation (2005/17)
This publication has 20 references indexed in Scilit:
- Indexing on modern hardwarePublished by Association for Computing Machinery (ACM) ,2014
- Meet the walkersPublished by Association for Computing Machinery (ACM) ,2013
- The adaptive radix tree: ARTful indexing for main-memory databasesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- KISS-TreePublished by Association for Computing Machinery (ACM) ,2012
- Efficient transaction processing in SAP HANA databasePublished by Association for Computing Machinery (ACM) ,2012
- Making B+- trees cache conscious in main memoryPublished by Association for Computing Machinery (ACM) ,2000
- Log-logarithmic worst-case range queries are possible in space Θ(N)Information Processing Letters, 1983
- Ubiquitous B-TreeACM Computing Surveys, 1979
- An Efficient Algorithm for Exploiting Multiple Arithmetic UnitsIBM Journal of Research and Development, 1967
- Trie memoryCommunications of the ACM, 1960