PaB-tree: Parallel B+-tree with Batch Updates

PaB-tree: Parallel 𝐵 +-tree with Batch Updates Ziyang Men

Yan Gu

Yihan Sun

Helen Xu

ziyang.men@email.ucr.edu University of California, Riverside

ygu@cs.ucr.edu University of California, Riverside

yihans@cs.ucr.edu University of California, Riverside

hxu615@gatech.edu Georgia Institute of Technology

44–46, 52, 53, 57, 62, 64, 65, 68, 70, 71, 74, 75, 77–79, 85]. These structures apply updates (insertions or deletions) in batches in parallel, and have been adopted in graph processing [27, 29, 31, 57, 69, 75], databases [61, 64], parallel algorithms for dynamic programming [28, 39], computational geometry [13, 52], vector similarity search [53, 84, 85], etc. Although both B/B+ -trees [7, 23] and BSTs [2, 41, 55] were introduced over 50 years ago, and while B/B+ -trees are the go-to index design due to their cache-friendliness, there is a striking disparity in the maturity of their batch-parallel counterparts. Parallel BST implementations have been studied extensively and are widely accessible in practice, with examples including the PAM [14, 65], Aspen [27], CPAM [26], and MCSTL [32]. Many of them are also theoretically efficient, achieving high parallelism while preserving optimal or near-optimal sequential work bounds. In contrast, there is a notable lack of accessible batch-parallel B/B+ -tree implementations with both strong empirical performance and provable, near-optimal I/O efficiency. Existing efforts are either purely theoretical [35, 43, 59], with no high-performance implementation, or concurrent, such as the well-known Bwtree [72] and the Mass-tree [50]. However, concurrent structures do not exploit the inherent advantages of batching; consistent with prior findings [65], Sec. 4 shows that they run an order of magnitude slower than parallel trees in batch updates. Other studies have explored binary trees with expanded node sizes [26, 27], but they remain a suboptimal compromise for I/O efficiency (also see Fig. 1), due to looser tree-height bounds compared to a true B/B+ -tree, and none offer non-trivial cache complexity. Challenges in Designing Efficient Parallel B/B+ -trees. The primary challenge in parallelizing B/B+ -trees lies in achieving low-cost structural repairs without eroding their I/O advantage. While the high fan-out in a B/B+ -tree decreases memory transfers (i.e., the cache complexity), it does not reduce the total work (in terms of the number of comparisons), and is inherently more complicated to deal with. Whereas BST rotations remain strictly local, the high fan-out nature of B/B+ -trees may cause structural imbalances (overflows or underflows) to propagate across neighboring parallel subtasks, demanding dedicated efforts to repair. Since the reduction in memory access, Θ(log2 𝐵), is relatively modest in practice, any overhead added to reconcile structural modifications is subtracted from the sole term that constitutes the benefit. Consequently, a merely correct design is easily slower than a well-tuned parallel BST.

Abstract

arXiv:2611.09172v1 [cs.DS] 6 Nov 2026

The 𝐵 + -tree is a ubiquitous search index due to its provable I/O (cache) efficiency. Yet unlike batch-parallel binary search trees, which are both fast and widely available, no batchparallel 𝐵 + -tree offers strong empirical performance together with provable, near-optimal I/O efficiency. Prior 𝐵 + -treebased designs are either parallel but purely theoretical, with no high-performance implementation, or concurrent indexes such as the Bw-tree and Mass-tree, which run an order of magnitude slower on batch updates. We present PaB-tree, the first batch-parallel 𝐵 + -tree with guarantees on work, span, and cache complexity alongside strong practical performance. Its core challenge—repairing node overflows and underflows without eroding the tree’s I/O advantage—is resolved by one simple invariant: a repair never touches a sibling and is always pushed to the parent. A Promote primitive reduces batch construction and insertion to repeated node promotion, and batch deletion to reinsertion. Batch updates take 𝑂 (𝐵 log𝐵 𝑛) work and 𝑂 (log𝐵 𝑛) I/O per element, matching the sequential 𝐵 + -tree bounds, with polylogarithmic span. Against highly optimized parallel and concurrent baselines, PaB-tree delivers the best overall performance trade-off: up to 1.4× faster on construction and up to 2.0× faster on batch insertion than the strongest baseline, while preserving 𝐵 + -tree query efficiency.

1

Introduction

