Buffered Partially-Persistent External-Memory Search Trees

For problems on massive amounts of data that do not fit in internal memory, the standard model of computation is the I/O-model by Aggarwal and Vitter [1]. In this model, all computation occurs in an internal memory of size $M$, while an infinite external memory is used for storage. Data is transferred between internal and external memory in blocks of $B$ consecutive elements, with each transfer counting as an I/O. The I/O complexity of an algorithm is defined as the total number of I/Os it performs, and the space usage is the maximum number of external-memory blocks used at any given time. The only operation we allow on stored keys are comparisons and we follow the standard assumption that the parameters $B\ge 2$ and $M\ge 2B$. Aggarwal and Vitter proved that the optimal bound for sorting in external memory is $\mathrm{𝑠𝑜𝑟𝑡}\left(N\right)=\mathrm{\Theta }\left(\frac{N}{B}{\log }_{M/B}\frac{N}{B}\right)$ I/Os [1]. An algorithm is called cache oblivious if it is designed without explicit knowledge of $B$ and $M$ but is still analyzed in the I/O model for arbitrary values of these parameters, assuming an optimal offline cache replacement strategy [22]. Some authors make stronger assumptions on the size of the internal memory, such as the tall-cache assumption $M\ge B^{1+\delta }$, for some constant $\delta >0$. For cache-oblivious algorithms, a tall-cache assumption is necessary to achieve optimal comparison-based external-memory sorting [11].

Considering the I/O-behavior of algorithms can be crucial in practice, as demonstrated by Streaming B-trees [8], the generation of massive graphs for the LFR benchmark [24, 27, 28], and the FlashAttention algorithm used in Transformer models [15].

A partially-persistent search tree stores an ordered set of keys supporting the interface below (in our examples we use integers, but our data structure works for any totally ordered set). Each version is identified by a unique integer version identifier $v$, with zero being the initial version and the current version denoted by $v_c$. Further, we let ${𝒮}_v$ denote the set of keys contained in version $v$, and $N_v$ the size of ${𝒮}_v$. Initially $v_c=0$ and ${𝒮}_{v_c}=\mathrm{\varnothing }$. Updates (insertions and deletions) can only be performed on the current set ${𝒮}_{v_c}$, and any update advances the current version identifier, i.e., each version of the set ${𝒮}_v$ only differs from the previous version ${𝒮}_{v-1}$ by at most a single key. Queries can be performed on any version.

• $\mathrm{■}$

  $\text{Insert}(x)$ Creates ${𝒮}_{v_c+1}={𝒮}_{v_c}\cup \{x\}$, increments $v_c$, and returns $v_c$.

• $\mathrm{■}$

  $\text{Delete}(x)$ Creates ${𝒮}_{v_c+1}={𝒮}_{v_c}\setminus \{x\}$, increments $v_c$, and returns $v_c$.

• $\mathrm{■}$

  $\text{Range}(v,x,y)$ Reports all keys in ${𝒮}_v\cap [x,y]$ in increasing order.

• $\mathrm{■}$

  $\text{Search}(v,x)$ Returns the successor of $x$ in ${𝒮}_v$, i.e., $\min \{y\in {𝒮}_v|x\le y\}$.

In internal memory, the fat node and node copying techniques can make any ephemeral linked data structure partially-persistent with constant overhead in both time and space, if the in-degree of each node in the ephemeral structure is constant [20]. Becker, Gschwind, Ohler, Seeger, and Widmayer [6] and Varman and Verma [32] adapted these techniques to B-trees in external-memory. An elegant application of partial persistence appears in the design of linear space planar point location data structures [31]. In this setting, the underlying set consists of segments which are partially ordered (only a pair of segments intersected by a vertical line can be compared). To adapt this approach to the external-memory setting, Arge, Danner, and Teh strengthened the partially-persistent B-tree to require only a total order on keys alive at any given version, leading to a static external-memory point-location structure [3].

