# Cuckoo Trie: Exploiting Memory-Level Parallelism for Efficient DRAM Indexing

arXiv: https://arxiv.org/abs/2201.09331 · HTML: https://mlsanity.com/paper/2201.09331/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2022.

## Built on by (most cited first, 1 of 1)

- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)

## Abstract (arXiv)

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.