B/B+ -trees [7, 23] are among the most fundamental data structures and search indexes, widely adopted in both inmemory and external-memory systems. In this paper, we focus on the in-memory setting. Unlike binary search trees (BSTs), which use a single key as a separator, B/B+ -trees keep a Θ(𝐵)-way fan-out so that each node aligns with the hardware access unit (typically a few cache lines in the inmemory setting). Every node access therefore fetches Θ(𝐵) keys for comparison, and a single access is logically equivalent to descending Θ(log 𝐵) levels of a BST. This design positions the B/B+ -tree as one of the most canonical data structures for achieving provable I/O (cache) efficiency. Backed by this theoretical guarantee, in-memory B/B+ -trees typically outperform binary trees by 2–8× in the sequential setting, and therefore have been natively offered across a wide spectrum of software libraries [10, 11, 36, 37, 66]. Batch-Parallel Paradigm. Driven by growing data scales and the multicore era, batch-parallel data structures have attracted significant research interest [1, 5, 14, 17, 26, 27, 29, 1

Conference’17, July 2017, Washington, DC, USA Sequential: ×102

3

Time in seconds

2

Parallel: 2 1

2.6×

1

1.3× 1.7×

(a) Build

12

2

×10−3

8

2.5×

1

×10−3

×10−2

0.8×

12 8 4

×101

1.8×

2 1

4

1.4× 4

2

1.8× 2.7×

(b) Insert(1%) (c) Insert(10%)

9 6

complexity. A batch insertion or deletion incurs 𝑂 (𝐵 log𝐵 𝑛) work and 𝑂 (log𝐵 𝑛) I/O cost per element, matching the bounds of a sequential 𝐵 + -tree, and both operations achieve polylogarithmic span (Thm. 3.1 and Thm. 3.3). The theoretical efficiency also translates into strong performance in practice. Fig. 1 confirms this observation: PaB-tree matches the cache-friendliness of sequential 𝐵 + -tree without sacrificing parallelism, and excels when processing large batches. Fig. 4 confirms this trend on a more comprehensive benchmark across different operations, data distributions, and more baselines. Overall, PaB-tree achieves the best performance trade-off among various existing data structures. It has an advantage in parallel construction and batch insertions, scaling especially well to processing large batches, as well as outperforming all other tree-based baselines on queries. As a result, PaB-tree demonstrates consistent gains on real-world geometric and graph workloads (Sec. 4.2 and Sec. 4.3). We release our anonymous code [51].

×10−1

7.4×

CPAM (BST with leaf blocking)

PAM (BST)

×10−1

TLX B+-tree

Std::Set (BST) 3

2

2.5×

1

×100

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

×10−3 1.5× 1.8×

3

PaB-tree 15 10 5

(d) Find

×10−2

3.8×4.5×

(e) Report

Figure 1. Running time (in seconds) of the sequential and parallel BSTs and 𝐵 + -trees. Lower is better. We measure the time under a uniform distribution, including the time to build a tree containing 108 entries and the time to insert 1% and 10% of entries into the tree. The query time is measured by searching 106 entries, and reporting [103, 105 ] entries in a range.

This raises a critical question: Can the high fan-out design of B/B+ -trees still offer provable cache efficiency in the parallel setting, and can this advantage translate into better performance in practice? In this paper, we answer the question affirmatively by presenting the PaB-tree, the first batch-parallel B+ -tree implementation with both theoretical guarantees (work, span, cache complexity) and strong practical performance across a wide range of workloads. Approach Overview. In light of the challenges discussed above, our design prioritizes conceptual simplicity to minimize parallel overhead during structural repairs. The design follows a single rule: a repair never touches a sibling; it is always pushed to the parent. The difficulty is that a repair must never reach sideways to a sibling, which another parallel task may be modifying at the same time; instead, every repair travels up the ancestor path the recursion already owns. We realize this by having each recursive call return a heavy node—a possibly oversized node that the parent absorbs and re-partitions—rather than a fixed-shape subtree, and by keeping a node-capacity margin that lets the more involved deletion cost amortize fully. A single overflow-like operation (our Promote primitive detailed in Sec. 3) resolves an oversized heavy node, and both construction and insertion reduce to repeated applications of it. Underflow in batch deletion, however, is more challenging to handle. Our solution reduces underflow repair to insertion—an operation we have already made parallel and cache-efficient—so no node ever consults a sibling. Specifically, given a set of underflowed subtrees invalidated by a batch deletion, we carefully identify a few entry points for them to be reinserted, letting them share the work, such that the total overhead can be bounded in an amortized fashion (Thm. 3.3). Fig. 5 shows that the reinserted volume also stays modest in practice, so the reduction is inexpensive as well as simple. Results Summary. For both batch insertion and deletion, PaB-tree achieves provable bounds on work, span, and cache

2

Preliminaries

This section reviews the analysis models, background on 𝐵 + -trees, and key subroutines that we will use to prove theoretical guarantees on the PaB-tree operations. In this paper, we use 𝑛 to denote the input size or the tree size. We write log 𝑛 for log2 (𝑛 +1), and log𝐵 𝑛 for log𝐵 (𝑛 +1). Computational Model. We assume a shared-memory multiprocessor that supports fork-join parallelism with binary forking [6, 15, 18]. A thread is a sequential RAM with a fork instruction that creates two parallel child threads and suspends the parent until both finish; a parallel for-loop compiles to a logarithmic number of forks. We analyze our algorithms using the work-span model, where the work is the total number of operations in the algorithm, and the span is the longest dependence chain in the parallel computation graph. On 𝑝 processors, a randomized work-stealing scheduler executes a computation with work 𝑊 and span 𝑆 in 𝑊 /𝑝 + 𝑂 (𝑆) time with high probability in 𝑊 [6, 18, 40]. We use I/O cost to refer to cache complexity, and analyze it using the ideal-cache model [3, 33]: a cache of size 𝑀 above an unbounded memory, exchanging size-𝐵 blocks at unit cost under an optimal offline policy. The cache complexity is the total number of block transfers. We also use 𝐵 for the block size of our PaB-tree, which can be any value in Θ(𝐵). 𝑩 + -trees. The B+ -tree is a canonical data structure for storing ordered data. Every node keeps a Θ(𝐵) fan-out so that it aligns with a hardware access unit (e.g., a cache line or a disk block). All entries are stored in the leaves, and all leaves are at the same depth. Each leaf contains a sequence of entries in sorted order. An interior node contains a sequence of child pointers and a sequence of splits that separate its children. Every interior node except the root has between B and 4B child nodes. A leaf can hold more entries since it stores no child pointers. However, for simplicity we assume that a leaf 2

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Conference’17, July 2017, Washington, DC, USA

Algorithm 1: PaB-tree Primitive: Promote

4 6 9 11 15 21 23 25 29 33 35 39 A

B

C

D

E

F

G

H

I

J

K

L

Heavy node

Overflow 4 15 29 4 6 9 11 A

B

C

New heavy node 29 33 35 39

15 21 23 25 D

E

F

G

H

I

J

K

L

Valid B+-tree nodes

Figure 2. Illustration of the Promote primitive. Assume 𝐵 = 2. Then Promote adjusts each node to a fan-out of 2𝐵 = 4. Trapezoids with uppercase letters represent subtrees. The virtual leading keys are marked in dotted boxes. The resulting subtrees are all valid and at the same level.

also holds between B and 4B entries. A B+ -tree with 𝑛 entries has height 𝑂 (log𝐵 𝑛). It can be constructed sequentially with 𝑂 (𝑛 log𝐵 𝑛) work and 𝑂 (𝑛/𝐵 · log𝐵 𝑛) I/O cost. During insertion, a node overflows if its size exceeds 4B. This overflow is resolved by splitting the node into two and promoting the midpoint key to its parent. Conversely, deleting an entry may decrease a node’s size below B. This triggers an underflow that is handled by merging the node with an adjacent sibling and removing a key from the parent. Both overflows and underflows can cascade up the tree, requiring recursive rebalancing.

3

Parallel Algorithms

3.1

PaB-tree Structure and Primitives

A heavy node maintains size: size of the heavy node, also denoted by | · | separators: an array of 𝑏 separator keys subtrees: an array of 𝑏 PaB-tree subtrees // Resolves overflow in heavy node 𝐻 and return a parent heavy node. ′ 1 Function 𝐻 ← Promote(𝐻 ) 2 if 𝐻 is a valid node then return 𝐻 3 𝑏 ′ ← max(⌊|𝐻 |/2B⌋, 1)// to be split into 𝑏 ′ valid PaB-tree nodes 4 𝐻 ′ .size ← 𝑏 ′ 5 parallel-for 𝑖 ← 0 to 𝑏 ′ − 1 do // partition 𝐻 into 𝑏 ′ groups // Group 𝑖 contains the 𝑠-th to the 𝑒-th separator and subtree in 𝐻 , each with similar sizes (differing by at most 1) 6 𝑠 ← ⌊𝑖 · 𝑏/𝑏 ′ ⌋, 𝑒 ← ⌊(𝑖 + 1) · 𝑏/𝑏 ′ ⌋ 7 Create a PaB-tree node 𝑣 using subtrees 𝐻 .subtrees[𝑠..𝑒) and separators 𝐻 .separators[𝑠..𝑒) // Set the 𝑖-th node and separator in return heavy node 𝐻 ′ 8 𝐻 ′ .subtrees[𝑖] ← 𝑣 9 𝐻 ′ .separators[𝑖] ← the first key in 𝑣 10 return 𝐻 ′ // Return the parent heavy node

no upper bound, but all its subtrees must be valid B+ -trees of equal height. This property is crucial, as structural invalidities are isolated and resolved locally within the node, streamlining the overall correctness justification (see Fig. 2 for an illustration). Specifically, a heavy node 𝐻 maintains its size, also denoted by |𝐻 |, and two arrays subtrees[] and separators[], each of size |𝐻 |. Here, 𝐻 .separators[𝑖] is the smallest key in 𝐻 .subtrees[𝑖]. A valid tree node is therefore a heavy node with size in [B, 4B). We use the heavy node as the core operational unit in our algorithms. The Promote Primitive. Our algorithm follows the standard overflow and underflow rebalancing scheme of B+ -trees. We first introduce the Promote primitive (Alg. 1), which simulates the handling of an overflow. It restructures a heavy node into a sequence of valid nodes at the same level, each of size about 2B, and generates a higher-level heavy node. In detail, the Promote first check whether 𝐻 is a valid node, and if so, returns it directly. This is consistency with the definition of a heavy node since a valid node is also a heavy node. Otherwise, it partitions the 𝑏 subtrees and separators of a heavy node 𝐻 into 𝑏 ′ =⌊𝑏/2B⌋ groups, each of size ⌈𝑏/𝑏 ′ ⌉ or ⌊𝑏/𝑏 ′ ⌋. It then packs each group into a standard node and extracts its leading key to form 𝑏 ′ separators. Crucially, even when 𝐻 does not overflow, at least one separator is still promoted: the Promote packs 𝐻 into a single node and promotes the key paired with it, so the operation applies uniformly. The resulting 𝑏 ′ subtrees and separators form a smaller heavy node, which is then passed to the parent (Fig. 2). The Promote primitive extends the sequential overflow process naturally, and also admits parallelism: the grouping depends only on local indices, so all subtrees and separators are processed in parallel, resolving an overflow of any size in a single step. With this simple primitive, our insertion algorithm largely reduces to applying this primitive repeatedly, and our deletion algorithm also implicitly leverages it.

In this section, we present the design of PaB-tree. A PaBtree is conceptually a B+ -tree, where all data entries reside in the leaf nodes and internal nodes store separators as routing keys. Unlike a standard B+ -tree, where a node with 𝑏 subtrees contains 𝑏 − 1 separators, an internal node in the PaB-tree always maintains 𝑏 separators and the same number of subtrees, where each subtree follows a key. A key and the subtree following it are paired. Such a node can be viewed as a regular B+ -tree node augmented with a leading key, which is the smallest key in its subtree. We always augment the entire dataset with a leading key −∞ to ensure correctness. Fig. 2 and Fig. 3 both illustrate this scheme. The leading key simplifies the algorithm design, since handling internal and leaf nodes can then follow the same logic. It also simplifies our proofs. In practice, there is no need to store the leading key explicitly, since it can always be retrieved from the recursive calls. A valid node has size in [B, 4B). Any 𝑐𝐵 with 𝑐 > 2 works as the upper bound and guarantees theoretical and practical efficiency. We fix 𝑐 = 4 for simplicity, and later show in our proofs how it bounds the costs. Heavy Node. The concept of a heavy node simplifies the description of the PaB-tree algorithms. A heavy node encapsulates the transient state of an invalidated B+ -tree node. We allow a heavy node to have any size of at least B, with 3

Conference’17, July 2017, Washington, DC, USA

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

in 𝑇 and recurse in parallel on every pair of subtree and slice. Each recursive call returns a heavy node. Because every heavy node retains its leading key, these results concatenate directly into one transient heavy node 𝐻 ′ . A final call to Promote(𝐻 ′ ) further partitions 𝐻 ′ into valid subtrees and returns them to the parent as a heavy node (line 20). Parallel Construction. We construct a PaB-tree in parallel by inserting a batch of entries 𝐸 into an empty tree. This is equivalent to viewing the entire batch as one large heavy node and applying Promote to it repeatedly, until a valid root is generated. Theoretical Analysis. We can now show the bounds for the PaB-tree insertion algorithm.

Algorithm 2: Batch Insertion Input: A sequence of entries 𝐸 and a PaB-tree 𝑇 . Output: A PaB-tree with 𝐸 inserted. // Insert the entries 𝐸 into 𝑇 and maintain the 𝐵 + -tree properties Function BatchInsert(𝑇 , 𝐸) 2 Sort the entries in 𝐸 by their keys 3 𝐻 ←InsertSorted(𝑇 , 𝐸) // Insert new entries into leaves 4 while 𝐻 .size ≥ 4B do 5 𝐻 ← Promote(𝐻 ) 6 return 𝐻 // Insert sorted entries 𝐸 into 𝑇 ; return updated node, possibly heavy 7 Function InsertSorted(𝑇 , 𝐸) 8 if 𝐸 is empty then return 𝑇 // Unchanged 9 if 𝑇 is a leaf then 10 Insert 𝐸 into 𝑇 in place // Use Promote to split the tree when necessary, which also identifies the upper-level separators to return to the parent 11 return Promote(𝑇 ) // Otherwise, 𝑇 is an interior node; continue recursive insertion 12 𝑏 ← 𝑇 .size 13 𝑃 [0..𝑏) ← Slices of 𝐸 partitioned by 𝑇 .separators 14 Initialize H as a sequence of 𝑏 heavy nodes, which will hold the results returned by the 𝑏 recursive calls 15 parallel-for 𝑖 ← 0 to 𝑏 − 1 do // Recursively insert 16 H [𝑖] ←InsertSorted(𝑇 .subtrees[𝑖], 𝑃 [𝑖]) Initialize 𝐻 ′ as a heavy node, which will represent the state of 17 𝑇 after absorbing all insertions 18 𝐻 ′ .subtrees ← concatenate all H [·].subtrees[] in order 19 𝐻 ′ .separators ← concatenate all H [·].separators[] in order // Resolving possible overflow and pass new separators to parent 20 return Promote(𝐻 ′ ) 1

Theorem 3.1. Given a PaB-tree of size 𝑛, a batch insertion of 𝑚 entries takes 𝑂 (𝐵𝑚 log𝐵 (𝑚 + 𝑛)) work, 𝑂 (𝑚 log𝐵 (𝑚 + 𝑛)) I/O cost, and 𝑂 (log 𝑛 log(𝑚 + 𝐵)) span. The I/O cost per entry is 𝑂 (log𝐵 (𝑚 + 𝑛)), which aligns with the sequential I/O cost of B/B+ -trees. The work bound is larger by a multiplicative factor of 𝑂 (𝐵). Given the high compute throughput and limited memory bandwidth of modern processors, our PaB-tree is rarely bottlenecked by computation, unless the tree fits in cache. The span is polylogarithmic. The analysis of I/O cost is based on the following fact. Fact 3.2. Given a PaB-tree with 𝑛 leaves and height no more than ⌈log𝐵 𝑛⌉, the total number of
nodes among any 𝑚 leaves 𝑛 and their ancestors is 𝑂 𝑚 log𝐵 𝑚 .

Below, we detail the complete algorithms based on the heavy node and the Promote primitive. 3.2

Because the fan-out of a PaB-tree is at least 𝐵, this height is an overestimation. We pessimistically assume that all nodes in the top ⌈log𝐵 𝑚⌉ levels are ancestors of the 𝑚 leaves, which gives 𝑂 (𝑚) nodes in total. Each of the remaining ⌈log𝐵 𝑛⌉ − ⌈log𝐵 𝑚⌉ = 𝑂 (log𝐵 (𝑛/𝑚)) levels contains at most one ancestor per leaf, hence at most 𝑚 nodes, which leads to the stated bound. We can now prove the batch insertion bounds in Thm. 3.1. Proof of Thm. 3.1. We can directly obtain the I/O bound from Fact 3.2. Since each node in a PaB-tree aligns with 𝑂 (1) memory blocks (cache lines), inserting 𝑚 entries into a tree of size 𝑛 can touch at most the number of nodes bounded by Fact 3.2. This corresponds to 𝑂 (𝑚 log𝐵 ((𝑚 + 𝑛)/𝑚)) cache line reads and writes. Note that this bounds the nodes touched in the output tree. The input tree (before modification) must also be accounted for, but in an insertion operation, the number of tree nodes in the input tree is less than or equal to that of the output tree. Adding both together yields the stated 𝑂 (𝑚 log𝐵 ((𝑚 + 𝑛)/𝑚)) I/O bound. We also need to sort the input entries (line 2) with 𝑂 (𝑚 log𝑀 𝑚) I/Os [16], and adding all pieces gives the overall 𝑂 (𝑚 log𝐵 (𝑚 + 𝑛)) I/O bound. The work bound is obtained by multiplying the I/O cost by 𝐵. As each node is accessed and processed, operations such as scanning, merging, and concatenating all take work linear in the input size, which is 𝑂 (𝐵). Therefore, the total work excluding the sorting part is 𝑂 (𝐵𝑚 log𝐵 (𝑚 + 𝑛)). Sorting

Batch Insertion and Construction

We now present our parallel batch update algorithms for PaB-trees. We consider the batch-parallel setting, where a batch of entries is inserted into or deleted from the current PaB-tree 𝑇 . We start with the insertion algorithm. With the Promote primitive, the insertion process is relatively straightforward. We present the algorithm in Alg. 2 and illustrate it in Fig. 3. The algorithm inserts a batch of entries 𝐸 into a PaB-tree 𝑇 . We first sort all keys in 𝐸, then follow a divide-and-conquer scheme and pass all entries to the root by calling the helper function InsertSorted. This function takes a subtree 𝑇 and inserts the sorted entries 𝐸 into it. It returns a heavy node 𝐻 holding the subtrees replacing 𝑇 , each paired with its leading key. By definition, the returned node is a sequence of 𝑏 ′ separators, each followed by a subtree. Here 𝑏 ′ can be any integer no smaller than B. InsertSorted has two base cases: 1) an empty batch leaves the subtree unchanged, and 2) a leaf merges the entries 𝐸 in place and calls Promote. Even though a leaf stores no subtrees, the Promote logic applies identically, with the entries playing the role of subtrees; i.e., it splits the leaf into new leaves of about 2B entries each and promotes the leading keys. At an internal node, we partition 𝐸 by the separators 4

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Insertion Batch: { 26, 27, 28, 29, 30, 31, 34 } 2. Leaf Merges and 1. Scatter -∞ 25 33 Returned Heavy Nodes -∞ 19