A different approach to persistence is to interpret it geometrically, see Figure 1(left), modeling it as a data structure problem on a dynamic set of vertical segments. Kolovson and Stonebraker explored this perspective [26], though their reliance on R-trees led to poor performance guarantees [23]. More recently, Brodal, Rysgaard, and Svenning [12] leveraged this geometric approach to develop fully persistent B-trees, which allow both queries and modifications to all past versions in $𝒪\left({\log }_B{N}_v\right)$ I/Os. In a fully persistent data structure, updating a version corresponds to cloning it and then applying the modification to the newly cloned version, ensuring that existing versions remain unaffected. Such behavior contrasts with retroactive data structures [17], where updates recursively propagate to cloned versions.

Concurrently with the work on persistent data structures in external-memory, there were significant improvements to external-memory data structures by leveraging buffering techniques to always process multiple updates and/or queries together. These include the Buffer Tree by Arge [2] which can form the basis for external-memory sorting, priority queues and batched dynamic algorithms [21] in amortized $𝒪\left(\frac{1}{B}{\log }_{M/B}\frac{N}{B}\right)$ I/Os per operation. For a batched operation the answer might not be immediately returned, which is often sufficient, e.g., in many geometric plane-sweep algorithms where only the end result matters. For standard (non-batched) data structures, a line of work has investigated the update-query trade-off, beginning with the Buffered Repository Tree [14] performing updates in amortized $𝒪\left(\frac{1}{B}{\log }_{B}N\right)$ I/Os and queries in $𝒪\left({\log }_{2}N\right)$ I/Os. This was later generalized by the $B^{\epsilon }$-tree [10] which corresponds to the Buffered Repository Tree for $\epsilon \approx 0$ and to the standard B-tree for $\epsilon \approx 1$. The amortized performance of the $B^{\epsilon }$-tree was improved to high-probability [7] and worst-case [16] I/O bounds using stronger assumptions on the size of $B$ and $M$ (see Table 1).

Combining the two lines of research on persistence and buffered data structures has remained an open challenge for the past 20 years, likely due to their seemingly conflicting principles. Persistence requires maintaining access to past versions without affecting their structure, while buffers essentially hold updates to past versions before applying them. Our work demonstrates that these two ideas can be effectively unified by developing partially-persistent external-memory search trees that achieve bounds matching those of ephemeral $B^{\epsilon }$-trees. In Section 2 we prove the following theorem.

Our construction is essentially a $B^{\epsilon }$-tree with buffers of $𝒪\left(B\right)$ delayed updates at each internal node, leaves storing $\mathrm{\Theta }\left(\frac{1}{\epsilon }B{\log }_B{N}_v\right)$ updates, and where partially persistence is obtained using path copying of nodes, where an internal node is only copied when its buffer is empty.

The query Search can trivially also answer a member query “$x\in {𝒮}_v$?” by checking if $\text{Search}(v,x)$ returns $x$. Our data structure also supports predecessor queries along with successor queries, as well as strict predecessor and successor queries, i.e., the returned key should be strictly smaller or larger than the query key $x$. The structure can also handle the case when ${𝒮}_0\ne \mathrm{\varnothing }$, where the initial structure can be constructed using $𝒪\left(1+|{𝒮}_0|/B\right)$ I/Os (essentially this is Section 2.6, where a structure is constructed for a given sorted set of keys). Our data structure is stated as maintaining a set of keys, but it can easily be extended to support dictionaries storing key-value pairs (each vertical segment in Figure 1 now stores a key-value pair, where the first axis is the key. Changing the value for key $x$ at version $v$ starts a new vertical segment at $(x,v)$ with the new value).

