Near-Sortedness in Indexes

Real-world data ingestion is rarely perfectly sorted — incoming records often arrive nearly sorted, with a small fraction entries displaced. What happens when such workloads are ingested into an index?
This demo lets you configure near-sorted data using the K-L-sortedness metric, visualize the data, and ingest such near-sorted streams into indexes that adapt to sortedness, as well as classical B+trees.

Our Publications about Sortedness

Aneesh Raman, Konstantinos Karatsenidis, Shaolin Xie, Matthaios Olma, Subhadeep Sarkar, Manos Athanassoulis
QuIT your B+-tree for the Quick Insertion Tree [PDF]
In Proceedings of the 28th International Conference on Extending Database Technology (EDBT), 2025.

Aneesh Raman, Andy Huynh, Jinqi Lu, Manos Athanassoulis
Benchmarking Learned and LSM Indexes for Data Sortedness [PDF]
In Proceedings of the 10th International Workshop on Testing Database Systems (DBTest), 2024.

Aneesh Raman, Subhadeep Sarkar, Matthaios Olma, Manos Athanassoulis
Indexing for Near-Sorted Data [PDF]
In Proceedings of the 39th IEEE International Conference on Data Engineering (ICDE), 2023.

Aneesh Raman, Konstantinos Karatsenidis, Subhadeep Sarkar, Matthaios Olma, Manos Athanassoulis
BoDS: A Benchmark on Data Sortedness [PDF]
In Performance Evaluation and Benchmarking - 14th TPC Technology Conference (TPCTC), 2022.