25 29

33 38

Conference’17, July 2017, Washington, DC, USA

4. Final Tree -∞ 27

3. Recursively Returned Heavy Node

-∞ 19 25 26 27 28 29 30 31 33 34 38

-∞ 25 27 29 33

-∞ 19 25 26 27 28 29 30 31 33 34 38

-∞ 25

27 29 33

…… ……

Figure 3. An illustration of the batch insertion algorithm with 𝐵 = 1. The algorithm runs in an asynchronous divide-and-conquer approach, and the output of each subtree is always a heavy node. The two heavy nodes each with a size over 4 apply the Promote function.

the subtrees and collects the updated subtrees. If at least 𝐵 subtrees survive (line 13), we build a node wraps them and return it (line 15). If fewer survive, node 𝑇 underflows. The algorithm removes it and returns ∅ to mark its absence (line 14). The surviving subtrees of the underflow node are set aside and later reinserted into the global PaB-tree. This involves collecting all dropped subtrees into an array in parallel, using a prefix sum over per-node counts to compute offsets, and then group subtrees by height for reinsertion. Reinserting these subtrees uses the same insertion algorithm (Alg. 2). The only difference is that the inserted items are subtrees instead of leaf entries. The logic of Alg. 2 still applies to both cases, because inserting a height-ℎ subtree into a node at height ℎ + 1 is the same operation as inserting an entry into a leaf. Theoretical Analysis. We now analyze the complexity of batch deletion, which is summarized in Thm. 3.3. The highlevel idea is to amortize the cost of reinsertion over the deletions that caused it. A node is created with at least 2𝐵 children and is dropped only when fewer than 𝐵 elements remain, so at least 𝐵 deletions must happen below it before triggering a reinsertion. Those 𝐵 deletions together have paid 𝑂 (𝐵 log𝐵 𝑛), which covers reinserting the at most 𝐵 surviving subtrees.

Algorithm 3: Batch Deletion Input: A sequence of unsorted entries 𝐸 and a PaB-tree 𝑇 . Output: A PaB-tree with 𝐸 deleted. Function BatchDelete(𝑇 , 𝐸) Sort the entries in 𝐸 by their keys 3 DeleteSorted(𝑇 , 𝐸) // Remove entries from 𝑇 4 Group the dropped subtrees in line 14 by height, and reinsert each group into 𝑇 using Alg. 2

1

2

Function DeleteSorted(𝑇 , 𝐸) if 𝐸 is empty then return 𝑇 7 if 𝑇 is a leaf then Remove 𝐸 from 𝑇 , and return 𝑇 // 𝑇 is an interior node; continue the recursive deletion. 8 𝑃 ← Slices of 𝐸 partitioned by 𝑇 .separators 9 𝑏 ← 𝑇 .size 10 Initialize N as a sequence of 𝑏 PaB-tree nodes, which will hold the results returned by the 𝑏 recursive calls 11 parallel-for 𝑖 ← 0 to 𝑏 − 1 do // Recursively delete 12 N [𝑖] ←DeleteSorted(𝑇 .subtrees[𝑖], 𝑃 [𝑖]) 13 if the number of non-empty N [𝑖] is less than 𝐵 then 14 Drop non-empty N [𝑖] to be reinserted later, and return ∅ 15 Create a PaB-tree node 𝑁 by concatenating N , and return 𝑁 5

6

takes 𝑂 (𝑚 log 𝑚) = 𝑂 (𝑚 log(𝑚 + 𝑛)) = 𝑂 (𝐵𝑚 log𝐵 (𝑚 + 𝑛)); thus, the total work remains 𝑂 (𝐵𝑚 log𝐵 (𝑚 + 𝑛)). Finally, we analyze the span bound. The insertion algorithm recurses for log𝐵 𝑛 levels. At each level, the parallel-for loop of size 𝐵 produces a span of log 𝐵. Multiplying these two factors yields a span of log 𝑛. At each level, the work for operations including merge and concatenate can be trivially parallelized with a span logarithmic in the input size. Since the worst-case input size is 𝑚 + 𝐵, the span per level is bounded by 𝑂 (log(𝑚 + 𝐵)). Together, the total span is bounded by 𝑂 (log 𝑛 log(𝑚 + 𝐵)), leading to the stated bound. □ 3.3

Theorem 3.3. Given a PaB-tree of size 𝑛, batch deleting 𝑚 entries takes 𝑂 (𝐵𝑚 log𝐵 𝑛) amortized work, 𝑂 (𝑚 log𝐵 𝑛) amortized I/O cost, and 𝑂 (log2 𝑛 log(𝑚 + 𝐵)) span. Proof. We analyze the complexity by dividing the deletion process into two phases: the DeleteSorted execution and the subsequent subtree reinsertions. We first bound the I/O cost. The DeleteSorted phase recursively routes the deleted entries down to the tree leaves and removes them. Since this phase requires no structural repairs and follows a simpler access pattern than InsertSorted, its I/O cost is 𝑂 (𝑚 log𝐵 𝑛). The reinsertion phase requires an amortized analysis. By the definition of the PaB-tree structure, any valid tree node is initially constructed with a fan-out of at least 2𝐵. During deletion, a node is dropped only if the number of its remaining subtrees falls below the degree bound 𝐵. This implies that at least 𝐵 subtrees must have been previously dropped to trigger the drop of the current node. Generalizing this property, we know that for a subtree at height ℎ (where leaves are at ℎ = 0) to underflow and be dropped, at least 𝐵ℎ entries must have been deleted from it. When such a subtree drops, we collect its remaining valid

Batch Deletion

Classic underflow logic is inherently sequential. An underflowing node is repaired by borrowing from or merging with a sibling, so the outcome depends on that sibling rather than on the node alone. A batch of deletions may trigger many underflows at once, and their repairs would conflict: the sibling borrowed from may itself underflow, or may be deleted entirely. Resolving these interactions requires serializing the dependencies among the repairs, which blocks parallelism. Our deletion algorithm (Alg. 3) avoids these interactions entirely, and the design is straightforward. It follows the same divide-and-conquer approach as the insertion algorithm to maximize efficiency. The algorithm first checks whether it has reached a base case: an empty entry list or a leaf node. Otherwise, it recursively deletes the entries in 5

Conference’17, July 2017, Washington, DC, USA

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

subtrees and reinsert them into the PaB-tree. Since there are at most 𝐵 subtrees left, reinserting them incurs an I/O cost of 𝑂 (𝐵 log𝐵 𝑛). We can charge this cost to the previously deleted entries in this subtree following a standard amortized analysis: each previously deleted entry pays 𝑂 ((𝐵 log𝐵 𝑛)/𝐵ℎ ) = 𝑂 ((log𝐵 𝑛)/𝐵ℎ−1 ) for the restructuring of its height-ℎ ancestor. Summing this geometric series across all heights from ℎ = 1 to 𝑂 (log𝐵 𝑛) yields an amortized cost of 𝑂 (log𝐵 𝑛) per entry. Combining this with the 𝑂 (log𝐵 𝑛) per-entry I/O cost from the DeleteSorted phase, we obtain an overall I/O cost of 𝑂 (𝑚 log𝐵 𝑛) for batch deletion. The work bound analysis is similarly structured. In the DeleteSorted phase, the algorithm performs simple data scanning and key routing without structural repairs, and its work is bounded by a factor of 𝐵 times its I/O cost. For the reinsertion phase, because the algorithm directly reuses the batch insertion subroutine, its work likewise remains a factor of 𝐵 times its I/O cost. Scaling the overall amortized I/O cost by 𝐵 yields an amortized work complexity of 𝑂 (𝐵𝑚 log𝐵 𝑛). Finally, we analyze the span bound. The span of the DeleteSorted phase is bounded by that of the InsertSorted phase. However, rather than inserting all dropped subtrees simultaneously, we group the dropped subtrees by height and iteratively reinsert each group level by level. This iterative approach adds an extra 𝑂 (log𝐵 𝑛) factor to the span depth. Multiplying the span of the insertion algorithm by this factor yields an overall span bound of 𝑂 (log2 𝑛 log(𝑚 + 𝐵)). This extra log factor could be removed by reinserting all heights together, at the cost of redesigning insertion. Since the span is already polylogarithmic and parallelism is strong in practice, we keep the simpler design. □ 3.4

