B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load

In the classic External Memory (EM) model, the $n$ data items of a problem instance must be transferred in blocks of a fixed size $B$ between a block-addressible external memory and an internal Main Memory (MM), which can store up to $M$ data items and perform computations. Typically, $n\gg M>B$ and the MM can only store a small number of blocks throughout processing, say $M/B=𝒪(1)$. Though Vitter’s Parallel Disk Model can formalize more general settings [30, Section $2.1$], we are interested in the most basic case with one, merely block-addressible, EM device and one computing device with MM. The cost of a computation is typically measured in the number of block-reads from EM (Is), the number of block-writes to EM (Os), or the total number of IOs performed on EM. For basic algorithmic tasks like the range search, block search trees with $\alpha =\mathrm{\Theta }(B)$ support algorithms with asymptotically optimal total IOs (e.g. [30, Section $10$]). Classic B-Trees [4] guarantee that every block, beside the root, has a load-factor of at least $1/2$ and that all leaves are at equal depth, using a deterministic balance criteria. The B*-Tree variant [23, Section 6.2.4] guarantees a load-factor of at least $2/3$ based on a (deterministic) overflow strategy that shares keys among the two neighboring nodes on equal levels. Yao’s Fringe Analysis [32] showed that inserting keys under a random order in (deterministic balanced) B-Trees yields an expected asymptotic load-factor of $\ln (2)\approx 69\%$, and the expected asymptotic load-factor is $2\ln (3/2)\approx 81\%$ for B*-Trees. For general workloads however, maintaining higher load-factors (with even wider overflow strategies) further increases the update write-bounds in block search trees [3, 24]. The B⁺-Tree variant for key-value pairs, which stores the values separate from the keys to increase the load-factor and thus fan-outs, is heavily used in practical file systems, see e.g. [14].

The IO-optimized¹¹1$B^{\epsilon }$-trees are usually called “write-optimized”, though they aim to minimize IOs and not writes (Os). B^ε-Tree [13, 7] provides smooth trade-offs between $𝒪({\log }_{1+{\alpha }^{\epsilon }}(n)/{\alpha }^{1-\epsilon })$ amortized IOs per update and $𝒪({\log }_{1+{\alpha }^{\epsilon }}n)$ block-reads (Is) for searches. E.g. tuning parameter $\epsilon =1$ retains the bounds of B-Trees and $\epsilon =1/2$ provides improved bounds. In the fully update IO-optimized case ($\epsilon =0$) however, searches have merely a $𝒪(\log n)$ bound for the number of block-reads. The main design idea to achieve this is to augment the non-leaf nodes of a B-Tree with additional “message buffers” so that a key insertion can be stored close to the root. Messages then only need propagation, further down the tree, once a message buffer is full (cf. [13, Section $3.4$] and [7]). Clearly, the state of either of those (deterministic) structures depends heavily on the actual sequence in which the keys were inserted in them.

For security or privacy reasons, some applications, see e.g. [19], require data structures that do not reveal any information about historical states to an observer of the memory representation, i.e. evidence of keys that were deleted or evidence of the keys’ insertion sequence. Data structures are called uniquely represented (UR) if they have this strong history independence property. For example, sorted arrays are UR, but the aforementioned search trees are not UR due to deterministic rebalancing. Early results [28, 29, 1] show lower and upper bounds on comparison-based search in UR data structures on the pointer machine. Using UR hash tables [9, 26] in the RAM model, pointer structures can also be mapped uniquely into memory. (See [9, Thm. $4.1$], [10, Sec. $2$].)

The Randomized Search Trees are defined by inserting keys, one at a time, in order of a random permutation into an initially empty binary search tree. The well-known Treap [27, 31] maintains the tree shape, of the permutation order, and supports efficient insertions, deletions, and searches (see also [25, Chapter 1.3]). Searches read with high probability $𝒪(\log n)$ tree nodes, any insertion (or deletion) performs expected $𝒪(1)$ rotations (writes), and the expected subtree weight, beneath the updated key, is $𝒪(\log n)$. Beside UR, these remarkably strong bounds are central in the design of simple MM algorithms for dynamic problems. The constant writes bound of Treaps, and some Red-Black Tree variants, is particularly valuable for persistent data structures [16, 22], that is $𝒪(1)$ amortized writes are not sufficient to design fully-persistent data structures with linear space. The logarithmic weight bound for example is particularly valuable for obtaining a $𝒪(1)$ query time for order-queries in dynamic sets with $𝒪(\log n)$ expected update time [12, Section 5]. This is a central sub-problem in designing fully-persistent data structures, see [18] for example. Further important examples include asymmetric read/write cost settings [8, 5] and parallel computation [11], or simply storage media that can only endure few write-cycles.

