SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block

Various devices such as smart cars, healthcare systems, and IoT platforms generate a massive amount of time series data. This type of data exhibits unique characteristics that pose new challenges for in-memory indexes, including heavy insert rates, monotonically increasing keys, and workloads dominated by range queries. In this paper, we propose a new in-memory index, Segmented Block-based Tree (SB-Tree), designed specifically for time series workloads. To support high insert throughput, SB-Tree decouples the index into a search layer and a data layer, and updates the search layer asynchronously to reduce write amplification. It introduces a shortcut mechanism to reduce tree traversal overhead and uses segmented blocks with per-thread data blocks to minimize contention during inserts. In addition, SB-Tree employs a lightweight block allocator to reduce system call overhead during memory management. We evaluate SB-Tree using synthetic time series workloads with varying levels of delayed data, inserting up to 1 billion keys across 80 threads. Our results show that SB-Tree outperforms state-of-the-art in-memory indexes, achieving up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$7\times $ </tex-math></inline-formula> higher throughput on insert-only workloads and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2.4\times $ </tex-math></inline-formula> lower 99.99th percentile tail latency on scan workloads compared to state-of-the-art.