to existing tree-based baselines. Experimental Setup. We perform experiments on a machine with 112 cores (224 hyper-threads), four Intel Xeon Platinum 8176 CPUs, and 1.47 TB RAM. We implement PaB-tree in C++ and compile it with GCC 15.2.0 with the -O3 optimization flag. We use ParlayLib [12] for fork-join parallelism. The reported numbers are the average of 3 runs after a warm-up run. We use block size 𝐵 = 641 and set the leaf randomness ratio 𝛼 = 0.5. The entries are sorted when the tree is initialized. We release our code at [51]. Baselines. We compare with several state-of-the-art batchparallel and concurrent data structures. For the parallel case, we evaluate (1) PAM [65], a parallel binary search tree, (2) CPAM [26], which improves the cache-friendliness of PAM with leaf wrapping, and (3) PMA [73, 77], a Packed Memory Array that stores all entries in a single contiguous sorted array, optimized for queries. For the concurrent case, we evaluate (1) Mass-tree [50] and (2) Bw-tree [72], two wellknown in-memory concurrent 𝐵 + -tree implementations. 4.1

Setup. We test different batch update patterns and key distributions. We test both the static and dynamic cases. In the static case, we measure the time to construct a tree with 109 entries. In the dynamic case, we measure both the incremental insertion and deletion. For insertion, we divide 𝑛 = 109 entries into batches of size 𝑚 and insert them into the tree 𝑛/𝑚 times, starting from an empty tree. For deletion, we first construct a tree with all entries, then similarly remove them in batches until the tree is empty. We report the total time of all batches. Under this workload, we also measure the query performance when half of the batches are applied. We evaluate membership (Find) and range queries (Range-Report): 108 random Find queries and 5 × 104 Range-Report queries, with range sizes spanning 102 to 104 . The query implementations all directly follow the standard B+ -tree algorithms. Each query runs serially, with different queries in parallel. We also test the update time for a single batch, compare it with that of sequential point updates, and show the results in Secs. A and D. We use three key distributions for batches: uniform (Uni), skewed (Skew), and adversarial (Adv). Uni generates keys uniformly at random within the range. Skew generates keys from a normal distribution with mean 0.5 and standard deviation 0.1, which simulates the real-world scenario where the data in a batch has certain locality. Adv sorts the keys before dividing them into batches, so that each batch contains a consecutive range of keys. This simulates the worst-case scenario for PaB-tree, since the batch updates always trigger the largest possible subtrees to overflow or underflow, maximizing the cost of node splitting and reinsertion. However, this is the best case for PAM and CPAM since their

Optimizations

To better accommodate dynamic workloads, PaB-tree incorporates a probabilistic leaf-sorting strategy controlled by the leaf randomness ratio 𝛼: an update leaves a leaf unsorted with probability 𝛼, and re-sorts it otherwise. Accordingly, queries scan an unsorted leaf linearly instead of using a binary search. For write-heavy workloads, this reduces the work of batch updates (e.g., insertions can directly append), at the cost of slightly slower queries. Note that the I/O cost is not affected because once a leaf node is loaded into cache, scanning it incurs no additional cache misses. We use 𝛼 = 0.5 by default, but a user can adjust it according to the update/query ratio of their target workload. We experimentally evaluate this strategy in Sec. 4.5.

4

Evaluation on Synthetic Benchmark

Experiments

We conduct comprehensive experiments to evaluate the performance of PaB-tree against several baselines on both synthetic and real-world datasets. Our results show that PaB-tree offers a clear advantage in batch updates while delivering competitive or better query performance compared

1 Evaluation for different block sizes is shown in Sec. B.

6

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Adversarial

Skewed

Uniform

Dist.

Trees

Build

PaB-tree PAM CPAM PMA Mass-tree Bw-tree PaB-tree PAM CPAM PMA Mass-tree Bw-tree PaB-tree PAM CPAM PMA Mass-tree Bw-tree

1.25 2.11 1.70 3.45 96.6 39.6 1.25 2.18 1.79 3.40 87.8 39.5 1.34 2.33 1.81 3.59 87.5 39.2

0.01% 29.4 29.8 55.2 30.1 88.4 55.8 25.7 27.0 48.4 39.3 86.4 52.9 7.75 8.40 7.59 192.0 84.7 55.1

Conference’17, July 2017, Washington, DC, USA

Incremental Insert Batch Size 0.1% 1% 15.3 5.06 19.2 11.8 30.9 7.29 19.0 13.3 77.8 77.0 39.6 33.3 11.7 3.65 16.6 9.26 21.0 5.10 27.8 20.3 75.7 75.8 38.9 33.2 4.50 2.55 5.52 4.57 3.42 2.23 82.2 36.2 78.1 76.5 36.8 32.2

The fastest time is in bold and underlined

10% 1.68 5.70 1.81 9.88 81.4 32.9 1.41 3.80 1.56 9.68 79.3 33.0 1.99 4.07 1.76 14.2 79.9 33.5

: < 1.1x the fastest

Query after Inc. Ins. Incremental Delete Range Batch Size Find Report 0.01% 0.1% 1% .099 .078 19.6 11.5 5.40 .128 .496 28.8 18.7 11.3 .098 .088 54.4 30.9 7.03 .031 .073 22.0 16.6 8.92 .082 .594 64.4 55.2 53.7 .222 .455 63.2 43.8 39.6 .073 .079 19.2 9.96 3.70 .108 .500 25.8 16.2 8.80 .081 .087 48.0 21.1 4.43 .025 .095 27.1 22.1 11.4 .067 .554 64.0 54.6 53.3 .161 .459 59.6 42.0 36.1 .044 .081 7.14 2.60 1.68 .069 .503 8.96 4.90 3.66 .056 .087 4.96 2.13 1.35 .018 .096 143.4 74.7 20.0 .064 .580 64.6 55.6 54.5 .109 .450 61.7 38.6 35.2 : < 1.5x the fastest

: < 2x the fastest

10% 1.77 5.50 1.58 3.01 53.9 39.1 1.82 3.76 1.36 4.30 53.4 35.6 1.36 3.35 1.13 3.83 54.6 36.2

: < 5x the fastest

Query after Inc. Del. Range Find Report .078 .085 .130 .497 .099 .087 .034 .099 .103 .813 .235 .632 .074 .087 .124 .501 .093 .087 .030 .107 .088 .817 .174 .667 .043 .086 .076 .501 .063 .088 .021 .106 .065 .738 .113 .534 : > 5x the fastest

Figure 4. Running time (in seconds) on synthetic data. Lower is better. The fastest running time for each dataset is bold and underlined. We use different colors to mark results within 1.1×, 1.5×, 2×, 5× and > 5× of the fastest time. Detailed settings for build, queries, and incremental insertion/deletion are introduced at the beginning of Sec. 4.1.

algorithms reduce to simply merging in or splitting out a subtree on the right spine. We use 32-bit integer keys and values, and summarize the results in Fig. 4. Construction. For tree construction, our PaB-tree is consistently faster than all baselines across all workloads. This advantage mainly comes from the shallower tree height and the blocked node layout of the 𝐵 + -tree, which enable fewer memory allocations and yield better cache behavior. Both PAM and CPAM are binary trees with higher tree heights, and are therefore up to 1.7× and 1.4× slower than PaB-tree, respectively. The PMA is up to 2.8× slower than PaB-tree, possibly due to the additional work required to scatter entries across the underlying array. More detailed hardware profiling is provided in Sec. 4.4. Both concurrent indexes, Mass-tree and Bw-tree, are orders of magnitude slower than PaB-tree, as concurrent insertion on a large batch incurs high node contention. Batch Updates. For batch updates, PaB-tree retains its advantage in most cases. It is always faster than the state-ofthe-art BST PAM (by up to 3.4×). In contrast, while CPAM also leverages larger node sizes to improve I/O performance, it can be up to 1.9× slower than the standard BST in PAM, particularly on small batch sizes. Altogether, on the Uni and Skew cases, PaB-tree is also almost always faster than CPAM, by up to 2.8×. On large deletion batches (10%) of Uni and Skew data, and more markedly on Adv data, CPAM outperforms PaB-tree. As noted earlier, the Adv workload consistently inserts 𝑚 keys strictly larger than the tree’s maximum value or deletes the 𝑚 smallest keys. This represents the worst-case scenario for PaB-tree because it is more prone to triggering node

overflows and underflows; hence, we include this workload as a stress test for PaB-tree. Interestingly, this is the best-case scenario for PAM and CPAM, as their Join-based algorithms simply merge or split trees along the rightmost path, reducing the cost to 𝑂 (log 𝑛 + 𝑚), rather than 𝑂 (𝑚 log 𝑛) in the general case. In this adversarial case, PaB-tree is expectedly slower than CPAM, but only by 1.02–1.32× for insertions and 1.20–1.44× for deletions. It also remains faster than PAM at every batch size, by up to 2.0× for insertions and 2.5× for deletions. Compared to the other baselines, including PMA, Masstree, and Bw-tree, PaB-tree is faster in every batch-update case. As an array-based structure, PMA optimizes queries at the cost of update efficiency. As a result, PaB-tree is on average 4.0× faster (up to 28.7×) than PMA on updates. Furthermore, both concurrent data structures perform worse than batch-parallel ones on batch updates, since larger batches increase contention rather than parallelism; PaB-tree achieves an average speedup of 13.1× (up to 56×) over Mass-tree and 7.9× (up to 27×) over Bw-tree. Queries. As expected, B-tree-like structures, including PaBtree, Mass-tree, and even CPAM, perform better than the strict BST PAM on all queries. In Find queries, PMA has a significant advantage over all other implementations, due to its array-based layout and query-focused optimizations. However, this comes at the cost of updates that are up to 28.7× slower than those of PaB-tree. Apart from PMA, PaBtree is almost always the fastest, or within 10% of the fastest, among the tree-based structures in Find queries. For RangeReport queries, PaB-tree is the fastest in four of the six cases and within 7% of the fastest in the other two. It achieves speedups of up to 6.4× over PAM, up to 1.1× over CPAM, up 7

