  The end-to-end lookup latency of a hierarchical index -- such as a B-tree or
a learned index -- is determined by its structure such as the number of layers,
the kinds of branching functions appearing in each layer, the amount of data we
must fetch from layers, etc. Our primary observation is that by optimizing
those structural parameters (or designs) specifically to a target system's I/O
characteristics (e.g., latency, bandwidth), we can offer a faster lookup
compared to the ones that are not optimized. Can we develop a systematic method
for finding those optimal design parameters? Ideally, the method must have the
potential to generate almost any existing index or a novel combination of them
for the fastest possible lookup.
  In this work, we present new data and an I/O-aware index builder (called
AirIndex) that can find high-speed hierarchical index designs in a principled
way. Specifically, AirIndex minimizes an objective function expressing the
end-to-end latency in terms of various designs -- the number of layers, types
of layers, and more -- for given data and a storage profile, using a
graph-based optimization method purpose-built to address the computational
challenges rising from the inter-dependencies among index layers and the
exponentially many candidate parameters in a large search space. Our empirical
studies confirm that AirIndex can find optimal index designs, build optimal
indexes within the times comparable to existing methods, and deliver up to 4.1x
faster lookup than a lightweight B-tree library (LMDB), 3.3x--46.3x faster than
state-of-the-art learned indexes (RMI/CDFShop, PGM-Index, ALEX/APEX, PLEX), and
2.0 faster than Data Calculator's suggestion on various dataset and storage
settings.
