Lazy B-Trees

Balanced binary search trees (BSTs) exist in many varieties, with AVL trees [1] and red-black trees [26] the most widely known. When augmented with subtree sizes, they support all sorted dictionary operations in $𝒪\left(\log N\right)$ worst-case time. Simpler variants can achieve the same via randomization [47, 39] or amortization [48]. In external memory, B-trees [8], often in the leaf-oriented flavor as B⁺-trees and augmented with subtree sizes, are the benchmark. They support all sorted-dictionary operations in $𝒪\left({\log }_{B}N\right)$ I/Os. By batching queries, buffer trees [3, 4] substantially reduce the cost to amortized $𝒪\left(\frac{1}{B}{\log }_{M/B}\frac{N}{B}\right)$ I/Os, but are mostly useful in an offline setting due to the long delay from query to answer. ${\text{B}}^{\epsilon }$-trees [15] avoid this with a smaller buffer of operations per node to achieve amortized $𝒪\left(\frac{1}{\epsilon B^{1-\epsilon }}{\log }_{B}N\right)$ I/Os for updates and $𝒪\left(\frac{1}{\epsilon }{\log }_{B}N\right)$ I/Os for queries (with immediate answers), where $\epsilon \in (0,1]$ is a parameter.

The dynamic-optimality conjecture for Splay trees [48] resp. the GreedyBST [38, 41, 21] algorithm posits that these methods provide an instance-optimal binary-search-tree algorithm for any (long) sequence of searches over a static set of keys in a binary search tree. While still open for Splay trees and GreedyBST, the dynamic optimality of data structures has been settled in some other models: it holds for a variant of skip lists [13], multi-way branching search trees, and B-trees [13]; it has been refuted for tournament heaps [42]. As in lazy search trees, queries clustered in time or space allow a sequence to be served faster. Unlike in lazy search trees, insertions can remain expensive even when no queries ever happen close to them. A more detailed technical discussion of similarities and vital differences compared to lazy search trees appears in [44, 45].

When only minimum-queries are allowed, a sorted dictionary becomes a priority queue (PQ) (a.k.a. “heap”). In internal memory, all operations except delete-min can then be supported in $𝒪\left(1\right)$ amortized [25] or even worst-case time [14, 19]. In external memory, developing efficient PQs has a long history. For batch use, buffer-tree PQs [4] and the I/O-efficient heap of [37] support $k$ operations of insert and delete-min in $𝒪\left(\frac{k}{B}{\log }_{M/B}\frac{N}{M}\right)$ I/Os, with $N$ denoting the maximum number of stored keys over the $k$ operations. The same cost per operation can be achieved in a worst-case sense [16] (i.e., $B$ subsequent insert/delete-min operations cost $𝒪\left({\log }_{M/B}\frac{N}{M}\right)$ I/Os).

None of these external-memory PQs supports decrease-key. The I/O-efficient tournament trees of [37] support a sequence of insert, delete-min, and decrease-key with $𝒪\left(\frac{1}{B}{\log }_2\frac{N}{B}\right)$ I/Os per operation. A further $\log \log N$ factor can be shaved off [32] (using randomization), but that, surprisingly, is optimal [23]. A different trade-off is possible: insert and decrease-key are possible in $𝒪\left(\frac{1}{B}{\log }_{M/B}\frac{N}{B}\right)$ amortized I/Os at the expense of driving up the cost for delete/delete-min to $𝒪\left(\frac{M^{\epsilon }}{B}{\log }_{M/B}^2\frac{N}{B}\right)$ [28].

Biased search trees [9] maintain a sorted set, where each element $e$ has a (dynamic) weight $w(e)$, such that operations in the tree spend $𝒪\left(\log \frac{W}{w(e)}\right)$ time, for $W$ the total weight, $W={\sum }_{e}w(e)$. Biased search trees can be built from height-balanced trees ($(2,b)$-globally-biased trees [9]) or weight-balanced trees (by representing high-weight elements several times in the tree [40]), and Splay trees automatically achieve the desired time in an amortized sense [48, 40].

