Concurrent Path-Copying Update to Tree Structures

Historical data are widely used in science, business, and web applications. In this context, tree structures play a fundamental role in databases, particularly in query processing. Path copying offers a cost-effective approach to providing immutable snapshots of a tree. If snapshots preserve the order of update requests, each snapshot version is mapped to a specific point in history, thereby facilitating historical data queries and analysis. Recently, Contreap enables concurrent path-copying updates on BSTs, primarily targeting historical queries on predefined statistics by maintaining the corresponding augments in tree nodes. However, real-world applications often require general-purpose operations, such as element retrieval or range scanning, while BSTs are not well-suited for such operations. Nevertheless, existing path-copying implementations for popular database tree structures generally lack efficient support for concurrent updates, limiting their applicability. In this paper, we present ConTree, a lightweight programming library that transparently supports concurrent path-copying updates for tree structures. We show how to integrate a recursive update process — subject to certain constraints to ensure correctness —,into ConTree. We further discuss techniques for optimising existing tree structures to improve the efficiency of concurrent path copying. Building on this foundation, we instantiate ART and B+Tree, addressing key obstacles to concurrent path copying with two novel solutions: AERT and BeTree, using our ConTree library. These optimised variants incorporate structural and algorithmic refinements to support scalable updates. Extensive experiments show that our concurrent update strategy is effective, delivering significant speedups for AERT and BeTree over their serial counterparts.