Efficient Concurrent Updates to Persistent Randomized Binary Search Trees
Proceedings of the VLDB Endowment · 2025-01 · 18 (5) · 1481-1494
DOI: 10.14778/3718057.3718074 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 27.08.2025. Verfasst von Guanhao Hou und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 73 Literaturangaben.
Abstract (Originalsprache)
In the era of big data, the demand for historical data analytics is growing across various applications. Simultaneously, range queries have been extensively explored within the domain of databases. Binary search trees are a classic type of in-memory index for facilitating range queries. Persistent binary search trees provide read-only snapshots of these trees, allowing range queries to be processed during updates while ensuring consistency. Additionally, multiple versions of snapshots support queries related to historical moments to meet the demands of numerous applications. However, existing implementations do not support both highspeed updates and efficient, accurate historical queries on multi-core platforms. Motivated by this gap, we propose a novel concurrent update strategy to balance update and query performance. For a binary search tree containing n elements, our approach completes m updates in O (log n + m ) time using O (log n ) threads. We further implement a hybrid concurrent strategy to improve the scalability and practical performance of our solution. The experimental results demonstrate that our proposal strikes a good balance between update and query performance. In particular, our proposal outperforms existing solutions under workloads with different data distributions and varying update-query ratios.
Zitieren
APA
Hou, G., Huang, J., Zhang, F., & Wang, S. (2025). Efficient Concurrent Updates to Persistent Randomized Binary Search Trees. Proceedings of the VLDB Endowment, 18(5), 1481-1494. https://doi.org/10.14778/3718057.3718074
Vancouver
Hou G, Huang J, Zhang F, Wang S. Efficient Concurrent Updates to Persistent Randomized Binary Search Trees. Proceedings of the VLDB Endowment. 2025;18(5):1481-1494. doi:10.14778/3718057.3718074
BibTeX
@article{Hou2025,
author = {Hou, Guanhao and Huang, Jinchao and Zhang, Fangyuan and Wang, Sibo},
title = {Efficient Concurrent Updates to Persistent Randomized Binary Search Trees},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {18},
number = {5},
pages = {1481--1494},
doi = {10.14778/3718057.3718074}
}
EUVIMED