This project explores a new type of a “learned index”, which can achieve significantly smaller footprint (relative to B+ Tree), with deterministic bounds on lookup times and support for inserts. At the heart of FITing-Tree is a trade-off between bandwidth and latency: FITing-Tree is an approximation of a full index where the number of random memory lookups (which is correlated with size of the index) is traded with non-random memory lookups (search in a bounded area).