None of the original designs are well suited for external memory. Feigenbaum and Tarjan [24] extended biased search trees to $(a,b)$-trees for that purpose. However, during the maintenance of $(a,b)$-trees, some internal nodes may have a degree much smaller than $a$ (at least $2$), which means that instead of requiring $𝒪\left(N/B\right)$ blocks to store $N$ weighted elements, they require $𝒪\left(N\right)$ blocks in the worst case.⁴⁴4In particular, in [24], they distinguish internal nodes between minor and major, minor being the nodes that have degree or have a small rank. All external nodes are major. The authors in [24] indeed leave it as an open problem to find a space-efficient version of biased $(a,b)$-trees. Another attempt at an external biased search tree data structure is based on deterministic skip lists [5]. Yet again, the space usage seems to be $\mathrm{\Omega }\left(N\right)$ blocks of memory.⁵⁵5Unfortunately, it remains rather unclear from the description in the article exactly which parts of the skiplist “towers” of pointers of an element are materialized. Unlike in the unweighted case, an input could have large and small weight alternating, with half the elements of height $\approx {\log }_{b}W$. Fully materializing the towers would incur $\mathrm{\Omega }\left(n{\log }_{b}W\right)$ space; otherwise this seems to require a sophisticated scheme to materialize towers on demand, e.g., upon insertions, and we are not aware of a solution.

To our knowledge, no data structure is known that achieves $𝒪\left({\log }_B\frac{W}{w(e)}\right)$ I/Os for a dynamic weighted set in external memory while using $𝒪\left(N/B\right)$ blocks of memory.

Deferred data structuring refers to the idea of successively establishing a query-driven structure on a dataset. This is what lazy search trees do upon queries. While the term is used more generally, it was initially proposed in [35] on the example of a (sorted) dictionary. For an offline sequence of $q$ queries on a given (static) set of $N$ elements, their data structure uses $𝒪\left(N\log q+q\log N\right)$ time. In [20], this is extended to allow update operations in the same time (where $q$ now counts all operations). The refined complexity taking query ranks into account was originally considered for the (offline) multiple selection problem: when $q$ ranks are sought, leaving gaps ${\mathrm{\Delta }}_1,\mathrm{\dots },{\mathrm{\Delta }}_{q+1}$, $\mathrm{\Theta }\left({\sum }_{i=1}^{q+1}|{\mathrm{\Delta }}_i|\log (N/{\mathrm{\Delta }}_i)\right)$ comparisons are necessary and sufficient [22, 33]. For multiple selection in external memory, $\mathrm{\Theta }\left({\sum }_{i=1}^{q+1}\frac{|{\mathrm{\Delta }}_i|}{B}{\log }_{M/B}\frac{N}{|{\mathrm{\Delta }}_i|}\right)$ I/Os are necessary and sufficient [7, 17], even cache-obliviously [17, 18].

Closest to lazy search trees is the work on online dynamic multiple selection by Barbay et al. [6, 7], where online refers to the query ranks arriving one by one. As pointed out in [44], the crucial difference between all these works and lazy search trees is that the analysis of dynamic multiple selection assumes that every insertion is preceded by a query for the element, which implies that insertions must take $\mathrm{\Omega }(\log N)$ time. (They assume a nonempty set of elements to initialize the data structure with, for which no pre-insertion queries are performed.) Barbay et al. also consider online dynamic multiple selection in external memory. By maintaining a B-tree of the pivots for partitioning, they can support updates – again, implicitly preceded by a query – at a cost of $\mathrm{\Theta }({\log }_{B}N)$ I/Os each.

In the context of adaptive indexing of databases, deferred data structuring is known under the name of database cracking [30, 29, 27]. While the focus of research is on systems engineering, e.g., on the partitioning method [43], some theoretical analyses of devised algorithms have also appeared [50, 49]. These consider the worst case for $q$ queries on $N$ elements similar to the original works on deferred data structures.

The remainder of the paper is structured as follows. Section 2 describes the gap data structure (our partial external biased search tree) and key innovation. Section 3 sketches the changes needed to turn the interval data structure from [44] into an I/O-efficient data structure; the full details, including our streamlined potential function, appear in Appendix A of the arXiv version of this paper. In Section 4, we then show how to assemble the pieces into a proof of our main result, Theorem 1. We conclude in Section 5 with some open problems.