PaB-tree

Bw-tree

14 15 16 17 18 19 20 21 22 23

(c) Find Query

2

1

1

(d) Range Report

Insert Delete Neighbor Flatten

1 14 15 16 17 18 19 20 21 22 23

(e) Size Breakdown Insert Batch

Insert Overflow

Delete Batch

Delete Underflow

2

1

1 Insert Delete Neighbor Flatten

0.4

6.5× Delete Neighbor Flatten

7.9× Insert

Delete Neighbor Flatten

Operations

0.3

Figure 6. Normalized running time of batch updates and queries on temporal graph datasets. Lower is better. Time exceeds 3 times slower than PaB-tree is chopped. Detailed settings can be found in Sec. 4.3. For all operations, we measure the sum of running time across all batches and normalized to the PaB-tree. The Neighbor query lists all neighbors for 107 vertices with the largest degree. The Flatten query outputs all entries in a sorted order.

0.2 0.1 ××××

14

××

15

××

16

17

18

19

Year of the batch

20

21

22

23

Figure 5. Running time (in seconds) of batch updates and queries on the OSM dataset. Lower is better. The inputs are batched by years from 2014 to 2023. In each year, we insert the batch in that year and then delete the batch from three years ago if applicable. After batch updates, we perform the queries on the current index. The Find query contains 108 candidates, and the Range-Report query contains 5 × 105 queries with output size between 102 −104 . Both queries are generated randomly. The yellow and blue bars depict the fraction of input batch sizes w.r.t the tree size in each year. The pink and grey bars show the fraction of overflow and underflow size w.r.t the tree size during the batch insertion and deletion, respectively.

insertions, PAM suffers from its large tree height, and CPAM must maintain a total order within its leaves; these make them slower than PaB-tree by 2.09× and 1.95×, respectively. For deletions, the gap between PMA and the other parallel baselines is smaller, since deletion involves fewer memoryallocation issues. Even though reinserted entries are up to 11.2% of the total tree size, PaB-tree stays up to 1.16× faster than CPAM, showing the practical value of its I/O efficiency. For Find queries, PMA benefits from the absence of pointer chasing and is the fastest among all baselines, 1.07–1.45× faster than PaB-tree. Its advantage on Range-Report queries is smaller, since the output size dominates the query cost. PAM provides better Find performance than PaB-tree and CPAM at small tree sizes, since the latter two must scan all entries in a leaf to find the target key. Meanwhile, without leaf blocking, PAM has poor cache locality when reporting many leaf entries, which also makes it much slower than the others for Range-Report queries. Both concurrent baselines, Mass-tree and Bw-tree, are orders of magnitude slower than PaB-tree for both queries, as locks block the queries.

to 1.2× over PMA, and 5.6–9.6× over Mass-tree and Bw-tree. 4.2

PMA

(d) PLANET 3

2

0.5

0.0

Insert

(c) SEM 3

14 15 16 17 18 19 20 21 22 23

Fraction of tree size

2

10

0.1

3

3.7×

0.1

14 15 16 17 18 19 20 21 22 23

CPAM

(b) REF

6.0×

1

3

6.0×

1

PAM

(a) RED Normalized time

10

1

Mass-tree

(b) Batch Delete

10

0.1

Time (sec.)

PMA

Normalized time

Time (sec.)

PaB-tree PAM CPAM (a) Batch Insert

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

3.8×

Conference’17, July 2017, Washington, DC, USA

Processing Real-world Geometric Data

We evaluate PaB-tree as a general key-value store on a realworld geometric dataset. Setup. We use OpenStreetMap (OSM) [42] as the benchmark. For each record in OSM, we use a 64-bit Morton code that encodes its geographical information as the key, and a 32-bit integer for its timestamp as the value. We divide the 1.35B inputs into 10 batches by their timestamps, from year 2014 to 2023. We simulate a sliding-window setting following the methodology of [53] with window length 3. In each year, we insert the corresponding batch and, where applicable, delete the batch from three years prior. After the update for each year is applied, we run membership queries for 108 randomly picked entries and 5 × 105 range-report queries with output sizes in [102, 104 ]. Results. We summarize the results in Fig. 5. PaB-tree is consistently faster than all baselines for batch updates. For

4.3

Processing Real-world Graph Data

We evaluate PaB-tree as a graph container on temporal graphs. Every edge in a temporal graph has a timestamp, and we group edges into batches by their timestamps (in years) to simulate the evolution of the graph over time. Setup. We compare the baselines on four benchmarks from GraphTide [76]: RED (746M edges, in 17 batches), REF (1.14B 8

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Conference’17, July 2017, Washington, DC, USA

PaB-tree

edges, in 27 batches), SEM (2.49B edges, in 229 batches), and PLANET (1.01B edges, in 20 batches). The batch sizes generally grow over the years. For graphs without explicit insert or delete tags on their edges, such as RED, REF, and SEM, we simulate the sliding-window setting as in Section 4.2 with window length 3; otherwise, we form the insertion and deletion batches according to those tags. For each year, we first apply the batched insertions, then the deletions. After the batch updates in each year, we run two fundamental primitives in graph algorithms: (1) Neighbor(𝑉 ), which retrieves the neighbors of every vertex in 𝑉 , and (2) Flatten, which returns all edges in sorted order, forming a compressed-sparserow-like (CSR-like) array. Flatten is widely used in dynamic graph systems to extract the graph prior to query execution (e.g., the flat snapshot operation in Aspen [27]). We encode each edge as a 64-bit integer and use it as the key, with another 32-bit integer as the value for its timestamp. We sum each operation’s running time over all years and normalize the total to PaB-tree. Results. We summarize the results in Fig. 6. For both batch insertion and batch deletion, PaB-tree is the fastest among all baselines, achieving 1.09–1.60× speedup over the fastest baseline CPAM on insertion and 1.06–1.44× speedup on deletion. This is consistent with the findings in Sec. 4.2: we believe that keeping leaf entries unsorted is the main reason for PaB-tree’s strong batch-update performance, while the overhead of reinsertion-based deletion remains modest in practice. As a static index, PMA is much slower than the others under highly dynamic updates, due to frequent memory allocation and reconstruction; this aligns with the findings on the synthetic datasets (Section 4.1). For graphs with a small average vertex degree (≤ 10), such as PLANET and SEM, Neighbor degenerates to Find, which favors PAM. For large-degree graphs (RED), this advantage diminishes. For Flatten, PAM is the slowest due to excessive pointer chasing, while PMA must skip empty slots in its underlying array; PaB-tree and CPAM are comparable. 4.4

PAM

CPAM

Normalized count

(a) Build (1B)

PMA

(b) Find (10M)

2 1.0 1

0.5 Cycles

Inst. Cache misses

Cycles

Inst. Cache misses

(d) Incremental Delete (1B) 5.2×

3.8×

3

6.3×

Normalized count

(c) Incremental Insert (1B) 2

2 1

1 Cycles

Inst. Cache misses

Cycles

Inst. Cache misses

Hardware counter

Figure 7. Profiling the cycles, instructions and cache-misses of tree construction, incremental batch updates, and membership queries on Skew distribution. Lower is better. The numbers are normalized to PaB-tree. We use the Skew dataset with batch size of 107 , in total 109 entries are processed. Insert (Ours) Insert (CPAM)

Delete (Ours) Delete (CPAM)

0

30

Neighbor query (Ours) Neighbor query (CPAM)

Time (sec.)

3 2 1 0

10

20

40

50

60

70

80

90

100

Randomness (%) Figure 8. Running time (in seconds) of batch updates and Neighbor queries w.r.t different randomness ratio in PaBtree. Lower is better. We use the temporal graph datasets PLANET. The update edges are divided into 20 batches by their timestamps. For each timestamp, after the batch insertion and deletion, we run 107 Neighbor queries. The bar shows the sum of the running time of the batch updates and the Neighbor queries. The corresponding times for CPAM are marked in lines.

Hardware Profiling

We profile the CPU cycles, instruction count, and cache misses of tree construction, incremental batch updates, and Find queries on the Skew distribution, with 109 entries and batches with size of 107 . The instruction count reflects the total work of the algorithm, and the cache misses reflect its I/O efficiency. We summarize the results in Fig. 7 and provide details in Sec. C. PaB-tree benefits the most from its I/O efficiency, which gives it the best performance on tree construction and batch insertion. The low instruction count from the algorithm’s simplicity also contributes to the performance gains of PaBtree. Compared with tree indexes, the PMA incurs the fewest cache misses for Find queries due to the absence of pointer chasing in inner tree structures, which makes it the fastest

for Find queries. However, incremental batch insertion frequently triggers memory allocation and reconstruction of overflowed blocks; as a result, the large number of cache misses and instruction counts make the PMA the slowest for batch insertion. The leaf blocking in CPAM enables it to have a lower tree height than the PAM and therefore fewer cache misses needed to traverse the tree, making it consistently faster than PAM for all operations. 4.5

Evaluation of Randomness in Leaves

We evaluate the impact of sortedness in the leaves on the performance of PaB-tree on the temporal graph dataset PLANET and summarize the results in Fig. 8. The randomness ratio 𝛼 9

Conference’17, July 2017, Washington, DC, USA

PaB-tree 100

PAM

Build, Uniform

10

CPAM 100

Mass-tree

Build, Skewed

10

100

1

1

1

0.1

0.1

Batch Insert, Uniform

1 4 16 32 64 112112h

4.6

Batch Insert, Skewed Batch Insert, Adversarial

100

100

10

10

10

1

1

1

0.1

0.1

0.1

1 4 16 32 64 112112h

1 4 16 32 64 112112h

Scalability

We also evaluate the scalability of the tested indexes on write operations and report the results in Fig. 9. Overall, except for the two concurrent indexes, which do not scale due to lock contention, all indexes scale well on 224 hyper-threads. This indicates that their performance is mostly bounded by the work and I/O efficiency of the underlying algorithms. PaB-tree generally achieves the best scalability for tree construction on 224 hyper-threads (75.6×), much better than the fastest baseline CPAM (50.7×). Similar trends appear for batch updates as well. PMA also scales well for single batch updates, since applying one batch of 1% of the tree size rarely triggers a reconstruction.

1 4 16 32 64 112112h

100

Batch Delete, Uniform

Bw-tree

Build, Adversarial

10

0.1 1 4 16 32 64 112112h

Normalized speedup

PMA

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

1 4 16 32 64 112112h

Batch Delete, Skewed Batch Delete, Adversarial

100

100

100

10

10

10

5

1

1

1

