Demonstrating Indexing for Near-Sorted Data

Abstract

Indexing sits at the heart of database systems due to its ability to support efficient queries. Classical indexes like B + -trees accelerate lookups by imposing order at the leaf level of the index, thereby adding structure (or sortedness ) to otherwise unstructured data. However, when data arrives pre-sorted or nearly-sorted , B + -trees fail to leverage the intrinsic order and perform redundant indexing effort. Near-sorted data is increasingly common in modern applications like the stock market or sensor readings. In such applications, the redundant indexing effort leads to sub-optimal performance. In this paper, we demonstrate recently proposed indexing techniques for near-sorted data, highlighting the performance implications of textbook ingestion in B + -trees as well as how our method achieves better ingestion performance. The demonstration integrates tail-leaf optimization - a widely deployed production technique for efficient ingestion, alongside SWARE and QuIT - our recently proposed index designs that harness sortedness to improve performance. Users can visualize differently sorted data workloads, view the complete index ingestion cycle, as well as analyze performance metrics that measure the impact of intrinsic order.