A search for a gap proceeds by searching in buckets $b_0,b_1,b_2,\mathrm{\dots }$ until the desired gap is found in some bucket $b_k$. To search in all buckets up until $b_k$ requires ${\sum }_{j=0}^k𝒪\left(2^j\right)=𝒪\left(2^k\right)$ I/Os, which is therefore up to constant factors the same cost as searching in only bucket $b_k$. Consider some gap ${\mathrm{\Delta }}_i$, which has the $\mathrm{\ell }$th heaviest weight, i.e., it is located at index $\mathrm{\ell }$, when sorting all gaps decreasingly by weight. By the invariant, the buckets are sorted decreasingly by the weight of their internal elements. Let the bucket containing ${\mathrm{\Delta }}_i$ be $b_k$. It must then hold that the sizes of the earlier buckets does not allow for ${\mathrm{\Delta }}_i$ to be included, but that bucket $b_k$ does. Therefore,

As $\left|b_j\right|=B^{2^j}$, the sums are asymptotically equal to the last term of the sum up to constant factors (arXiv version, Lemma 10). It then holds that $\mathrm{\ell }=𝒪\left(B^{2^k}\right)$ and $\mathrm{\ell }=\mathrm{\Omega }\left(B^{2^{k-1}}\right)=\mathrm{\Omega }\left({(B^{2^k})}^{1/2}\right)$. Thus ${\log }_B(\mathrm{\ell })=\mathrm{\Theta }\left({\log }_B\left|b_k\right|\right)$, and conversely $2^k=\mathrm{\Theta }\left({\log }_B\mathrm{\ell }\right)$. The gap ${\mathrm{\Delta }}_i$ can thus be found using $𝒪\left({\log }_B\frac{W}{w_i}\right)$ I/Os, concluding the GapByElement operation.

When performing GapIncrement on gap ${\mathrm{\Delta }}_i$, the weight is increased by $1$. In the conceptual list, this may result in the gap moving to an earlier index, with the order of the other gaps the same. This move is made in the conceptual list (Figure 2) by swapping ${\mathrm{\Delta }}_i$ with its neighbor. As the buckets are ordered by element value, swapping with a neighbor (by weight) in the same bucket does not change the bucket structure. When swapping with a neighbor in an earlier bucket, however, the bucket structure must change to reflect this. Following the conceptual list (Figure 2), this gap is a lightest (minimum-weight) gap in bucket $b_{k-1}$. This may then result in ${\mathrm{\Delta }}_i$ moving out of its current bucket $b_k$, into some earlier bucket. As the gap moves to an earlier bucket, some other gap must take its place in bucket $b_k$. Following the conceptual list, it holds that this gap is a lightest (minimum-weight) gap in bucket $b_{k-1}$, and so on for the remaining bucket moves.

When performing GapDecrement, the gap may move to a later bucket, where the heaviest gap in bucket $b_{k+1}$ is moved to bucket $b_k$.

In both cases, a lightest gap in one bucket is swapped with a heaviest gap in the neighboring (later) bucket. To find lightest or heaviest gaps in a bucket, we augment the nodes of the B-tree of each bucket with the values of the lightest and heaviest weights in the subtree for each of its children. This allows for finding a lightest or heaviest weight gap in bucket $b_j$ efficiently, using $𝒪\left({\log }_B\left|b_j\right|\right)$ I/Os. Further, this augmentation can be maintained under insertions and deletions.

Upon a GapIncrement or GapDecrement operation, the desired gap ${\mathrm{\Delta }}_i$ can be located in the structure using $𝒪\left({\log }_B\frac{W}{w_i}\right)$ I/Os, and the weight is adjusted. We must then perform swaps between the buckets, until the invariant that buckets are sorted decreasingly by weight holds. This swapping may be performed on all buckets up to the last touched bucket. For GapIncrement the swapping only applies to earlier buckets as the weight of ${\mathrm{\Delta }}_i$ increases, and the height of the tree in the latest bucket is $𝒪\left({\log }_B\frac{W}{w_i}\right)$. For GapDecrement the swapping is performed into later buckets, but only up to the final landing place for weight $w_i-1$. If $w_i\ge 2$, the height of the tree in the last touched bucket is $𝒪\left({\log }_B\frac{W}{w_i-1}\right)=𝒪\left(1+{\log }_B\frac{W}{w_i}\right)$. If $w_i=1$, gap ${\mathrm{\Delta }}_i$ is to be deleted. The gap is swapped until it is located in the last bucket, from where it is removed. We have $𝒪\left({\log }_B\frac{W}{w_i}\right)=𝒪\left({\log }_{B}W\right)$, as $w_i=1$, whereas the height of the last bucket is $𝒪\left({\log }_{B}G\right)=𝒪\left({\log }_{B}W\right)$, as $G\le W$. Therefore both GapIncrement and GapDecrement can be performed using $𝒪\left({\log }_B\frac{W}{w_i}\right)$ I/Os.