Golovin [20] introduced the B-Treap as the first UR data structure for Byte-addressable External Memory (BEM). The B-Treap originates from a certain block storage layout of an associated (binary) Treap, i.e. the block tree is obtained, bottom-up, by iteratively placing subtrees, of a certain size, in one block node²²2E.g. byte-addressable memory is required for intra-block child pointers and each key maintains a size field that stores its subtree size (in a binary Treap), resulting in logarithmic writes (cf. Os in Table 1). . The author shows bounds of B-Treaps, under certain parameter conditions: If $\alpha$ is at least polylogarithmic, specifically $\alpha =\mathrm{\Omega }({(\ln n)}^{\frac{1}{1-\delta }})$ for some $\delta \in (0,1)$, then updates have expected $𝒪(\frac{1}{\delta }{\log }_{\alpha }n)$ block-writes and range-queries have expected $𝒪(\frac{1}{\delta }{\log }_{\alpha }n+k/\alpha )$ block-reads, where $k$ is the output size (see Theorem 1 in [20]). The paper also discusses experimental data, from a non-dynamic implementation, that shows an expected load-factor close to $1/3$ [20, Sec.$6$]. Though this storage layout approach allows leveraging known bounds of Treaps to analyze B-Treaps, the block size conditions are limiting for applications of B-Treaps in algorithms. Since the update algorithm is rather involved, Golovin [21] proposed a simpler, Skip-List based EM approach for a UR solution.

The known Skip-List based approaches [21] and [6] avoid the restrictions on $\alpha$, however both require an involved form of history independent hash-table for strings of key values (see [21, Section 2.2.2]). Moreover, the B-Skip-List [21] provides only a logarithmic $𝒪(\log n)$ depth bound (see [6, Lemma 15]) and the EM Skip-List in [6] offers only a weaker notion of History Independence than UR and has logarithmic block-writes (cf. [6, proof of Lem.19]).

Our work provides the first UR EM search tree that is generally applicable for all block sizes $\alpha \ge 2$, whilst providing bounds that improve on the only known UR EM search tree solution, B-Treap [20].

We introduce a new design technique, and provide a self-contained analysis, that leads to a two-layer randomized data structure called $(\alpha ,\epsilon )$-Randomized Block Search Trees (RBSTs), where $\alpha$ is the block size and $\epsilon \in (0,1/2]$ a tuning parameter for the space-efficiency of our secondary layer (see Section 2). Without the secondary structures, the RBSTs are precisely the distribution of trees that are obtained by inserting the keys, one at a time, under a random order into an initially empty block search tree (e.g. $\alpha =1$ yields the Treap distribution). RBSTs are UR and the algorithms for searching are simple. In Section 2.1, we give a partial-rebuild algorithm for dynamic updates that occupies $𝒪(1)$ blocks of temporary MM storage and performs a number of writes (Os) to EM that is proportional to the structural change in the RBST. Its number of reads (Is) is bounded within a small factor of the writes. We prove three performance bounds for $(\alpha ,\epsilon )$-RBSTs in terms of block-reads, block-writes, and blocks stored.

Section 3 shows that searching reads expected $𝒪({\epsilon }^{-1}+{\log }_{\alpha }n)$ blocks, and that RBST depth is with high probability $𝒪({\epsilon }^{-1}+\sqrt{{\epsilon }^{-1}\ln n}+{\log }_{\alpha }n)$ for all $\alpha \ge 2$. If $\alpha =\mathrm{polylog}(n)$, RBST depth is with high probability $𝒪({\epsilon }^{-1}+{\log }_{\alpha }n)$. Section 4 shows that $(\alpha ,\epsilon )$-RBSTs have an expected asymptotic load-factor of at least $(1-\epsilon )$ for every $\epsilon \in (0,1/2]$. Combining both analysis techniques, we show in Section 5 that dynamic updates perform expected $𝒪({\epsilon }^{-1}+{\log }_{\alpha }(n)/\alpha )$ block-writes and expected $𝒪({\epsilon }^{-2}+(1+\frac{{\epsilon }^{-1}+\log n}{\alpha }){\log }_{\alpha }n)$ block-reads.

