Concurrent Splay-Based Tree Vitaly Aksenov # ITMO University, Russia
Rene van Bevern # Independent Researcher
Artem Shilkin # ITMO University, Russia
arXiv:2606.28889v1 [cs.DC] 27 Jun 2026
Abstract Most work on efficient concurrent ordered indices, such as concurrent binary search trees, B-trees, skip lists, etc., has focused on data structures that provide good worst-case guarantees. In real workloads, objects are often accessed at different rates, since access distributions may be non-uniform. Many efficient distribution-adaptive data structures exist in the sequential case; however, they are often complicated to make efficient in the concurrent case. The most prominent distribution-adaptive data structure is Splay Tree. Its most important advantage is that it does not store any balancing information and provides a reasonable performance improvement on extremely skewed workloads, such as Zipfian workloads. This paper proposes a splay-like rotation design for concurrent binary search trees. Instead of moving an accessed node to the root, rotations use two depth thresholds that are based on the static-optimality complexity computed from the number of accesses to the node: a node is rotated only when it is substantially deeper than the upper threshold, and rotations of the node stop before reaching the lower threshold. This design aims to preserve the main practical benefit of splaying on skewed workloads while reducing contention near the root. We present two variants of the rotation design: one using an exact 64-bit access counter per node and one using a 6-bit approximate counter. We prove static optimality for the corresponding sequential read-only tree and evaluate both rotation designs by implementing them on top of the concurrent AVL tree of Bronson et al. Our experiments show that the approach can improve throughput on several skewed workloads.
2012 ACM Subject Classification Replace ccsdesc macro with valid one Keywords and phrases Concurrent data structures, binary search trees, splay trees, adaptive data structures Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23
1
Introduction
There has been a significant effort to design concurrent data structures from sequential variants, e.g., hash tables [11, 8], skip lists [6, 7, 10], and search trees [13, 4]. However, most of these works have focused on data structures with optimal worst-case guarantees. It is known that the worst-case complexity of point operations in any data structure built using only comparisons is logarithmic in the size of the data structure. One of the ways to escape this lower bound is to adapt to the workload, i.e., requests. Fortunately, in many real workloads, the access rates for keys are not uniform. This fact is well known and is modelled in several industrial benchmarks, such as YCSB [5] and TPC-C [15], where the generated access distributions are heavy-tailed, e.g., following a Zipfian distribution [5]. There is a large line of work devoted to adaptive data structures in the sequential case; see, e.g., [9] and references therein, with the most renowned one being Splay Tree [17]. One can consider it as one of the simplest yet efficient data structures using no balancing information and working exceptionally well on Zipfian workloads, with the © Vitaly Aksenov, Rene van Bevern, Artem Shilkin; licensed under arXiv.org perpetual, non-exclusive license 42nd Conference on Very Important Topics (CVIT 2016). Editors: John Q. Open and Joan R. Access; Article No. 23; pp. 23:1–23:9 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
23:2
Concurrent Splay-Based Tree
most accessed element always very close to the root. Unfortunately, Splay Tree is not easy to make concurrent efficiently due to its rebalancing procedure, which rotates the accessed node to the root. This has an effect on its concurrent implementation: multiple concurrent operations will contend for the root, leading to a large bottleneck. Because of that issue, we are unaware of any work on making the original Splay Tree concurrent without changes. Instead, researchers have proposed two adaptive data structures based on specialized rotations: CBTree [1] and Splay-List [2]. CBTree uses a rebalancing procedure similar to those of both AVL and Splay Trees. Intuitively, it tries to maintain the following invariant for each node: the ratio between the numbers of requests to the left and right subtrees should not exceed some predefined constant. Compared to Splay Tree, which does not store any additional information, CBTree requires storing three integers per node: the number of accesses to it and the number of accesses to both subtrees (this can be improved to two integers by storing just the size of its own subtree). In addition to the memory overhead, it appeared to scale a bit worse than the second known concurrent adaptive data structure, Splay-List. Splay-List is based on a Skip List [16] with a rebalancing procedure that uses the number of accesses. Unfortunately, better scaling comes with even worse memory utilization: Splay-List requires much more memory than CBTree, since it stores the number of accesses per node plus the number of accesses per “subtree”. In this work, we try to come up with data structures based on Splay Tree that work better and use less additional memory than the presented counterparts. For that, we propose two concurrent variations of Splay Tree that use the same rotations as the vanilla one while requiring only one integer per node: the number of accesses. The idea is quite simple. The usual goal of an adaptive data structure is to provide static optimality for accesses, recalled in Section 2. Splay Tree satisfies this property, but, as we explained, its straightforward implementation creates a bottleneck close to the root. Thus, instead of splaying to the root, we rotate the node only up to depth A · log(m/ac(x)). That change is not enough, since nodes would still be splayed on each access. To reduce the number of rotations, we rotate the node only if its current depth exceeds B · log(m/ac(x)). Finally, we initiate the rotation only with some probability, which was experimentally shown to be helpful for Splay Tree [3] while maintaining the complexity. Our first version of the rotation design stores the number of accesses in each node using 64 bits. Then, we propose a second version based on an approximate counter by Morris [12]. Instead of the number of accesses, it stores roughly its logarithm, and on an access it increments its value, r, with probability 21r . We analyze the first proposed rotation design in a sequential read-only setting and show that it preserves static optimality. We then evaluate our design in a concurrent setting by integrating it into the AVL tree of Bronson et al. [4]. The implementation is compared with the original AVL tree and with CBTree. The experiments show that our rotation design improves the performance on several skewed workloads. The paper has the following structure. In Section 2, we recall the necessary background on Splay Tree and static optimality. In Section 3, we propose the design of our rotation procedure. In Section 3.2, we prove that this design leads to the static-optimality property. In Section 4, we present the evaluation of our data structure.
2
Background
Splay tree [17] is a binary search tree that does not store balancing information. An access (or get operation) to a key x traverses the tree as usual. If x is found in a node u, the tree then splays u: it repeatedly applies local rotations that move u toward the root.
V. Aksenov, R. van Bevern, and A. Shilkin
v
u
u
C
⇒
w v
v
A B
B
w
u D
v
A
v
C
u v
D
⇒ u
A
23:3
w
⇒ w
B
u
A
A
B C
D
C A
B
zig
C zig-zig
D
B
C zig-zag
Figure 1 The left-child versions of Splay Tree rotations. The right-child versions are symmetric.
The splay step uses three types of rotations, shown in Figure 1. In the zig case, u has no grandparent, so one ordinary rotation makes u the root. In the zig-zig case, u and its parent are both left children or both right children; the algorithm rotates the parent and then u. In the zig-zag case, u is a left child and its parent is a right child, or symmetrically; the algorithm rotates u twice. The zig-zig and zig-zag cases decrease the depth of u by two, while the final zig decreases it by one.
▶ Definition 1 (Static optimality). Consider a sequence of m successful access operations. Let ac(x) be the number of accesses to key x. A search tree is statically optimal if its total P access cost is O ( x ac(x) · log(m/ac(x))), or, equivalently, if the amortized cost of an access to key x is O(log(m/ac(x))).
3
Rotation Procedure
The simplest approach to avoid the bottleneck of the Splay Tree in the concurrent setting is to splay the accessed node only up to some fixed depth and perform rotations only up to some number of conflicts (i.e., when one rotation is overtaken by another concurrent rotation). Unfortunately, our experiments showed that such an approach does not work well due to at least two issues. First, we were unable to find universal constants that work well for every tree size and every number of working threads. Such tuning, of course, is undesirable. Second, it provides quite a large constant overhead on skewed workloads due to the inability to move nodes up the depth threshold. For example, on a Zipfian workload, the most commonly accessed element may be lower than the threshold, and thus will never be moved past the depth threshold, leading to a traversal overhead. So, the choice of the threshold is complicated: it should be large enough to reduce the bottleneck, but at the same time it should be small.
3.1
Version with exact counters
Since the trivial approach does not seem to work, we had to find another way to bound the depth up to which we rotate the node. We decided to choose this bound by trying to satisfy the static-optimality property: rotate up to the level A · log(m/ac(x)), where m is the total number of accesses and ac(x) is the number of accesses to the key. Unfortunately, with only that bound, the nodes lower than it will always be splayed leading to a large number of rotations. Thus, we decided to allow some slack and rotate only if the depth of the node is much larger than the static-optimality property requires, i.e., exceeds B · log(m/ac(x)).
CVIT 2016
23:4
Concurrent Splay-Based Tree
1 void get ( x ) : 2 depth = 0 3 node = root 4 while node != null : 5 if node . key = x : 6 break 7 depth += 1 8 if node . key < x : 9 node = node . right 10 else : 11 node = node . left 12 13 if node == null : 14 return null 15 16 node . counter += 1
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
global_ counter += 1 target = log ( glob al_count er / node . counter ) // We allow the slack if depth < B * target : return node . value if rand () > PTHRESHOLD : return node . value // Rotate only up to some level while depth > A * target : rotate ( node ) depth -= 2 // zig - zig and zig - zag reduce depth // by 2. zig happens only at the root .
Listing 1 The code of the access (get) operation.
First, in Lines 2-11, we traverse the tree to find a node with the requested key and simultaneously calculate the depth of the target node. If the key is not found, we return null (Lines 13-14). Otherwise, we increment the global counter and the key counter, and calculate the target value of the static-optimal complexity (Lines 16-18). If the node has depth less than some constant B times the target complexity, we end the operation (Lines 21-22). Then, we generate a random number to decide whether we need to perform rotations (Line 24). If we decide not to, we return the value (Line 25). Otherwise, we rotate the node toward the root until its depth becomes less than A times the target (Lines 28-30). Note that during splaying, usually zig-zig and zig-zag rotations are used, reducing the depth by 2. The zig rotation can happen only at the very top. The concurrent implementation follows the exact same procedure. We have three notes about it: 1) increments of the counters are implemented using the fetch-and-add operation; 2) the increments to the global counter may lead to contention, which will be fixed in the second design; and 3) the depth may not be calculated precisely and the node may not be rotated to the expected place due to concurrent rotations.
3.2
Static-optimality proof
In this subsection, we prove that the sequential tree with our rotation design provides static optimality. To prove it, we require a tree to be initially filled with all keys, and to serve only access, i.e., get, requests. Let w(u) be the number of accesses to the node at the end, let σ(u) be the sum of weights of all nodes in the subtree of u, and let the rank be ρ(u) = log σ(u). Suppose that we decide to make a rotation with probability p (PTHRESHOLD). Thus, we will introduce a potential P function Φ = (1/p + d) · ρ(u) where d is the cost of one rotation. ▶ Lemma 2. The expected amortized time incurred by the i-th operation is O(log(ACi /aci (t))+ log(m/acm (t))), where t is the node found by the operation, aci (t) is the total number of accesses to t, ACi is the total number of accesses before the i-th access, and m is the total number of requests. Proof. Let us start with the simplest case. If the depth of the node does not exceed B · log ACi /aci (t) by the condition in Line 21, the statement follows directly. Now, we consider the case when the depth exceeds that bound. Let us calculate the expected cost of the change of the potential and the cost of the operation. We split an access operation into two parts. In the first part, we traverse to node s at depth A · log(ACi /aci (t)) (adding that cost). Then, we traverse to the target node t and splay it up to s with some probability. For simplicity, we assume that t takes the place of s and not a slightly higher position due to the parity of the depth.
V. Aksenov, R. van Bevern, and A. Shilkin
23:5
For the second part, we repeat a standard potential-based proof for Splay Tree from [3] and get the bound log(m/acm (t)). We provide the full version in the Appendix. ◀ The main result follows from this lemma almost straightforwardly — we just need to replace ACi /aci (t) by m/acm (t). The full proof is in the Appendix. P ▶ Theorem 3. A tree with such rotations serves accesses in O(1/p · x ac(x) · log(m/ac(x))) amortized time, where m is the total number of accesses and ac(x) is the total number of accesses to x.
3.3
Version with approximate counters
The second version of our rotation design is not much different from the one above. Instead of exact counters, we use the approximate counter from [12] for global and node counters: on an access, we increment a counter with value r with probability 21r and return 2r . The Morris counter gives a compact estimate whose expectation is within a constant-factor scale of the true count. This counter needs just 6 bits to approximate a 64-bit counter. The pseudocode is shown in Listing 2. Unfortunately, the basic Morris counter does not provide direct static-optimality bounds due to nontrivial variance. Instead, one can use the improvement presented in [14]. Nevertheless, we use the basic approach in the implementation.
4
Experiments
We implemented our rotation design on top of the concurrent AVL tree by Bronson et al. [4] and obtained two data structures: Splay-like and Approximate-Splay-like. We compare their performance against the AVL tree by Bronson et al. [4] and its adaptive version, CBTree [1]. We implemented the code in Java. We did not compare with Splay-List [2] since it was written in C++. As noted, the issue with the simplest concurrent Splay Tree is fixing the best constants. Fortunately, we were able to find good generic parameters for our data structures. For the 1 Splay-like tree, we set the probability of splaying to 20·T , where T is the number of threads, the upper bound constant is B = 2.5, and the lower bound constant is A = 0.7. For the Approximate-Splay-like tree, we set the probability to 1, B = 2, and A = 0.5. We also had to update CBTree to rotate with some probability in order to improve its performance. The 1 probability was set to 10·T . For the workloads, we chose ones similar to the workloads presented in the Splay-List paper [2]. First, we fix the range to 106 elements. Then, we fix five distributions: 1) uniform — a key is chosen uniformly; 2) zipfian — a key is chosen from a Zipfian distribution with α = 1 over a preliminarily shuffled set; 3) 99/1, 95/5, and 90/10 — x/y means that we choose a set of x% random elements from the range, and the key is chosen with probability y% from this set and otherwise from the rest. We also choose two types of workloads. In read-only workloads, the structure is pre-filled with all the keys, and get operations choose the key from the distribution. In update workloads, the data structure is pre-filled with a random half of the range, and the operation is get with probability 80%, with the key from the distribution, or insert/remove with probability 10% each, with the key taken uniformly from the range. The experiments were run three times on a machine with four x86 chips with 16 cores each (64 cores in total) and 256 GB of RAM, with each run consisting of 20 seconds of warmup and 20 seconds of measured execution. The throughput shown in the plots was averaged. The code was written in Java and compiled with OpenJDK 21.0.11.
CVIT 2016
23:6
Concurrent Splay-Based Tree
(a) uniform
(b) zipfian
(d) 95/5
(c) 90/10
(e) 99/1
Figure 2 Throughput of the implementations on read-only workloads with range size 106 .
(a) uniform
(b) zipfian
(d) 95/5
(c) 90/10
(e) 99/1
Figure 3 Throughput of the implementations on update workloads.
Figure 2 shows the results of the experiments on the read-only workloads. As one can see, the original AVL outperforms the other data structures on lower-skew workloads, i.e., uniform and 90/10, and on Zipfian workloads due to its static structure and, thus, better cache performance. On higher regular skew, 95/5 and 99/1, our trees work similarly to or better than the original AVL. Please note that our approximate-counter version works similarly to the exact-counter version. CBTree performs worse than expected in our implementation, even though we followed the pseudocode from the paper [1] and tuned for the best parameters. Figure 3 shows the results of the experiments on the update workloads. This time, AVL has worse cache usage, and our data structures outperform it on almost all workloads while working a little worse on the uniform workload. Our approximate-counter version works slightly better than the exact-counter version.
V. Aksenov, R. van Bevern, and A. Shilkin
23:7
References 1
2
3 4 5
6 7
8 9 10 11
12 13
14
15 16 17
A
Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E. Tarjan. Cbtree: A practical concurrent self-adjusting search tree. In Proceedings of the 26th International Conference on Distributed Computing, DISC’12, pages 1–15, Berlin, Heidelberg, 2012. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-33651-5_1, doi:10.1007/978-3-642-33651-5_1. Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. The splay-list: A distribution-adaptive concurrent skip-list. In 34th International Symposium on Distributed Computing (DISC 2020), pages 3–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. Susanne Albers and Marek Karpinski. Randomized splay trees: Theoretical and experimental results. Information Processing Letters, 81(4):213–221, 2002. Nathan G Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. A practical concurrent binary search tree. ACM Sigplan Notices, 45(5):257–268, 2010. Brian F Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM symposium on Cloud computing, pages 143–154, 2010. Keir Fraser. Practical lock-freedom. Technical Report UCAM-CL-TR-579, University of Cambridge, Computer Laboratory, February 2004. Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. A simple optimistic skiplist algorithm. In Proceedings of the 14th international conference on Structural information and communication complexity, SIROCCO’07, pages 124–138, Berlin, Heidelberg, 2007. SpringerVerlag. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. Donald Ervin Knuth. The art of computer programming, volume 3. Pearson Education, 1997. Doug Lea, 2007. http://java.sun.com/javase/6/docs/api/java/util/concurrent/ ConcurrentSkipListMap.html. Maged M Michael. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, pages 73–82. ACM, 2002. Robert Morris. Counting large numbers of events in small registers. Communications of the ACM, 21(10):840–842, 1978. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’14, pages 317–328, New York, NY, USA, 2014. ACM. URL: http: //doi.acm.org/10.1145/2555243.2555256, doi:10.1145/2555243.2555256. Jelani Nelson and Huacheng Yu. Optimal bounds for approximate counting. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 119–127, 2022. Meikel Poess and Chris Floyd. New tpc benchmarks for decision support and web commerce. ACM Sigmod Record, 29(4):64–71, 2000. William Pugh. Concurrent maintenance of skip lists. 1998. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686, 1985.
Deferred proofs
▶ Lemma 4. The expected amortized time incurred by the i-th operation is at most O(log(ACi /aci (t))+ log(m/acm (t))), where t is the node found by the operation, aci (t) is the total number of
CVIT 2016
23:8
Concurrent Splay-Based Tree
accesses to t, ACi is the total number of accesses before the i-th access, and m is the total number of requests. Proof. Let us start with the simplest case. If the depth of the node does not exceed B · log ACi /aci (t) by the condition in Line 21, the statement follows directly. Now, we consider the case when the depth exceeds that bound. Let us calculate the expected cost of the change of the potential and the cost of the operation. We split the cost of an access into two parts. In the first part, we traverse to node s at depth A · log(ACi /aci (t)). Then, we traverse to the target node t and splay it up to s with some probability. For simplicity, we assume that t takes the place of s and not a slightly higher position due to the parity of the depth. For the second part, we repeat the proof from [3] and provide the full version in the Appendix. Let w(u) be some weight function on nodes, let σ(u) be the sum of weights of all nodes in the subtree of u, and let the rank be ρ(u) = log σ(u). Suppose that we decide to make a rotation with probability p (PTHRESHOLD). Thus, we will introduce a potential function P Φ = (1/p + d) · ρ(u) where d is the cost of one rotation. The expected amortized cost of the second part is E[T ] + E[∆Φ] where T is the cost of traversal from s and rotations to s and ∆Φ is the change in the potential. Note that the first part of an access up to s does not change the potential and always is O(log(ACi /aci (t))). The algorithm performs rotations with probability p. Since the expectation of the sum is the sum of the expectations, we can consider each rotation separately. Each rotation consists of three parts: the initial cost of the traversal, the cost of the rotation times the probability p, and the change in the potential times the probability p. Thus, traversal plus rotation for each node is 1 + p · d. Now, we will bound the change in the potential. Suppose we rotate a node u. Let v and w be its parent and grandparent, if exists. 1. Zig rotation. If the edge is rotated, the change in the potential is ρ′ (u)+ρ′ (v)−ρ(u)−ρ(v) because the ranks change only for u and v. Thus, the expected amortized cost is (1 + pd) + p(1/p + d) · (ρ′ (u) + ρ′ (v) − ρ(u) − ρ(v)) ≤ (1 + pd) + (1 + pd) · (ρ′ (u) − ρ(u)) ≤ C + 3 · C · (ρ′ (u) − ρ(u)). The inequalities hold since ρ(v) ≥ ρ′ (v). 2. Zig-zig and zig-zag rotations. There are two rotations, which lead to 2(1 + pd), while the change in the potential is ρ′ (u) + ρ′ (v) + ρ′ (w) − ρ(u) − ρ(v) − ρ(w), because only the ranks of u, v, and w are changed. Therefore, the expected amortized cost does not exceed 2(1 + pd) + p(1/p + d) · (ρ′ (u) + ρ′ (v) + ρ′ (w) − ρ(u) − ρ(v) − ρ(w)) ≤ (1 + pd) · (2 + ρ′ (u) + ρ′ (v) + ρ′ (w) − ρ(u) − ρ(v) − ρ(w)). Using the same technique as in [17], we can show that ρ′ (u) + ρ′ (v) + ρ′ (w) − ρ(u) − ρ(v) − ρ(w) ≤ 3 · (ρ′ (u) − ρ(u)). Hence, the amortized cost of that rotation is 3 · (1 + pd) · (ρ′ (u) − ρ(u)). Finally, the expected amortized cost of traversal from s to u and rotations equals the sum over all rotations. This sum is bounded by 3 · (1 + pd) · (ρ′ (t) − ρ(t)) = 3 · (1 + pd) · (ρ(s) − ρ(t)), since t takes the place of s. To finish the proof, we fix the weight function w of nodes as the number of accesses to the corresponding key at the end. This gives the required bound 3 · (1 + pd) · log(m/acm (t)) since ρ(s) ≤ log m. ◀ P ▶ Theorem 5. A tree with such rotations serves accesses in O(1/p · x ac(x) · log(m/ac(x))) amortized time, where m is the total number of accesses and ac(x) is the total number of accesses to x.
V. Aksenov, R. van Bevern, and A. Shilkin
23:9
Proof. Choosing the weight function as the number of accesses bounds the initial potential P from above by (1/p + d) · log m and bounds the final potential from below by (1/p + d) · x P log ac(x). The contribution of the potential is the difference between the initial and final x
potentials and is thus upper-bounded by the desired bound. Pac(x) Now, we consider all accesses to node x. By Lemma 4, their total cost is i=1 O(log(ACoi /i)+ Pac(x) log(m/ac(x))), where oi is the identifier of the i-th operation on x. Since i=1 log i ≥ Pac(x) Pac(x) i=1 O(log(ACoi /i)) = i=ac(x)/2 log i ≥ ac(x)/2 · log(ac(x)/2) and ACoi ≤ m, we get O(ac(x) · log(m/ac(x))), which is exactly what we require. ◀
B
Listings
1 if rnd () < 1 / 2^ gl obal_co unter : 2 global _counter += 1 3 4 if rnd () < 1 / 2^ node . counter : 5 node . counter += 1 6 7 target = glo bal_coun ter - node . counter
Listing 2 Approximate computation of the target depth
CVIT 2016