Parallel 𝑩 + -trees. Since the 𝐵 + -tree [7, 23] was introduced in the 1970s, many parallel variants have been proposed in the literature. Early parallel 𝐵 + -trees in the PRAM model focused on improving the bounds on construction [25] and updates [19, 43, 48, 58]. These approaches are based on pipelining and rely on cycle-based synchronization, which makes them unsuited for modern hardware. Goodrich et al. [35] attempted to adapt the Join-based framework [14] to 𝐵 + trees; however, the resulting algorithm exhibits high design complexity, posing significant challenges for practical implementation. These works are purely theoretical, however. Many practical implementations—for DRAM [47, 67, 72, 81], disk [9, 60, 63], persistent memory [21, 30, 49], and GPUs [24, 82, 83]—rely on locks to handle node splits/merges. When processing batch updates, such designs inevitably incur high synchronization overhead due to intense lock contention, which degrades the performance. Various batch-parallel BSTs have been developed. Our main baseline, PAM [65], uses weight-balanced trees. Later works, Aspen [27] and CPAM [26], extend PAM with enlarged tree nodes to improve I/O performance, yet preserve the binary layout, partly to support functional updates via path copying. Unlike these systems, we focus on in-place updates. Ultimately, their binary structure prevents them from achieving non-trivial I/O bounds. Several lock-free parallel 𝐵 + -trees exist. The PALM tree [61] performs batch updates in the Bulk Synchronous Parallel (BSP) model [34]. Like PaB-tree, it splits overflow nodes during insertion and reinserts underflow nodes. However, its BSP design targets communication cost and load balancing, exposing limited parallelism: work within each node is pinned to a single thread, so underflow reinsertion is sequential. It also provides no I/O optimization or theoretical guarantees. Akhremtsev et al. [4] present a parallel (𝑎, 𝑏)tree with provable work and span bounds for batch updates. However, their analysis assumes constant 𝑎 and 𝑏, and therefore also does not yield I/O bounds. Since their code is not publicly available, we could not include it in our evaluation.

0.1

0.1 1 4 16 32 64 112112h

0.1 1 4 16 32 64 112112h

1 4 16 32 64 112112h

Number of threads

Figure 9. Normalized parallel speedup of tree construction, batch insertion and batch deletion on different number of processors. Higher is better. The speedup is normalized to the running time on the PaB-tree on 1 thread respectively. The 109 entries, and batch updates apply a single batch of 107 entries. “112h” means using all 112 cores (224 hyper-threads).

controls the degree of randomness in the leaf entries, with 𝛼 = 0 corresponding to a fully sorted leaf and 𝛼 = 1 corresponding to a fully random leaf. Sorted leaves improve query performance at the cost of more expensive batch updates. Both batch insertion and deletion become faster if we tolerate more randomness in the leaf. Insertion is more sensitive to the ratio than deletion. This comes from the asymmetry between the two operations. With a larger randomness 𝛼, an insertion will likely just append new entries to an unsorted leaf, whereas a sorted leaf requires merging, resulting in a more significant difference between the two cases. On the other hand, a deletion has to filter the leaf in one pass regardless of whether it is sorted, so 𝛼 minimally affects its leaf-level cost. The remaining effect of 𝛼 on deletion comes from the reinsertions it triggers, which follow the insertion path. Since the reinserted subtrees are usually much smaller than the batch itself, 𝛼 affects the total deletion time much less than the insertion time. A Neighbor query needs to locate the start and end of the range in the leaf. A sorted leaf enables binary search, which is much faster than linear search in a random leaf. As a result, the query time increases as the randomness ratio grows. Overall, the randomness ratio 𝛼 = 0.5 provides a good balance between batch update and query performance.

10

Related Work

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Conference’17, July 2017, Washington, DC, USA

Concurrent Search Indexes. Concurrent B/B+ -trees, such as Mass-tree [50] and Bw-tree [72], are widely studied [8, 20, 22, 38, 47, 54, 56, 80] due to their prevalence in storage systems and databases. Concurrent data structures target a different setting of simultaneous point updates, and thus rarely deliver peak performance on batch-parallel workloads. However, applying updates individually makes single-update latency independent of batch size. On the other hand, parallel structures (including our PaB-tree) suit batch-based applications such as those in graph processing [27, 57, 75].

6

[8] Rudolf Bayer and Mario Schkolnick. 1977. Concurrency of operations on B-trees. Acta informatica 9, 1 (1977), 1–21. [9] Michael A Bender, Jeremy T Fineman, Seth Gilbert, and Bradley C Kuszmaul. 2005. Concurrent cache-oblivious B-trees. In Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures. 228–237. [10] Timo Bingmann. 2013. STX B+ Tree C++ Template Classes. https: //panthema.net/2007/stx-btree/. [11] Timo Bingmann. 2018. TLX: Collection of Sophisticated C++ Data Structures, Algorithms, and Miscellaneous Helpers. https://panthema. net/tlx. [12] Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib—A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 507–509. doi:10.1145/3350755. 3400254 [13] Guy E Blelloch and Magdalen Dobson. 2022. Parallel Nearest Neighbors in Low Dimensions with Batch Updates. In Algorithm Engineering and Experiments (ALENEX). SIAM, 195–208. doi:10.1137/1.9781611977042. 16 [14] Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). [15] Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal Parallel Algorithms in the Binary-Forking Model. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 89–102. doi:10.1145/3350755.3400227 [16] Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2010. Low depth cache-oblivious algorithms. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 189–199. doi:10. 1145/1810479.1810519 [17] Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan. 2016. Parallel Shortest Paths Using Radius Stepping. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 443–454. [18] Robert D. Blumofe and Charles E. Leiserson. 1998. Space-Efficient Scheduling of Multithreaded Computations. SIAM J. on Computing 27, 1 (1998), 202–229. doi:10.1137/s0097539793259471 [19] Anastasia Braginsky and Erez Petrank. 2012. A lock-free B+ tree. In Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures. 58–67. [20] Sang K. Cha, Sangyong Hwang, Kihong Kim, and Keunjoo Kwon. 2001. Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems. In Proc. 27th International Conference on Very Large Data Bases (VLDB). 181–190. [21] Youmin Chen, Youyou Lu, Kedong Fang, Qing Wang, and Jiwu Shu. 2020. uTree: a persistent B+-tree with low tail latency. Proceedings of the VLDB Endowment 13, 12 (2020), 2634–2648. [22] Jiwon Choe, Andrew Crotty, Tali Moreshet, Maurice Herlihy, and R Iris Bahar. 2022. Hybrids: Cache-conscious concurrent data structures for near-memory processing architectures. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. 321–332. [23] Douglas Comer. 1979. Ubiquitous B-tree. ACM computing surveys (CSUR) 11, 2 (1979), 121–137. [24] Mayank Daga and Mark Nutter. 2012. Exploiting coarse-grained parallelism in B+ tree searches on an APU. In 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 240– 247. [25] Narsingh Deo, Amit Jain, and Muralidhar Medidi. 1994. Parallel construction of (a, b)-trees. J. Parallel and Distrib. Comput. 23, 3 (1994), 442–448. [26] Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun. 2022. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections. In ACM Conference on Programming Language Design and Implementation (PLDI). [27] Laxman Dhulipala, Guy E Blelloch, and Julian Shun. 2019. Low-

Conclusion

We introduce PaB-tree, the first batch-parallel 𝐵 + -tree to pair provable guarantees on work, span, and cache complexity with state-of-the-art practical performance. Its design rests on a single invariant—a repair never touches a sibling and is always pushed to the parent—one that reduces every overflow and underflow to one uniform, Promotebased mechanism. This simplicity is what makes PaB-tree scale: repairs stay on the ancestor path, so the divide-andconquer structure exposes ample parallelism with little coordination overhead. As a result, across synthetic, key–value, and temporal-graph workloads, PaB-tree achieves the fastest batch updates among the baselines while remaining competitive on queries. Natural next steps include extending it to the external- and persistent-memory settings and interleaving concurrent point queries with batched updates.

7

Acknowledgments

This work is supported by NSF grants IIS-2227669, TI-2346223, NSF CAREER Awards CCF-2238358, CCF-2339310, and OAC2543534, and the Google Research Scholar Program.

References [1] Umut A Acar, Daniel Anderson, Guy E Blelloch, and Laxman Dhulipala. 2019. Parallel batch-dynamic graph connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures. 381–392. [2] M AdelsonVelskii and Evgenii Mikhailovich Landis. 1963. An algorithm for the organization of information. Technical Report. DTIC Document. [3] Alok Aggarwal and Jeffrey S. Vitter. 1988. The input/output complexity of sorting and related problems. Commun. ACM 31, 9 (1988), 1116–1127. doi:10.1145/48529.48535 [4] Yaroslav Akhremtsev and Peter Sanders. 2016. Fast Parallel Operations on Search Trees. In IEEE International Conference on High Performance Computing (HiPC). [5] Daniel Anderson, Guy E. Blelloch, and Kanat Tangwongsan. 2020. Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). [6] Nimar S Arora, Robert D Blumofe, and C Greg Plaxton. 2001. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems (TOCS) 34, 2 (2001), 115–144. doi:10.1007/s00224-0010004-z [7] Rudolf Bayer and Edward McCreight. 1970. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control. 107– 141. 11