When GapSplit is performed on gap ${\mathrm{\Delta }}_i$, the gap is removed and replaced by two new gaps ${\mathrm{\Delta }}_i^{\prime }$ and ${\mathrm{\Delta }}_{i+1}^{\prime }$, s.t. $\left|{\mathrm{\Delta }}_i\right|=\left|{\mathrm{\Delta }}_i^{\prime }\right|+\left|{\mathrm{\Delta }}_{i+1}^{\prime }\right|$. In the conceptual list, the new gaps must reside at later indexes than ${\mathrm{\Delta }}_i$. As the sizes of the buckets are fixed, and the number of gaps increases, some gap must move to the last bucket. Similarly to GapIncrement and GapDecrement, the order can be maintained by performing swaps of gaps between consecutive buckets: First, we replace ${\mathrm{\Delta }}_i$ (in its spot) by ${\mathrm{\Delta }}_i^{\prime }$; if this violates the ordering of weights between buckets, we swap ${\mathrm{\Delta }}_i^{\prime }$ with the later neighboring bucket, until the correct bucket is reached. Then we insert ${\mathrm{\Delta }}_{i+1}^{\prime }$ into the last bucket and swap it with its earlier neighboring bucket until it, too, has reached its bucket. Both processes touch at most all ${\log }_B{\log }_{2}G$ buckets and spend a total of $𝒪\left({\log }_{B}G\right)$ I/Os.

To determine the global rank of a gap ${\mathrm{\Delta }}_i$, the total weight of all smaller gaps must be computed. This is equivalent to the sum of the local ranks of ${\mathrm{\Delta }}_i$ over all buckets: $r({\mathrm{\Delta }}_i)={\sum }_j{r}_j({\mathrm{\Delta }}_i)$. First we augment the B-trees of the buckets, such that each node contains the total weight of all gaps in the subtree. This allows us to compute the local rank $r_j({\mathrm{\Delta }}_i)$ of a gap ${\mathrm{\Delta }}_i$ inside a bucket $b_j$ using $𝒪\left({\log }_B\left|b_j\right|\right)$ I/Os. The augmented values can be maintained under insertions and deletions in the tree within the stated I/O cost. When searching for the gap ${\mathrm{\Delta }}_i$, the local rank $r_j({\mathrm{\Delta }}_i)$ of all earlier buckets $b_j$ up to the bucket $b_k$, which contains ${\mathrm{\Delta }}_i$, can then be computed using $𝒪\left({\log }_B\frac{W}{w_i}\right)$ I/Os in total.

It then remains to compute the total size of gaps smaller than ${\mathrm{\Delta }}_i$ in all buckets after $b_k$, i.e., the sum of the local ranks $r_{\mathrm{\ell }}({\mathrm{\Delta }}_i)$ for all later buckets $b_{\mathrm{\ell }}$, $\mathrm{\ell }>k$, to compute in total the global rank $r({\mathrm{\Delta }}_i)$. As these buckets are far bigger, we cannot afford to query them. Note that any gaps in these later buckets must fall between two consecutive gaps in $b_k$, as the gaps are non overlapping in element-value space. Denote the space between two gaps in a bucket as a hole. We then further augment the B-tree to contain in each hole of bucket $b_j$ the total size of gaps of later buckets contained in that hole, and let each node contain the total size of all holes in the subtree. See Figure 4 for an illustration of which gaps contributes to a hole.

This then allows computing the global rank $r({\mathrm{\Delta }}_i)$ of gap ${\mathrm{\Delta }}_i$, by first computing the local rank $r_j({\mathrm{\Delta }}_i)$ in all earlier buckets $b_j$, i.e., for all $j\le k$, and then adding the total size of all smaller holes in $b_k$. The smaller holes in $b_k$ exactly sum to the local ranks $r_{\mathrm{\ell }}({\mathrm{\Delta }}_i)$ for all later buckets $b_{\mathrm{\ell }}$ for $\mathrm{\ell }>k$. As this in total computes ${\sum }_j{r}_j({\mathrm{\Delta }}_i)$, then by definition, we obtain the global rank $r({\mathrm{\Delta }}_i)$ of the gap ${\mathrm{\Delta }}_i$.