In Section 3 we describe how to convert the amortized I/O bounds of Theorem 1 to worst-case bounds under the assumption that $M=\mathrm{\Omega }\left(B^{1-\epsilon }{\log }_2({\max }_v{N}_v)\right)$ (Theorem 2), a weaker or equal assumption on the memory size than used in [7] and [16] for high-probability and worst-case bounds for $B^{\epsilon }$-trees, respectively. Under the weakest assumption that $M\ge 2B$, we achieve the worst-case bounds in Theorem 3 with an additional term of at most $𝒪\left(\mathrm{𝑠𝑜𝑟𝑡}\left(B^{1-\epsilon }{\log }_2{N}_v\right)\right)$ I/Os, where $B^{1-\epsilon }{\log }_2{N}_v$ is an upper bound on the number of buffered updates on a root-to-leaf path in our buffered $B^{\epsilon }$-tree that should be flushed to a leaf. For updates, where the I/O bound can be $o(1)$, we assume that the I/Os are performed evenly spread out among the updates.

Note that, for example, when $N_v=2^{𝒪\left(B^{\epsilon }\right)}$ then $B^{1-\epsilon }{\log }_2{N}_v=𝒪\left(B\right)$ and $\gamma =𝒪\left(1\right)$ and the I/O bounds of Theorem 3 match those of Theorem 2, with only the assumption $M\ge 2B$. This observation can be further strengthened, as when $\gamma =𝒪\left(\frac{1}{\epsilon }{\log }_B{N}_v\right)$ the I/O bounds match similarly, which holds when $N_v=2^{B^{\epsilon }{\left(\frac{M}{B}\right)}^{𝒪\left(\frac{B^{\epsilon }}{\epsilon {\log }_{2}B}\right)}}$.

