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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11123847/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849223089509892096 |
|---|---|
| author | Christine Euna Jung Jaesang Hwang Yedam Na Haena Lee Wook-Hee Kim |
| author_facet | Christine Euna Jung Jaesang Hwang Yedam Na Haena Lee Wook-Hee Kim |
| author_sort | Christine Euna Jung |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-453365e7e29f46d28caf3b6c8b1d6744 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-453365e7e29f46d28caf3b6c8b1d67442025-08-25T23:12:00ZengIEEEIEEE Access2169-35362025-01-011314492714494010.1109/ACCESS.2025.359873611123847SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented BlockChristine Euna Jung0https://orcid.org/0009-0004-3764-0615Jaesang Hwang1https://orcid.org/0009-0003-3590-1917Yedam Na2Haena Lee3https://orcid.org/0009-0008-6573-8838Wook-Hee Kim4https://orcid.org/0000-0001-6292-3001Department of Computer Science and Engineering, Konkuk University, Seoul, Republic of KoreaDepartment of Computer Science and Engineering, Konkuk University, Seoul, Republic of KoreaDepartment of Computer Science and Engineering, Konkuk University, Seoul, Republic of KoreaDepartment of Computer Science and Engineering, Konkuk University, Seoul, Republic of KoreaDepartment of Computer Science and Engineering, Konkuk University, Seoul, Republic of KoreaVarious 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.https://ieeexplore.ieee.org/document/11123847/In-memory indextime series databaseinsert-heavy workloadssegmented block |
| spellingShingle | Christine Euna Jung Jaesang Hwang Yedam Na Haena Lee Wook-Hee Kim SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block IEEE Access In-memory index time series database insert-heavy workloads segmented block |
| title | SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block |
| title_full | SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block |
| title_fullStr | SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block |
| title_full_unstemmed | SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block |
| title_short | SB-Tree: A B+-Tree for In-Memory Time Series Databases With Segmented Block |
| title_sort | sb tree a b tree for in memory time series databases with segmented block |
| topic | In-memory index time series database insert-heavy workloads segmented block |
| url | https://ieeexplore.ieee.org/document/11123847/ |
| work_keys_str_mv | AT christineeunajung sbtreeabtreeforinmemorytimeseriesdatabaseswithsegmentedblock AT jaesanghwang sbtreeabtreeforinmemorytimeseriesdatabaseswithsegmentedblock AT yedamna sbtreeabtreeforinmemorytimeseriesdatabaseswithsegmentedblock AT haenalee sbtreeabtreeforinmemorytimeseriesdatabaseswithsegmentedblock AT wookheekim sbtreeabtreeforinmemorytimeseriesdatabaseswithsegmentedblock |