For a GapByRank operation, some rank $r$ is given, and the gap ${\mathrm{\Delta }}_i$ is to be found, s.t. ${\mathrm{\Delta }}_i$ contains the element of rank $r$, i.e., the global rank . The procedure is as follows. First, the location of the queried rank $r$ is computed in the first bucket. If this location is contained in a gap ${\mathrm{\Delta }}_i$ of the bucket, then ${\mathrm{\Delta }}_i$ must be the correct gap, which is then returned. Otherwise, the location of $r$ must be in a hole. As the sizes of the gaps contained in the first bucket is not reflected in the augmentation of later buckets, the value of $r$ is updated to reflect the missing gaps of the first bucket: we subtract from $t$ the local rank $r_0({\mathrm{\Delta }}_i)$ of the gap ${\mathrm{\Delta }}_i$ immediately after the hole containing the queried rank $r$. This adjusts the queried rank $r$ to be relative to elements in gaps of later buckets. Put differently, the initial queried rank $r$ is the queried global rank, which is the sum local ranks; we now remove the first local rank again. This step is recursively applied to later buckets, until the correct gap ${\mathrm{\Delta }}_i$ is found in some bucket $b_k$, which contains the element of the initially queried global rank $r$. As the correct gap ${\mathrm{\Delta }}_i$ must be found in the bucket $b_k$ containing it, the GapByRank operation uses $𝒪\left({\log }_B\frac{W}{w_i}\right)$ I/Os to locate it.

The augmentation storing the sizes of all holes in a subtree can be updated efficiently upon insertions or deletions of gaps in the tree, or upon updating the size of a hole. However, computing the sizes of the holes upon updates in the tree is not trivial. If a gap is removed from a bucket, the holes to the left resp. right of that gap are merged into a single hole, with a size equal to the sum of the previous holes. If the removed gap is moved to a later bucket, the hole must now also include the size of the removed gap. A newly inserted gap must, by the non-overlapping nature of gaps, land within a hole of the bucket, which is now split in two. If the global rank of the inserted gap is known, then the sizes of the resulting two holes can be computed, s.t. the global rank is preserved.

In the operations on the gap structure, GapByElement or GapByRank do not change the sizes of gaps, so the augmentation does not change. Upon a GapIncrement or GapDecrement operation, the size of some gap ${\mathrm{\Delta }}_i$ changes. This change in size can be applied to all holes containing ${\mathrm{\Delta }}_i$ in earlier buckets using $𝒪\left({\log }_B\frac{W}{w_i}\right)$ I/Os in total. Then swaps are performed between neighboring buckets until the invariant that buckets are sorted by weight, holds again. During these swaps, the sizes of gaps do not change, which allows for computing the global rank of the gaps being moved, and update the augmentation without any overhead in the asymptotic number of I/Os performed. The total number of I/Os to perform a GapIncrement or GapDecrement operation does not increase asymptotically, and therefore remains $𝒪\left({\log }_B\frac{W}{w_i}\right)$.

When a GapSplit is performed, a single gap ${\mathrm{\Delta }}_i$ is split. As the elements in the two new gaps ${\mathrm{\Delta }}_i^{\prime }$ and ${\mathrm{\Delta }}_{i+1}^{\prime }$ remain the same as those of the old gap ${\mathrm{\Delta }}_i$, there cannot be another gap between them. The value in all smaller holes therefore remains correct. Moving ${\mathrm{\Delta }}_{i+1}^{\prime }$ to the last bucket then only needs updating the value of the holes of the intermediate buckets, which touches at most all ${\log }_B{\log }_{2}G$ buckets spending $𝒪\left({\log }_{B}G\right)$ I/Os in total. Swaps are then performed, where updating the augmentation does not change the asymptotic number of I/Os performed.

To bound the space usage, note that the augmentation of the B-trees at most increase the node size by a constant factor. Since the space usage of a B-tree is linear in the number of stored elements, and since each gap is contained in a single bucket, the space usage is $𝒪\left(G/B\right)$ blocks in total. This concludes the proof of Theorem 3.