The problem has a natural geometric interpretation in a two-dimensional space, with the first dimension representing the keys and the second dimension representing the versions, see Figure 1(left). On this two-dimensional plane, a key $x$ existing in a half-open interval of versions $[v,w[$, is represented by the vertical line segment $\{x\}\times [v,w[$, i.e., $x$ is inserted in version $v$ and deleted in version $w$. If $x\in {𝒮}_{v_c}$, then $w=+\mathrm{\infty }$ ($x$ has not been deleted yet).

We consider the sequence of versions partitioned into intervals $[v_0,v_1[,\mathrm{\dots },[v_{k-1},v_k[,[v_k,\mathrm{\infty }[$, for some versions . In Section 2.6 we show how to maintain the version intervals. We let $\overline{v}=v_k$ and $\overline{N}=|{𝒮}_{\overline{v}}|$. In the following, we consider the interval $[\overline{v},\mathrm{\infty }[$, which contains the current version $v_c$ of the set. We allow up to $\alpha \cdot \overline{N}$ partially-persistent updates during this interval of versions for a constant , i.e., all versions $v$, $\overline{v}\le v\le v_c$, satisfy $(1-\alpha )\cdot \overline{N}\le |{𝒮}_v|\le (1+\alpha )\cdot \overline{N}$.

Our data structure is built around four parameters:

The basic idea is to have a $B^{\epsilon }$-tree $T$ of degree at most $2\mathrm{\Delta }-1$ (and degree at least $\mathrm{\Delta }$, if only insertions can be performed, and degree at least 1 if deletions are allowed), where leaves (open rectangles) store between $4R$ and $10R$ updates (see Section 2.4) and all leaves are at the same level of $T$. In Section 2.5 we prove that $H$ is an upper bound on the height of $T$ (number of nodes on a root-to-leaf path, excluding the leaves). Each internal node of $T$ will have a buffer of at most $2\mathrm{\Delta }F=\mathrm{\Theta }\left(B\right)$ updates yet to be applied to the leaves of the subtree rooted at the node. Note that $R$ is an upper bound on the total number of buffered updates along a root-to-leaf path in $T$. The essential property of the parameters is that $R/B=\mathrm{\Theta }\left(H\right)=\mathrm{\Theta }\left(\frac{1}{\epsilon }{\log }_B\overline{N}\right)$.

The geometric plane defined in Section 2.1 is partitioned into a set of axis aligned rectangles $[x,y[\times [v,w[$, such that the number of updates in each rectangle is $\mathrm{\Theta }\left(R\right)$. For each rectangle we store a list of the updates in the rectangle in lexicographical order by first the key and secondly the version of that update. Note that equal keys are group consecutively in the list. To allow efficiently locating a rectangle for a given version and key, we store a list indexed by version identifier, where we for each version $v$ store a pointer to the root of a B-tree $P_v$ over the rectangles left-to-right containing ${𝒮}_v$ (see Section 2.4). The tree $P_v$ has degree $\mathrm{\Theta }\left(B\right)$ and does not store buffered updates. Further, we require that each rectangle contains $\mathrm{\Omega }\left(R\right)$ keys which are present in all versions the rectangle spans. We denote such a key as spanning. If $\overline{N}=𝒪\left(R\right)$, all updates are stored in a single list.

New updates are buffered, to achieve I/O efficient update bounds. The topmost rectangles, which cover the current version $v_c$, are all open, with all other rectangles being closed. Crucially, new updates are always performed in the current version. We maintain the invariant that for a buffered update, i.e., an update not having been flushed to the corresponding rectangle yet, the rectangle must be open.

For the open rectangles, we store a $B^{\epsilon }$-tree $T$, such that recent updates to the open rectangles are buffered. We let the maximum degree of an internal node in $T$ be $2\mathrm{\Delta }-1$. Each internal node of $T$ contains a buffer of up to $2\mathrm{\Delta }F$ updates, sorted lexicographically by key and version. Additionally, each update stores if the update is an insertion or deletion. Consider a full buffer, i.e., it contains at least $2\mathrm{\Delta }F$ updates, where each update should be flushed to one of the at most $2\mathrm{\Delta }-1$ children. Then, there must exist a subset of least $F$ updates that should be flushed to the same child.

The setup is illustrated on Figure 1(right). The vertical black and gray lines represent the version intervals containing a key. The black lines represent updates present in the list of updates contained in that rectangle, while the gray lines and endpoints represent updates contained in buffers of $T$, which are illustrated at the top of the figure.

When performing $\text{Search}(v,x)$, first the rectangle $r$ covering point $(x,v)$ in the plane must be found. By using the B-tree $P_v$ associated with version $v$, $r$ can be found using $𝒪\left(H\right)$ I/Os. If $r$ is closed, then all updates inside $r$ are contained in the sorted list of updates stored in $r$, and these can be scanned in $𝒪\left(R/B\right)$ I/Os. If $r$ is open, then the result of the successor query may be affected by buffered updates, which are not stored in $r$. The rectangle $r$ must therefore be actualized, by merging all updates in buffers on the path from the root of $T$ to $r$ with the updates in $r$. The details of this operation are described in Section 2.4, where the actualize operation is shown to take amortized $𝒪\left(H\right)$ I/Os. After $r$ is actualized, the query continues by scanning the updates of $r$. If the result of the successor query is not contained in the rectangle $r$, then by the spanning requirement, the result of the query must be in the neighboring rectangle to the right, that similarly is actualized if it is open. In total, the operation spends amortized $𝒪\left(H+R/B\right)=𝒪\left(\frac{1}{\epsilon }{\log }_B\overline{N}\right)$ I/Os. Note that the operation easily can be modified to support member, predecessor, and strict predecessor or successor queries.

A $\text{Range}(v,x,y)$ query is performed very similarly to a Search query. The query may however touch more than two rectangles. Note that for the at most two rectangles containing the endpoints of the query we do not necessarily report all keys they contain at version $v$. These rectangles can be found using amortized $𝒪\left(H+R/B\right)$ I/Os by the argument above. For each intermediate rectangle accessed (and possibly actualized if it is open), then by the spanning requirement, a constant fraction of the updates scanned result in reported keys. Since accessing a rectangle takes amortized $𝒪\left(H+R/B\right)$ I/Os, and each rectangle contains $\mathrm{\Theta }\left(R\right)=\mathrm{\Theta }\left(B\cdot H\right)$ keys at version $v$, then amortized $𝒪\left(1/B\right)$ I/Os are spent for each key reported for an intermediate rectangle. In total, a Range query reporting $K$ keys takes amortized $𝒪\left(H+R/B+K/B\right)=𝒪\left(\frac{1}{\epsilon }{\log }_B\overline{N}+K/B\right)$ I/Os.

Each update, either an Insert or Delete, is applied to the current version $v_c$ of the set. The $B^{\epsilon }$-tree $T$ contains all buffered updates to the open rectangles, which cover the current version $v_c$. For an update operation, a tuple with the update and $v_c$ is added to the root buffer of $T$, which is stored in internal memory. In Section 2.4 it is shown that adding the update to the root buffer and handling possible buffer overflows takes amortized $𝒪\left(H/F\right)=𝒪\left(\frac{1}{\epsilon B^{1-\epsilon }}{\log }_B\overline{N}\right)$ I/Os.

To argue about the amortized cost of flushing the content of buffers down the tree $T$, we let the potential of each buffered update be $1/F$ multiplied by the height of the buffer the update is stored in, with the root buffer being at the largest height. One unit of released potential can cover $𝒪\left(1\right)$ I/Os. When adding an update to the tree, the root buffer is always stored in internal memory, and therefore no I/Os are needed to access it. However, the potential is increased by at most $1/F\cdot H$, and the operation therefore uses amortized $𝒪\left(H/F\right)$ I/Os.

In this section we show that $H$ is an upper bound on the height of the $B^{\epsilon }$-tree $T$.

We define the weight of a node at height $i$ in $T$ to be the number of updates on keys in the key range of the node, and let $w_i$ be a lower bound for the weight of a node at height $i$. The rectangles are at height $0$ of the tree, with the nodes of the tree starting at height $1$. The updates are both the $\overline{N}$ initial keys as well as the up to $\alpha \cdot \overline{N}$ additional updates. It holds that the weight of a node is the sum of the weights of its children. By induction on the number of updates we show that $w_i\ge B{\mathrm{\Delta }}^i$ for all nodes at all heights, except for the root. First note that the inequality holds for $i=0$, as any rectangle contains at least $4R\ge B$ updates when it was created. Initially, $\overline{N}$ updates are distributed into at most $\overline{N}/(4R)$ rectangles, where the number of updates in each rectangle is at least $4R\ge B$. Each internal node initially has degree $[\mathrm{\Delta },2\mathrm{\Delta }[$, except for the root that has degree $[2,2\mathrm{\Delta }[$. By induction on the tree height $i$, it holds that the initial tree satisfies $w_i\ge B{\mathrm{\Delta }}^i$, except for the root. Each update affects a root-to-leaf path of the tree. If the tree is not updated, then the weights of the nodes on the path can only grow, and therefore the inequality holds. If rectangles are merged, then one rectangle disappears together with all the ancestors having only this single rectangle as a leaf. The other rectangle and its ancestors up to the least common ancestor of the two merged leaves get their key ranges expanded. It follows that the surviving nodes after merging rectangles only can have their key range increase, and therefore the inequality holds. If a split occurs in any node at height $i$, then the degree of the node before the split is $2\mathrm{\Delta }$. The node is split into two nodes at height $i$, each with $\mathrm{\Delta }$ children. The weight of each of the two nodes is therefore at least $\mathrm{\Delta }\cdot w_{i-1}\ge \mathrm{\Delta }\cdot B{\mathrm{\Delta }}^{i-1}=B{\mathrm{\Delta }}^i$. Therefore, it holds that $w_i\ge B{\mathrm{\Delta }}^i$.

Since the number of updates is at most $(1+\alpha )\cdot \overline{N}$, we have $B{\mathrm{\Delta }}^i\le (1+\alpha )\cdot \overline{N}$ for all nodes at height $i$, except for the root. Since by definition $2\le \mathrm{\Delta }\le B$ and , we have ${\mathrm{\Delta }}^{i+1}\le 2\overline{N}$, i.e., $i\le {\log }_{\mathrm{\Delta }}\left(2\overline{N}\right)-1\le {\log }_{\mathrm{\Delta }}\overline{N}$. The height of $T$ is then at most the largest value of $i$ satisfying this inequality, plus one for the root, i.e., the height of $T$ is at most $1+{\log }_{\mathrm{\Delta }}\overline{N}\le 1+\lceil {\log }_{\mathrm{\Delta }}\overline{N}\rceil =H$.

The data structure above allows for an initial set of $\overline{N}$ keys to receive up to $\alpha \cdot \overline{N}$ persistent updates, for a constant . For any version $v$, we have $(1-\alpha )\cdot \overline{N}\le N_v\le (1+\alpha )\cdot \overline{N}$, i.e., $N_v=\mathrm{\Theta }\left(\overline{N}\right)$. Therefore, the asymptotic costs of all operations also hold with $\overline{N}$ replaced by $N_v$.

To allow for more than $\alpha \cdot \overline{N}$ updates, we create multiple copies of the data structure above using global rebuilding [29, 30]. Whenever the current data structure reaches $\alpha \cdot \overline{N}$ updates, a new data structure is created with initial set ${𝒮}_{v_c}$ and ${\overline{N}}_{\mathrm{new}}=|{𝒮}_{v_c}|$ (and new $H$ and $R$ parameters), with a new set of rectangles and a new $B^{\epsilon }$-tree $T$, where all buffers are empty. We compute ${𝒮}_{v_c}$ by performing $\text{Range}(v_c,-\mathrm{\infty },\mathrm{\infty })$ in amortized $𝒪\left(\frac{1}{\epsilon }{\log }_B\overline{N}+K/B\right)=𝒪\left(\overline{N}/B\right)$ I/Os. This actualizes all open rectangles which now can be closed. The new data structure can be build using $𝒪\left(\overline{N}/B\right)$ I/Os by a single scan of the sorted list containing ${𝒮}_{v_c}$. In the old data structure $\alpha \cdot \overline{N}$ updates have been performed before this rebuild is performed. By amortizing the rebuild cost over these updates, the amortized cost of each update is increased by $𝒪\left(1/B\right)$ I/Os, i.e., the asymptotic amortized cost of an update is not increased. As the space usage of the new data structure is $𝒪\left(\overline{N}/B\right)$ blocks, a similar argument can be used to amortize the space usage over the updates, maintaining a linear space usage in the total number of updates. This concludes the proof of Theorem 1.

We first consider the case when $M=\mathrm{\Omega }\left(HB\right)$. When actualizing a rectangle (see Section 2.3), the buffers at the $𝒪\left(H\right)$ nodes along the root-to-leaf path, with a total size of $𝒪\left(HB\right)$, are merged to produce a sorted list of updates to apply to the rectangle. As shown in Section 2.4, this can be done in amortized $𝒪\left(H\right)$ I/Os, by merging the buffers top-down. In the worst case, this requires $𝒪\left(H^2\right)$ I/Os. By instead merging the buffers using an external memory sorting algorithm, the worst-case number of I/Os can be improved to $𝒪\left(\mathrm{𝑠𝑜𝑟𝑡}\left(HB\right)\right)$. Previous approaches to improving the amortized performance of $B^{\epsilon }$-trees in the randomized [7] and worst-case [16] settings both assumed at least that $M=\mathrm{\Omega }\left(HB\right)$, in which case the sorting term trivially disappears by performing the sorting internally after reading the $H$ buffers into internal memory. The remaining challenge was handling flushing cascades, which occur when merging internal nodes of $T$ results in large buffers requiring many flushes in different directions. For our structure, we avoid this issue, by never merging internal nodes, and instead maintain the height of $T$ using global rebuilding. For the remainder of this section, we assume a large internal memory of size $M=\mathrm{\Omega }\left(HB\right)$ and describe how to achieve worst-case guarantees by incrementally performing amortized work.

In the previous section, we showed that there is no overhead on worst-case queries and updates compared to the amortized bounds, if the internal memory can hold all keys on a root-to-leaf path towards the same open rectangle. To lower the possible number of such keys, we slightly change the flushing strategy described in Section 2.4 where we only performed a flush when a buffer overflowed. Instead, for every $F$’th update, we flush along an entire root-to-leaf path, always flushing towards the child where most of the updates are going. We still flush at most $F$ keys, which preserves the property that internal nodes of $T$ contain at most $2\mathrm{\Delta }F$ updates. In the following, we show that this flushing strategy guarantees that all buffers contain $𝒪\left(F{\log }_2\mathrm{\Delta }\right)$ updates going towards the same child, and therefore also the same leaf. This implies that the assumption $M=\mathrm{\Omega }\left(HF{\log }_2\mathrm{\Delta }\right)=\mathrm{\Omega }\left(B^{1-\epsilon }{\log }_2\overline{N}\right)$ is sufficient to achieve no overhead for worst-case queries and updates. This is a factor $\mathrm{\Theta }\left(B^{\epsilon }/{\log }_{2}B\right)$ improvement over the previous smallest assumption on $M$ [16].

We can view each node as playing the subtracting game studied by Dietz and Raman [18] for the number of updates $x_1,x_2,x_3,\mathrm{\dots },x_{2\mathrm{\Delta }-1}$ going towards each of its at most $2\mathrm{\Delta }-1$ children. When at most $F$ updates are flushed towards a node, and ${\delta }_i$ new updates are going towards the $i$th child, then variable $x_i$ is increased by ${\delta }_i$. We flush towards the child $j$ where most of the updates are going which sets the variable $x_j=\max \{x_j-F,0\}$. Following [18, Theorem 3], scaled by a factor of $F$, this guarantees $x_i=𝒪\left(F{\log }_2\mathrm{\Delta }\right)$ for any $i$.

We also need to consider how merging and splitting nodes in $T$ impacts the subtraction games. Only leaves of $T$, corresponding to open rectangles, are merged. When an internal node is split, it corresponds to evenly distributing the $x_i$ variables from one game to two new games, except for one variable that is split into two new variables, each with a smaller or equal value. When a leaf, i.e., an open rectangle, is merged or split, the one or two rectangles involved are first actualized, which sets their variables to zero, a stronger operation than subtracting. Thus, the variable for a new rectangle is always zero and variables on root-to-leaf paths to actualized rectangles may be decremented. In all cases and for all games, variables are either decremented without adding to the game, or a copy of an existing game is created, where all variables in the copy are equal or smaller in value than before. This concludes the proof of Theorem 2.

In this section, we consider the small-memory setting with $M\ge 2B$, to overcome the theoretical limitation of the memory assumptions made in Sections 3.1 and 3.2. Actualizing a rectangle by merging the relevant updates on a root-to-leaf path to a rectangle requires $𝒪\left(H+\gamma \right)$ total I/Os, where $\gamma =\mathrm{𝑠𝑜𝑟𝑡}\left(B^{1-\epsilon }{\log }_2\overline{N}\right)$. The construction from the previous section directly results in worst-case Search queries using $𝒪\left(H+\gamma \right)$ I/Os and updates using $𝒪\left(\frac{1}{F}\left(H+\gamma \right)\right)$ I/Os. However, since Range queries are performed by repeatedly searching for the $\mathrm{\Theta }\left(1+K/R\right)$ rectangles intersecting the query, the worst-case number of I/Os is $\mathrm{\Theta }\left(\left(1+K/R\right)\left(H+\gamma \right)\right)=\mathrm{\Theta }\left(H+\gamma +\frac{K}{B}\left(1+\frac{\epsilon {\log }_{2}B}{B^{\epsilon }}{\log }_{M/B}\left(B^{-\epsilon }{\log }_2\overline{N}\right)\right)\right)$, notably with a multiplicative non-constant overhead on the reporting term. In this section, we describe how to guarantee Range queries in worst-case $\mathrm{\Theta }\left(H+\gamma +\frac{K}{B}\right)$ I/Os when $M\ge 2B$.

The worst-case I/O cost of a Range query can be improved by merging all the buffered updates to the open rectangles intersecting the query in a top-down, level-by-level fashion. That is, by essentially actualizing all the open rectangles intersected by the Range query simultaneously. We denote the updates already present in the rectangles the partial output list. Rather than applying the buffered updates to the rectangles, we merge them with the partial output list to obtain the final output. A given query $\text{Range}(v,x,y)$ reports $\mathrm{\Omega }\left(R\right)$ keys from each intermediate rectangles, i.e., all rectangles intersecting the query except for the two that contain the endpoints $x$ and $y$. Thus, in $𝒪\left((1+K/R)H+(R+K)/B\right)=𝒪\left(H+K/B\right)$ I/Os we can find all the relevant rectangles and compute the partial output list. To collect the buffered updates in $T$ for the intermediate open rectangles in sorted order, we merge the updates down level-by-level. We only move down the updates to versions earlier or equal to $v$ since only these can affect the query result. Once obtained, these updates are merged with the partial output list using linear I/Os to report the output of the Range query.

The buffered updates are stored in $T$, which contains the open rectangles at version $v_c$, however, the Range query is on the rectangles present at version $v$. Let $T_v$ denote the $B^{\epsilon }$-tree on open rectangles at version $v$, i.e., the state of $T$ when version $v$ was created. From $T_v$ to $T$ the tree may have changed, but no later updates are relevant for the query. Thus, the total number of relevant updates does not increase from $T_v$ to $T$, and each update remains on the root-to-leaf path towards the open rectangle to which the update is relevant. The relevant updates in $T$ can be collected in sorted lists ordered by level by traversing each root-to-leaf path in $T$ towards open rectangles intersecting the query using $𝒪\left((1+K/R)H\right)$ I/Os. To bound the I/Os to move the updates down level-by-level, we show that the total number of updates is $𝒪\left(B^{1-\epsilon }{\log }_2\overline{N}+K/H\right)$. To this end, we need the additional invariant that the buffer of a degree one node is empty, which we show how to obtain below. Let $T_v^{\prime }$ be the subtree of $T_v$ consisting of all nodes on root-to-leaf paths to rectangles intersecting the query. Then split $T_v^{\prime }$ into two root-to-leaf paths $p_x$ and $p_y$ to $x$ and $y$, respectively, along with all the subtrees hanging off $p_x$ or $p_y$. For a node on $p_x$ (symmetrically $p_y$) of degree at least two there may be one or more subtrees $T_{sub}$ hanging off the node. Since only the nodes of $T_{sub}$ with degree at least two have non-empty buffers, if $T_{sub}$ has $\mathrm{\ell }$ leaves, the number of buffered updates in $T_{sub}$ is at most $𝒪\left((\mathrm{\ell }-1)B\right)$. Thus, the number of buffered updates in $T_v^{\prime }$ excluding degree one nodes on $p_x$ and $p_y$ is $𝒪\left(K/H\right)$. A degree one node on $p_x$ and $p_y$ may have a large degree in $T_v$, but since it only has one child in the direction of the query, due to the subtracting game, it stores at most $𝒪\left(F{\log }_2\mathrm{\Delta }\right)$ relevant updates. The number of degree one nodes on $p_x$ and $p_y$ is at most $2H$, and they together contribute $𝒪\left(B^{1-\epsilon }{\log }_2\overline{N}\right)$ buffered updates, which we locate and sort separately using $𝒪\left(H+\gamma \right)$ I/Os. For the remaining $𝒪\left(K/H\right)$ buffered updates, we merge them level-by-level using $𝒪\left(H+K/B\right)$ I/Os. In total, the worst-case number of I/Os to perform a Range query is $𝒪\left(H+\gamma +K/B\right)$ I/Os.