See Table 1 for an overview of the write bounds (Os), and read bounds (Is), of the known bottom-up B-Treap and our proposed top-down RBST. To compare the update write-bounds (Os), note that RBSTs have constant $𝒪({\epsilon }^{-1})$ writes for all $\alpha$ that are admissible in B-Treaps, whereas B-Treaps write at least logarithmic $\mathrm{\Omega }({\log }_{\alpha }n)$ blocks. This is a significant asymptotic improvement. To compare the update read-bounds (Is), note that the factor $(1+\frac{\log n}{\alpha })=𝒪(1)$ for all $\alpha =\mathrm{\Omega }({\ln }^{\frac{1}{1-\delta }}n)$ with $\delta \in (0,1)$ that are admissible in B-Treaps, whereas the factor $\frac{1}{\delta }\to \mathrm{\infty }$ for $\alpha$ close to $\ln (n)$. That is, the RBST bounds improve on all B-Treap bounds. Thus, RBSTs are simple UR search trees, for all block sizes $\alpha \ge 2$, that simultaneously provide improved search, storage utilization, and write-efficiency, compared to the bottom-up B-Treap [20].

Comparing also with non-UR structures, $(\alpha ,\epsilon )$-RBSTs are, to the best of our knowledge, the first EM structure that provides storage-efficiency and write-efficiency for every update. The decisive novelty of our tree structure is that all block-nodes of the primary layer use the maximum fan-out and that the block-nodes of the secondary layer use a weight-proportional fan-out, i.e. proportional to the number of keys that are stored in the subtree. The design of our secondary layer structures has thus nothing in common with the “message-buffers” in $B^{\epsilon }$-trees. Our result is incomparable to IO-optimized $B^{\epsilon }$-trees: Though RBSTs are UR and provide better bounds for space, searching (Is), and writes (Os), the block-reads (Is) for updates are $\mathrm{\Omega }({\log }_{\alpha }n)$ and thus worse than the IO-bound of the (non-UR) $B^{\epsilon }$-Tree.

Our buffers are search trees that consist of nodes similar to the primary tree. They also store the keys with the $\alpha$ smallest priority values, from the subtree, in their block. However, the fan-out of internal nodes varies based on the number of keys $n\le \alpha +\beta$ in the subtree. Define $\delta (n)=\min \{\alpha +1,\max \{1,\lceil \frac{n-\alpha }{\rho }\rceil \}\}$ as the fan-out bound for a subtree of weight . We defer the calibration of the parameter $\rho =\mathrm{\Theta }(\alpha /\epsilon )$ to the start of the proof of Theorem 9. The subtree weight of buffering nodes is maintained explicitly, with the aforementioned in-pointers. To obtain UR, the buffer layout is again defined recursively solely based on the set of keys in the buffer and the random permutation $\pi$.

For fan-out bound $\delta =1$, the subtree root has at most one child, which yields a list of blocks. The keys inside each block are stored in ascending key order, and the blocks in the list have ascending priority values. That is, the first block contains those keys with the $\alpha$ smallest priorities, the second block contains, from the remaining $n-\alpha$ keys, those with the $\alpha$ smallest priorities, and so forth.

For fan-out bound $\delta \in [2,\alpha +1]$, we also store the keys with the $\alpha$ smallest priorities in the root. We call those keys with the $\delta -1$ smallest priority values the active separators of this block. The remaining $n-\alpha$ keys in the subtree are partitioned in $\delta$ sets of key values, using the active separators only. Each of these key sets is organized recursively, in a buffer, and the resulting trees are referenced as the children of the active separators.

This concludes the definition of our tree structure.

