# FITing-Tree: A Data-aware Index Structure

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

## Key facts

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

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

- [One Model to Rule them All: Towards Zero-Shot Learning for Databases](https://mlsanity.com/paper/2105.00642/) (2021)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [On Distribution Dependent Sub-Logarithmic Query Time of Learned Indexing](https://mlsanity.com/paper/2306.10651/) (2023)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [Learned Sorted Table Search and Static Indexes in Small Model Space](https://mlsanity.com/paper/2107.09480/) (2021)
- [No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees](https://mlsanity.com/paper/2108.10130/) (2021)
- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [Theoretical Analysis of Learned Database Operations under Distribution Shift through Distribution Learnability](https://mlsanity.com/paper/2411.06241/) (2024)
- [NFL: Robust Learned Index via Distribution Transformation](https://mlsanity.com/paper/2205.11807/) (2022)
- [Daisy Bloom Filters](https://mlsanity.com/paper/2205.14894/) (2022)
- [LeCo: Lightweight Compression via Learning Serial Correlations](https://mlsanity.com/paper/2306.15374/) (2023)
- [Towards Effective Next POI Prediction: Spatial and Semantic Augmentation with Remote Sensing Data](https://mlsanity.com/paper/2404.04271/) (2024)
- [Micro-architectural Analysis of a Learned Index](https://mlsanity.com/paper/2109.08495/) (2021)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [Towards Establishing Guaranteed Error for Learned Database Operations](https://mlsanity.com/paper/2411.06243/) (2024)
- [A New Paradigm in Tuning Learned Indexes: A Reinforcement Learning Enhanced Approach](https://mlsanity.com/paper/2502.05001/) (2025)
- [A Pluggable Learned Index Method via Sampling and Gap Insertion](https://mlsanity.com/paper/2101.00808/) (2021)
- [DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees](https://mlsanity.com/paper/2502.05369/) (2025)
- [L2T-Tune:LLM-Guided Hybrid Database Tuning with LHS and TD3](https://mlsanity.com/paper/2511.01602/) (2025)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Testing the Robustness of Learned Index Structures](https://mlsanity.com/paper/2207.11575/) (2022)
- [SparDL: Distributed Deep Learning Training with Efficient Sparse Communication](https://mlsanity.com/paper/2304.00737/) (2023)
- [LearnedKV: Integrating LSM and Learned Index for Superior Performance on Storage](https://mlsanity.com/paper/2406.18892/) (2024)
- [Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2506.20139/) (2025)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)
- [Lower Bounds for the Algorithmic Complexity of Learned Indexes](https://mlsanity.com/paper/2601.06629/) (2026)
- [M-CTX: Exact and Scalable Spatial Context Retrieval for Trajectory Analytics](https://mlsanity.com/paper/2606.15244/) (2026)
- [Poisoning Attacks on the PGM-index](https://mlsanity.com/paper/2609.02328/) (2026)
- [Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications](https://mlsanity.com/paper/2609.04787/) (2026)

## Abstract (arXiv)

Index structures are one of the most important tools that DBAs leverage to improve the performance of analytics and transactional workloads. However, building several indexes over large datasets can often become prohibitive and consume valuable system resources. In fact, a recent study showed that indexes created as part of the TPC-C benchmark can account for 55% of the total memory available in a modern DBMS. This overhead consumes valuable and expensive main memory, and limits the amount of space available to store new data or process existing data. In this paper, we present FITing-Tree, a novel form of a learned index which uses piece-wise linear functions with a bounded error specified at construction time. This error knob provides a tunable parameter that allows a DBA to FIT an index to a dataset and workload by being able to balance lookup performance and space consumption. To navigate this tradeoff, we provide a cost model that helps determine an appropriate error parameter given either (1) a lookup latency requirement (e.g., 500ns) or (2) a storage budget (e.g., 100MB). Using a variety of real-world datasets, we show that our index is able to provide performance that is comparable to full index structures while reducing the storage footprint by orders of magnitude.