Conference’17, July 2017, Washington, DC, USA

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu [47] Philip L Lehman and S Bing Yao. 1981. Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems (TODS) 6, 4 (1981), 650–670. [48] Wei Quan Lim. 2019. Optimal multithreaded batch-parallel 2-3 trees. arXiv preprint arXiv:1905.05254 (2019). [49] Yibo Liu, Bing Wu, Shiyi Song, Xueliang Wei, Huan Cheng, Heng Zhou, Wei Tong, and Dan Feng. 2026. pTree: Building Efficient B+Tree on Non-Volatile Memory With Processing-in-Memory. IEEE Trans. Comput. (2026). [50] Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012. Cache craftiness for fast multicore key-value storage. In Proceedings of the 7th ACM european conference on Computer Systems. 183–196. [51] Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu. 2026. Implementation for PaB-tree. https://github.com/ucrparlay/pab-tree. [52] Ziyang Men, Bo Huang, Yan Gu, and Yihan Sun. 2026. Parallel Dynamic Spatial Indexes. In Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 150–163. doi:10.1145/3774934.3786412 [53] Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun. 2025. Parallel kd-tree with Batch Updates. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–26. doi:10.1145/3709712 [54] Jacob Nelson-Slivon, Ahmed Hassan, and Roberto Palmieri. 2022. Bundling linked data structures for linearizable range queries. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 368–384. [55] Jürg Nievergelt and Edward M Reingold. 1973. Binary search trees of bounded balance. SIAM J. on Computing 2, 1 (1973), 33–43. [56] Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, and Wolfgang Lehner. 2016. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In Proceedings of the 2016 International Conference on Management of Data. 371–386. [57] Prashant Pandey, Brian Wheatman, Helen Xu, and Aydin Buluc. 2021. Terrace: A hierarchical graph container for skewed dynamic graphs. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 1372–1385. [58] Heejin Park, Kunsoo Park, and Yookun Cho. 2004. Deleting keys of B-trees in parallel. J. Parallel and Distrib. Comput. 64, 9 (2004), 1041–1050. [59] Wolfgang J. Paul, Uzi Vishkin, and Hubert Wagener. 1983. Parallel Dictionaries in 2-3 Trees. In Intl. Colloq. on Automata, Languages and Programming (ICALP). 597–609. [60] Hongchan Roh, Sungho Kim, Daewook Lee, and Sanghyun Park. 2014. AS B-tree: A Study of an Efficient B+-tree for SSDs. J. Inf. Sci. Eng. 30, 1 (2014), 85–106. [61] Jason Sewall, Jatin Chhugani, Changkyu Kim, Nadathur Satish, and Pradeep Dubey. 2011. PALM: Parallel architecture-friendly latch-free modifications to B+ trees on many-core processors. Proceedings of the VLDB Endowment 4, 11 (2011), 795–806. [62] Julian Shun and Guy E Blelloch. 2014. Phase-concurrent hash tables for determinism. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 96–107. [63] Venkathachary Srinivasan and Michael J Carey. 1991. Performance of B-tree concurrency control algorithms. In Proceedings of the 1991 ACM SIGMOD international conference on Management of data. 416–425. [64] Yihan Sun, Guy E Blelloch, Wan Shen Lim, and Andrew Pavlo. 2019. On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes. Proceedings of the VLDB Endowment (PVLDB) 13, 2 (2019), 211–225. [65] Yihan Sun, Daniel Ferizovic, and Guy E Blelloch. 2018. PAM: Parallel Augmented Maps. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [66] The Rust Project Developers. 2024. std::collections::BTreeMap — The Rust Standard Library. https://doc.rust-lang.org/std/collections/ btree_map/struct.BTreeMap.html.

latency graph streaming using compressed purely-functional trees. In ACM Conference on Programming Language Design and Implementation (PLDI). 918–934. [28] Xiangyun Ding, Yan Gu, and Yihan Sun. 2024. Parallel and (Nearly) Work-Efficient Dynamic Programming. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures. 219–232. doi:10.1145/3626183.3659958 [29] Xiaojun Dong, Yan Gu, Yihan Sun, and Yunming Zhang. 2021. Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 184–197. [30] Mingzhe Du and Michael L Scott. 2025. Buffered persistence in b+ trees. In Proceedings of the 3rd Highlights of Parallel Computing Workshop. 34–36. [31] Jeremy T. Fineman. 2018. Nearly Work-Efficient Parallel Algorithm for Digraph Reachability. In ACM Symposium on Theory of Computing (STOC). 457–470. [32] Leonor Frias and Johannes Singler. 2007. Parallelization of bulk operations for STL dictionaries. In European Conference on Parallel Processing. Springer, 49–58. [33] Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. 1999. Cache-Oblivious Algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS). 285–297. doi:10.1109/sffcs. 1999.814600 [34] Alexandros V Gerbessiotis and Leslie G Valiant. 1994. Direct bulksynchronous parallel algorithms. Journal of parallel and distributed computing 22, 2 (1994), 251–267. [35] Michael T Goodrich, Yan Gu, Ryuto Kitagawa, and Yihan Sun. 2025. Parallel Joinable B-Trees in the Fork-Join I/O Model. (2025). [36] Google. 2018. Abseil C++ Common Libraries: Btree Containers. https://github.com/abseil/abseil-cpp. absl::btree_map, absl::btree_set, absl::btree_multimap, absl::btree_multiset. Design rationale: https://abseil.io/about/ design/btree. Accessed 2026-08-02. [37] Google. 2024. btree: An Ordered, In-Memory B-Tree for Go. https: //github.com/google/btree. [38] Goetz Graefe. 2010. A survey of B-tree locking techniques. ACM Transactions on Database Systems (TODS) 35, 3 (2010), 1–26. [39] Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan. 2023. Parallel Longest Increasing Subsequence and van Emde Boas Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). [40] Yan Gu, Zachary Napier, and Yihan Sun. 2022. Analysis of WorkStealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46–60. doi:10.1137/1.9781611977059.4 [41] Leo J Guibas and Robert Sedgewick. 1978. A Dichromatic Framework for Balanced Trees. (1978). [42] Mordechai Haklay and Patrick Weber. 2008. Openstreetmap: Usergenerated street maps. IEEE Pervasive computing 7, 4 (2008), 12–18. [43] Lisa Higham and Eric Schenk. 1994. Maintaining B-trees on an EREW PRAM. Journal of parallel and distributed computing 22, 2 (1994), 329–335. [44] Hongbo Kang, Phillip B Gibbons, Guy E Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey. 2021. The Processing-in-Memory Model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 295–306. [45] Hongbo Kang, Phillip B Gibbons, Guy E Blelloch, Laxman Dhulipala, Yan Gu, and Charles McGuffey. 2023. A Skew-Resistant Trie for Processing-in-Memory. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). [46] Hongbo Kang, Yiwei Zhao, Guy Blelloch, Laxman Dhulipala, Yan Gu, Charles McGuffey, and Phillip Gibbons. 2023. PIM-tree: A Skewresistant Index for Processing-in-Memory. In Proceedings of the VLDB Endowment (PVLDB). 12

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Conference’17, July 2017, Washington, DC, USA

[67] Ruiqin Tian, Junqiao Qiu, Zhijia Zhao, Xu Liu, and Bin Ren. 2019. Transforming query sequences for high-throughput b+ tree processing on many-core processors. In 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). IEEE, 96–108. [68] Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. 2019. Batchparallel euler tour trees. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 92– 106. [69] Letong Wang, Xiangyun Ding, Yan Gu, and Yihan Sun. 2023. Fast and Space-Efficient Parallel Algorithms for Influence Maximization. Proceedings of the VLDB Endowment (PVLDB) 17, 3 (2023), 400–413. [70] Yiqiu Wang, Yan Gu, and Julian Shun. 2020. Theoretically-Efficient and Practical Parallel DBSCAN. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2555–2571. [71] Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2022. ParGeo: a library for parallel computational geometry. In European Symposium on Algorithms (ESA). [72] Ziqi Wang, Andrew Pavlo, Hyeontaek Lim, Viktor Leis, Huanchen Zhang, Michael Kaminsky, and David G Andersen. 2018. Building a bw-tree takes more than just buzz words. In Proceedings of the 2018 International Conference on Management of Data. 473–488. [73] Brian Wheatman, Randal Burns, Aydın Buluç, and Helen Xu. 2023. Optimizing Search Layouts in Packed Memory Arrays. In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, 148–161. [74] Brian Wheatman, Randal Burns, and Helen Xu. 2024. Batch-Parallel Compressed Sparse Row: A Locality-Optimized Dynamic-Graph Representation. In 2024 IEEE High Performance extreme Computing Conference (HPEC). IEEE. [75] Brian Wheatman, Xiaojun Dong, Zheqi Shen, Laxman Dhulipala, Jakub Łącki, Prashant Pandey, and Helen Xu. 2024. BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers. In Proceedings of the VLDB Endowment (PVLDB). [76] Brian Wheatman, Quinten De Man, Xiangyun Ding, Zhongqi Wang, Randal Burns, Laxman Dhulipala, Xiaojun Dong, Yan Gu, Yihan Sun, and Letong Wang. 2026. Use Your Time(stamp) Wisely: The GraphTide Real-World Dynamic Graph Datasets. (2026). Manuscript under review. [77] Brian Wheatman and Helen Xu. 2018. Packed compressed sparse

row: A dynamic graph representation. In 2018 IEEE High Performance extreme Computing Conference (HPEC). IEEE. [78] Brian Wheatman and Helen Xu. 2021. A parallel packed memory array to store dynamic graphs. In Algorithm Engineering and Experiments (ALENEX). SIAM, 31–45. [79] Brian Wheatman and Helen Xu. 2021. A parallel packed memory array to store dynamic graphs. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 31–45. [80] Evan Wrench, Ajay Singh, Younghun Roh, Panagiota Fatourou, Siddhartha Jayanti, Eric Ruppert, and Yuanhao Wei. 2026. Concurrent Balanced Augmented Trees. In Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 136–149. [81] Helen Xu, Amanda Li, Brian Wheatman, Manoj Marneni, and Prashant Pandey. 2023. BP-Tree: Overcoming the point-range operation tradeoff for in-memory B-trees. Proceedings of the VLDB Endowment 16, 11 (2023), 2976–2989. [82] Zhaofeng Yan, Yuzhe Lin, Lu Peng, and Weihua Zhang. 2019. Harmonia: a high throughput B+ tree for GPUs. In Proceedings of the 24th symposium on principles and practice of parallel programming. 133–144. [83] Weihua Zhang, Chuanlei Zhao, Lu Peng, Yuzhe Lin, Fengzhe Zhang, and Jinhu Jiang. 2022. High performance GPU concurrent B+ tree. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 443–444. [84] Yiwei Zhao, Hongbo Kang, Yan Gu, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons. 2025. Optimal Batch-Dynamic kd-trees for Processing-in-Memory with Applications. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures (Portland, OR, USA) (SPAA ’25). Association for Computing Machinery, New York, NY, USA, 350–366. doi:10.1145/3694906.3743318 [85] Yiwei Zhao, Hongbo Kang, Ziyang Men, Yan Gu, Guy E. Blelloch, Laxman Dhulipala, Charles McGuffey, and Phillip B. Gibbons. 2026. PIM-zd-tree: A Fast Space-Partitioning Index Leveraging ProcessingIn-Memory. In Proceedings of the 31st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Sydney, Australia) (PPoPP ’26). Association for Computing Machinery, New York, NY, USA. doi:10.1145/3774934.3786411

13

Time in seconds (log-scale)

Conference’17, July 2017, Washington, DC, USA

PaB-tree PAM CPAM (a) Batch Insert, Uniform

PMA

102

102

100

100

10-2

10-2 10-1

100

101

102

10-1

103

(c) Batch Delete, Uniform

100

100

10-2

10-2 101

102

Bw-tree