See the right part of Figure 1 for an example of the $(\alpha ,\epsilon )$-RBST on the same permutation ($y$-coordinates) and $25$ keys ($x$-coordinates) that consists of $11$ blocks. (See [31] for Cartesian Tree representations.) The active separators are shown in black, non-active separators in gray, and the block nodes as rectangles.

Some remarks on the definition of primary and secondary RBST nodes are in order. The buffer is UR since the storage layout only depends on the priority order $\pi$ of the keys, the number of keys in the buffer, and the order of the key values in it. Note that summing the state values of the child pointers yields $s_1+\mathrm{\dots }+s_{\delta }+\alpha =n$ the weight of the subtree, without additional block reads. Moreover, whenever an update in the secondary structure brings the buffer’s root above the threshold, i.e. $s_1+\mathrm{\dots }+s_{\alpha +1}\ge \beta$, we have that its root contains those keys with the $\alpha$ smallest priorities form the set and all keys are active separators, i.e. the buffer root immediately provides both invariants of blocks from the primary tree.

Note that this definition of RBSTs not only naturally contains the randomized search trees of block size $\alpha$, but also allows a smooth trade-off towards a simple list of blocks (respectively $\epsilon =\mathrm{\infty }$ and $\epsilon =0$). Though leaves are non-empty, it is possible that the tree shape defined by the random permutation $\pi$ yields leaves with load as low as $1/\alpha$ in RBSTs.

As stated at the beginning of this section, the definition above does not yield an efficient algorithm to actually maintain RBSTs. The remainder of this section specifies our algorithms for searching, dynamic insertion, and dynamic deletion in RBSTs. Our analysis is presented in Sections 3, 4, and 5.

As with ordinary B-Trees, we determine with binary search on the array the successor of search value $q$, i.e. the smallest active separator key in the block that has a value of at least $q$, and follow the respective child pointer. If the current search node is buffering, then we additionally check the set of non-active separators in the block (i.e. all keys) during the search to find the actual successor of $q$ from $X$. The search descends until the list, i.e. block nodes with fan-out $\le 1$, in the respective RBST buffer is found. Since the lists are sorted by priority, we check all keys, by scanning the $𝒪(1/\epsilon )$ blocks of the list, to determine the successor of $q$. This point-search extends to range-queries in the ordinary way by considering the two search paths of the range’s boundary $[q,q^{\prime }]$.

To summarize, successor and range search occupies $𝒪(1)$ blocks in main memory, does not write blocks, and the number of block-reads is $𝒪(D)$, where $D$ is the depth of the RBST.

Recall that there are in the worst case $𝒪(1/\epsilon )$ nodes with fan-out $\delta \le 1$ on the search path of $q$. Consider the active separators $\{x_1,\mathrm{\dots },x_d\}$ of the RBST blocks that contain $q$ in their search-interval. This set consists of two sequences $\{x_i^{+}\}$ and $\{x_i^{-}\}$ of strictly decreasing and increasing key values, respectively. Since their priority values are strictly increasing, i.e. , we have from the known bounds of ordinary Treaps that $d=𝒪(\log n)$ with high probability [27, Lem. 4.8]. Thus, RBST depth is with high probability less than $𝒪({\epsilon }^{-1}+\log n)$.

To show our sharper search bound, let random variable $D_q$ be the number of primary tree nodes $v$ that contain $q$ in their interval $[\mathrm{\ell }(v),r(v)]$. Partition $\{1,\mathrm{\dots },n\}$ with intervals of the form $[{\alpha }^i,{\alpha }^{i+1})$ for indices $0\le i\le \lfloor {\log }_{\alpha }n\rfloor$. E.g. permutation $\pi$ induces an assignment of keys $x\in X$ to an unique layer index, i.e. $i$ with $\pi (x)\in [{\alpha }^i,{\alpha }^{i+1})$. For internal node $v$ let $p^{\ast }(v)=\min \{\pi (x):x\text{ is stored in }v\}$ and $p^{†}(v)$ is the maximum over the set. Note that $p^{\ast }(v)+\alpha -1\le p^{†}(v)$, since every internal node stores exactly $\alpha$ keys. Thus, $D_q$ counts nodes $v$ that either have both $p^{\ast }(v),p^{†}(v)\in [{\alpha }^i,{\alpha }^{i+1})$ or have that $p^{†}(v)$ has a larger layer index than $i$. We bound the expected number of nodes of the first kind, since there are in the worst case at most $\lfloor {\log }_{\alpha }n\rfloor$ from the second kind. Defining for every layer index $i$ a random variable $V_i$ that counts the tree nodes in that layer

