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

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 domina...

Full description

Saved in:
Bibliographic Details
Main Authors: Christine Euna Jung, Jaesang Hwang, Yedam Na, Haena Lee, Wook-Hee Kim
Format: Article
Language:English
Published: IEEE 2025-01-01
Series:IEEE Access
Subjects:
In-memory index
time series database
insert-heavy workloads
segmented block
Online Access:https://ieeexplore.ieee.org/document/11123847/
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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> <tex-math notation="LaTeX">$7\times $ </tex-math></inline-formula> higher throughput on insert-only workloads and <inline-formula> <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.
ISSN:2169-3536

Similar Items