routing the entries to their leaves accounts for most of the cost; and for large batches, handling invalid subtrees poses less overhead than it does in the incremental setting, where the updates trigger invalid subtrees far more often. Overall, PaB-tree is the fastest or among the fastest under both distributions. On small batches, CPAM and PAM are slightly slower than PaB-tree because of their larger tree height. The gap narrows as the batch size grows, since applying the batch invalidates larger subtrees, where both PAM and CPAM can utilize tree rotations to fix them easily, while PaB-tree must reinsert every entry in the invalid subtree. The insertion curve of PMA shows several spikes, most likely because the entries exceed the capacity of the underlying array and force PMA to reallocate the memory and copy every entry. For batch deletion, PMA performs similarly to the others, since a freshly constructed tree leaves every leaf block nearly full and a single batch rarely removes enough entries to trigger an underflow.

100

101

102

103

(d) Batch Delete, Adversarial 102

100

Mass-tree

(b) Batch Insert, Adversarial

102

10-1

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

10-1

103

100

101

102

103

Batch size ( × 1M)

Figure 10. Running time (in seconds) of single batch update on synthetic datasets. Lower is better. The tree contains 109 entries, and the batch size ranges from 105 to 109 . The batch insertion is to insert another batch from same distribution, and the batch deletion is to delete a batch of entries from the tree. Plots are in log-log scale. Uni. (Ours)

Skewed (Ours)

Uni. (CPAM)

Time (sec.)

(a) Build

0.09

1.0

0.06

0.5

0.03

0.0

2

4

8 16 32 64 128 256 5121024

Time (sec.)

(c) Incre. Batch Insert (1%) 6 4 2 0

Skewed (CPAM)

(b) Find Query

0.12

1.5

B

2

4

8 16 32 64 128 256 512 1024

0.00 12.5 10.0 7.5 5.0 2.5 0.0

2

4

8 16 32 64 128 256 5121024

(d) Incre. Batch Delete (1%)

2

4

8 16 32 64 128 256 5121024

Block size

Figure 11. Running time (in seconds) of tree construction, incremental batch updates and Find queries w.r.t different block sizes in PaB-tree on synthetic datasets. Lower is better. The time for CPAM on the same datasets is marked in lines. We measure both the Uni and Skew distribution.

A

Evaluation of the Block Size

We compare the performance of PaB-tree under different block sizes on synthetic datasets. The block size offers a tradeoff between tree height and the cost of searching within leaves. A smaller block size yields a taller tree, which incurs additional rounds of partitioning during construction and batch updates, but it reduces the search cost within each leaf and thereby accelerates queries, and vice versa. We measure the performance of PaB-tree on tree construction, incremental batch updates, and membership queries for block sizes 𝐵 ranging from 2 to 1024. We evaluate both the Uni and Skew distributions, compare against CPAM with a block size of 64, and summarize the results in Fig. 11. For tree construction, the time decreases as the block size grows and stabilizes beyond 𝐵 = 64, which is about 1.31× faster than with 𝐵 = 2 and 1.39× faster than the CPAM. For membership queries, a smaller block size produces a taller tree and thus more pointer chasing, increasing query latency; a larger block size, in turn, demands more work to search within each leaf, also raising query time and causing PaB-tree to fall behind CPAM once 𝐵 ≥ 512. For batch insertion, the running time rebounds under both distributions as the block grows. The reason is twofold: a small block raises the tree height and therefore the number of rounds needed to reach the leaves, while a large block demands more work to restore the order of the entries within each leaf. However, the PaB-tree is still faster than the CPAM due to a better cache access pattern for large block sizes. Similar rebounds are observed for batch deletion as well. However, for batch deletion, the cost of reinsertion dominates the overall cost, especially for the Skew distribution. A larger block size can absorb more entries during deletion, while it also leads to more entries being involved if a reinsertion is triggered, which makes it much slower than the CPAM for

Single Batch Updates Evaluation

We measure the time for PaB-tree and the baselines to apply a single batch of insertions or deletions on the Uni and Adv datasets. All baselines behave on Skew much as they do on Uni, so we omit it. We construct a tree with 109 entries, apply one batch to it, and report the running time. The batch size ranges from 105 to 109 ; we exclude smaller batches because their low computation cost diminishes the practical benefits of parallelism. We summarize the results in Fig. 10. In the incremental setting of Sec. 4.1, the running time is dominated by handling invalid subtrees, while a single batch update behaves more like the static case: for small batches, 14

PaB-tree: Parallel 𝐵 + -tree with Batch Updates

Conference’17, July 2017, Washington, DC, USA

Bench.

Trees

Build (1B) Inst CRs CMs

Incre. Batch Insert (10M) CC Inst CRs CMs

Incre. Batch Delete (10M) CC Inst CRs CMs

Uni

PaB-tree 689102 427666 2757 1896 PAM 1309474 641143 3676 2450 CPAM 1141550 460966 2913 2172 PMA 1659997 782120 3931 3137

2606644 1916753 7499 6732 5010064 1769777 14481 13654 3970271 2557469 14894 13246 8056747 4005441 19041 16428

2527648 1131125 9065 8541 41462 12126 7713895 1682153 28172 26765 54587 9944 3833292 2306154 13942 12550 51803 12059 5071312 2026665 14687 13641 22512 12389

229 257 322 162

135 154 200 63

Skew

PaB-tree 723544 434176 2759 1884 1898140 1342657 5414 4731 PAM 1145419 638249 3645 2366 3692366 1497891 10573 9827 CPAM 918078 459656 2854 2123 2847642 1817654 9932 8844 PMA 1623022 810203 3888 3122 12012571 5086143 28184 24814

2962518 1425902 8599 7727 33791 11387 5449122 1475377 19262 18105 45955 10145 2379974 1453233 8032 7177 41816 13034 6178408 2680818 15210 13757 21433 13849

196 219 269 134

106 118 149 50

Adv

PaB-tree 755753 427042 2700 1847 1492662 1028816 2869 2303 1501640 880613 2992 2297 24772 11319 118 PAM 1069354 638485 3599 2340 1836388 944630 5682 4908 1684620 920743 4583 3908 31828 10358 128 CPAM 932701 470555 2852 2105 1486898 919756 4024 3407 769352 451312 1668 1270 30904 13207 163 PMA 1757184 767818 3711 3094 18835645 7638258 43640 39373 10353164 4490375 22971 20477 16384 12977 86

71 76 101 34

CC

CC

Find (10M) Inst CRs CMs

Table 1. Hardware profiling of the baselines. We report the number of CPU cycles (CC), instructions (Inst), cache references (CRs) and cache misses (CMs). The detailed setting is shown in Sec. 4.1. The Find query contains 10M queries on a tree with 1B entries. All units are in millions. The best result in each column is underlined. Update in Batch

Update in Single Entry

Time (sec.)

(a) Insert 10

2

10

2

10

0

10

0

10

-2

10

-2

10

-4

10

-4

10

-6

10

-6

10

0

10

2

10

4

count of all indexes in all three distributions, but its large tree height requires fetching more cache lines and leaves it slower. For batch deletion, CPAM is faster than PaB-tree on Skew and Adv, by up to 1.95×. On Skew, PaB-tree still executes the fewest instructions, and the gap comes entirely from I/O, whereas on Adv, CPAM wins on both counters, since its join-based algorithm can easily split out the single tree that is triggered by applying a batch of consecutive keys, while PaB-tree must reinsert every underflow subtree. Once this shortcut disappears under Uni, PaB-tree leads on all four counters again. For Find queries, the PMA incurs about 2.1× fewer cache misses than the PaB-tree on every distribution. This gain is confined to queries on different distributions. Rebuilding overflowed blocks during incremental insertion costs PMA up to 12.6× the cycles of PaB-tree, with the gap widening as the keys in a batch become more local, as in the Adv distribution, which makes PMA the slowest index for updates. Overall, the hardware profiling confirms the importance of cache efficiency in achieving high-performance parallel 𝐵 + -trees, which is the main reason that PaB-tree outperforms the baselines in most of the experiments.

(b) Delete

10

6

10

8

10

0

10

2

10

4

10

6

10

8

Batch size

Figure 12. Running time (in seconds) of batch updates vs. sequential point updates. Lower is better. We measure the time to apply insertion or deletion batches of different sizes to a tree of 109 entries. Entries in both the tree and the batches are uniformly distributed. Because of the inherent overhead of batching and parallelism, batch updates may be slower than point updates on small batches. However, at a batch size of about 100, the benefits of batching and parallelism start to outweigh this overhead. Accordingly, PaB-tree can fall back to sequential point updates for batches below this size.

𝐵 > 64. Overall, 𝐵 = 64 balances update and query performance best, so we adopt it as the default block size in all other experiments.

D C

Hardware Profiling Details

Handling of Small Batches

As shown in Alg. 3, batch deletion repairs node underflows by setting aside dropped subtrees and reinserting them level by level. For very small deletion batches, the reinsertion overhead may dominate the total cost. Although Fig. 5 shows that reinsertions occur infrequently in practice, we discuss how to handle small batches here for completeness. More generally, small batches may diminish the benefits of batch-parallel updates because each thread receives too little work. Existing work on parallel data structures such as CPAM has shown that below a certain batch size, applying a batch as a sequence of point updates is faster. In any case, the cost of such small batches is low. We test PaB-tree with

Table 1 reports the raw counters behind Fig. 7 and extends the profiling from the Skew distribution to all three synthetic distributions. For tree construction, PaB-tree attains both the lowest instruction count and the fewest cache misses under every distribution, and the two counters barely change across different distributions, because the construction process is purely comparison-based and thus resistant to different distributions. On incremental batch insertion under Uni, PAM executes 8% fewer instructions than PaB-tree, yet incurs 2.03× the cache misses, which in turn makes it 1.92× slower. Find repeats the pattern: PAM has the lowest instruction 15

Conference’17, July 2017, Washington, DC, USA

Ziyang Men, Yan Gu, Yihan Sun, and Helen Xu

very small batches on a tree of 109 entries under the Uni distribution and show the results in Fig. 12. Batch updates start to outperform point updates at a batch size of about 100,

where a batch takes less than 1 millisecond. Below this cutoff, PaB-tree can simply fall back to sequential point updates, which are even faster.

16

Related documents

• Ultra Efficient Acceleration for De Novo Genome Assembly via Near-Memory Computing#1328507
• Shore-MT: A Scalable Storage Manager for the Multicore Era#415047
• An Empirical Analysis of the B-Tree Navigator Algorithm: Solving the Subset Sum Problem in Polynomial-Average Time#28917
• An Empirical Analysis of the B-Tree Navigator Algorithm: Solving the Subset Sum Problem in Polynomial-Average Time#28916
• IDS-DEEP2: Strategies for selecting the best IDS for Drones with heterogeneous or homogeneous EmbEdded parallel platforms#1251493