we have that $D_q\le \lfloor {\log }_{\alpha }n\rfloor +V$, where $V={\sum }_{i\ge 0}{V}_i$ is the total number of blocks of the first kind. The remainder of the proof shows bounds for $V_i$.

Let for each index $i$, , and $K_i^{+}=K_i\setminus K_i^{-}$. Thus, $K_i\subset K_{i+1}$, and $|K_i|={\alpha }^{i+1}-1$. Define $Y_i^{-}$ to be the number of consecutive keys form $K_i^{-}$ that are less than $q$ but not contained in $K_{i-1}$. Analogously, random variable $Y_i^{+}$ counts those larger than $q$ and $Y_i:=Y_i^{-}+Y_i^{+}$ is the number of consecutive keys of $K_i$, whose range contain $q$, but do not contain elements from $K_{i-1}$. Since all separators of primary nodes are active and internal nodes store exactly $\alpha$ keys, we have $V_i(\pi )\le Y_i(\pi )/\alpha$ for every $\pi \in \mathrm{Perm}(n)$.

Next we bound $𝔼[Y_i^{-}]$ based on a sequence of binary events: Starting at $q$, we consider the elements $x\in K_i^{-}$ in descending key-order and count as “successes” if $x\in K_i\setminus K_{i-1}$ until one “failure” ($x\in K_{i-1}$) is observed. If $K_i^{-}$ has no more elements, the experiment continues on $K_i^{+}$ in ascending key order. Defining $Z_i$ as the number of successes on termination, we have $Y_i^{-}(\pi )\le Z_i(\pi )$. The probability to obtain failure, after observing $j$ successes, is $\frac{|K_{i-1}|}{|K_i|-j}$, which is at least $p_i:=\frac{|K_{i-1}|}{|K_i|}$ for all $j\ge 0$ and $i>0$.

Hence $\mathrm{Pr}[Z_i=j]\le \mathrm{Pr}[Z_i^{\prime }=j+1]$ where random variable $Z_i^{\prime }\sim NB(1,p_i)$, i.e. the number of trials to obtain one failure in a sequence of independent Bernoulli trials with failure probability $p_i$. Since $𝔼[Z_i^{\prime }]=1/p_i$, we have .

We thus have for all $\alpha \ge 2$, which shows the lemma’s statement for the primary tree nodes.

Since there are in the worst case $𝒪(1/\epsilon )$ nodes with fan-out $\delta \le 1$ on a search path, it remains to bound the expected number of secondary nodes with a fan-out in $[2,\alpha ]$ on a search path. If there are any such nodes to count, consider the top-most buffering node $v$ and let $n^{\prime }:=|X(v)|$ be its subtree weight. For any fixed integer $n^{\prime }$, random variables regarding the subtree only depend on the relative order of the $n^{\prime }$ keys, which are uniform from $\mathrm{Perm}(n^{\prime })$. Since the expected number of keys in either of the $\delta (n^{\prime })$ sections is $(n^{\prime }-\alpha )/\delta (n^{\prime })$, the expected number of keys in the section of $q$ has an upper bound of the form $(n^{\prime }-\alpha )/\delta (n^{\prime })=𝒪(\alpha /\epsilon )$. Since the bound holds for all $n^{\prime }$, this bound holds unconditionally. The lemma’s $𝒪(1/\epsilon )$ expectation bound on the nodes follows from the fact that all secondary nodes (with $\delta \ge 2$) of a search path store exactly $\alpha$ keys. Thus, the expected number of such nodes is $𝒪(1/\epsilon )$. $◀$

Next, we show our depth bound that improves on the simpler $𝒪({\epsilon }^{-1}+\ln n)$ bound above. We first give a tail-estimate for the number of primary nodes and then an estimate for the number of secondary nodes on a search-path to the fixed query point $q$.

