Data structures that maintain a sorted sequence are crucial for many applications. There is a zoo of variants with recent particular interest in "learned" indexes that accelerate operations by learning the distribution of the data. This paper helps to bring some order to this complex situation. We identify important building blocks and model the input using smoothed analysis where an adversary can control the dynamically changing input except for a small amount of noise. Within a resulting design space of data structures, we prove that already a simple 2-level data structure with minimal learning can achieve constant operation times in many situations: PARROT partitions the input into equal size parts, within which keys are approximately uniformly distributed. In many of our experiments, PARROT performs very well compared to state-of-the-art learned indexes, being 2× faster than the well known ALEX and LIPP indexes on large datasets, and 10× faster than a well engineered standard B-Tree.

The rapid evolution of learned data structures has revolutionized database indexing, particularly for sorted integer datasets. While learned indexes excel in static scenarios due to their low memory footprint, reduced storage requirements, and fast lookup times, benchmarks like SOSD and TLI have largely overlooked compressed indexes and SIMD-based implementations of traditional indexes. This paper addresses this gap by introducing a comprehensive benchmarking framework that (i) evaluates traditional, learned, and compressed indexes across 12 datasets (real and synthetic) of varying types and sizes; (ii) integrates state-of-the-art SIMD-enhanced B-Tree variants; and (iii) measures critical performance metrics such as memory usage, construction time, and lookup efficiency. Our findings reveal that while learned indexes minimize memory usage, a feature useful when internal memory constraints are mandatory, SIMD-enhanced B-Trees consistently achieve superior lookup times with comparable extra space. On the other hand, compressed indexes like LA-vector and EliasFano provide very effective compression of the indexed data with slower access speeds (2x-3x). Another contribution of this paper is a publicly available benchmarking framework (composed of code and datasets) that makes our experiments reproducible and extensible to other indexes and datasets.