We will tighten above’s analysis by considering the relative priority orders of the $Y_i$ keys that are counted in layer $i$, where $i\le r=𝒪({\log }_{\alpha }n)$. Indeed, even if random variable $Y_i$ exceeds its mean $\mathrm{\Theta }(\alpha )$ by a large factor, the blocks of a search path to $q$ can only contain all $Y_i$ keys if also their relative priority-order have a, very specific, deep block structure. This observation allows to obtain a much stronger tail bound.

Let ${\widehat{Y}}_i$ be the number of keys from $K_i\setminus K_{i-1}$ that are stored in the block of a node on the search path to $q$, i.e. ${\widehat{Y}}_i\le Y_i$. We will show for the random variables ${\widehat{Y}}_i$ that to obtain a tailbound that is strong enough for a union bound of all $n+1$ possible queries $q\notin X$. Recall from Stirling’s formula, that for all $n\ge 1$.

To observe $c\alpha$ keys from layer $i$ stored in $c$ blocks of a search path, the $\alpha$ keys stored in the last block must all have priorities larger than the first $(c-1)\alpha$ keys, the $\alpha$ keys in the second to last block must all have priorities larger than the first $(c-2)\alpha$ keys, and so forth. Further, each of the $\alpha !$ relative orders of any one such batch of $\alpha$ keys does not affect them being stored in the block of a search path. Thus the probability that $c\alpha$ keys have relative priorities to form $c$ blocks of a search path is at most

where the last inequality is due to and $\frac{e\sqrt{\alpha }}{c^{\alpha }}\le {(e/c)}^{\alpha }\iff \sqrt{\alpha }\le e^{\alpha -1}$ being true for all $\alpha \ge 2$. Thus .

For $c\ge e^3$, and we have

From the layer partition, we have that the outcome of $Y_i$ is independent of $Y_{i+1}$, i.e. bounds for $Y_i$ are with respect to $|K_i|$ and regardless of the actual set $K_i$, and all relative priority-orders of the keys in $K_i\setminus K_{i-1}$ are equally likely. Since across all $r$ layers the probability bound for the sum is maximized when all $r$ factors have equal thresholds, we have

where the third last inequality uses that ${\log }_{\alpha }(n+1)\le r\le {\log }_{\alpha }(n)+1$, the second last inequality uses that $\alpha \ge 2$ and $2\alpha \le n$, and and the last inequality uses that $\alpha /\ln \alpha >1$. $◀$

We believe that Lemma 4 cannot be improved substantially without redesigning the secondary structures, update algorithms, and proofs. Specifically, parameter constellations with small $\delta (n)=\omega (1)$ provide a major obstacle in obtaining better bounds.

For the number of secondary tree nodes, which have ${\delta }_v\in [2,\alpha ]$ and store exactly $\alpha$ keys, we observe that having $d$ such nodes on a search path requires that the topmost node has one child with weight $N_1\ge (d-1)\alpha +\rho$, and the second topmost node must have one child with weight $N_2\ge (d-2)\alpha +\rho$, and so forth, where the RBST parameter $\rho =\mathrm{\Theta }(\alpha /\epsilon )$. Thus, at least $d/4$ nodes must have weight $N_i\ge (d/2)\alpha +\rho$, and consequently fan-out value at least $k\ge \delta ((d/2)\alpha +\rho )=\mathrm{\Omega }(\epsilon d)$. Using our $\mathrm{Pr}[\delta (N_i)\ge k]\le e^{2-k}$ bound of Corollary 17 on the fan-out of a child, we obtain the probability of having $d$ such nodes on a search path is at most ${\prod }_{i=d/4}^{d/2}\exp (2-\delta (N_i))\le e^{-\mathrm{\Omega }(\epsilon d^2)}$, i.e. a high-probability bound for all $d=\omega (1)$.

Thus, the number secondary nodes $({\delta }_v\ge 2)$ is at most $d=O({\log }_{\alpha }n)$ with probability at least $1-n^{-\mathrm{\Omega }(\epsilon \ln (n)/{(\ln \alpha )}^2)}$, and $d=O(\sqrt{{\epsilon }^{-1}\ln n})$ with probability at least $1-n^{-\mathrm{\Omega }(1)}$. $◀$