  The $B^{\epsilon}$-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient
external-memory-model data structure that supports updates orders of magnitude
faster than B-tree with a query performance comparable to the B-tree: for any
positive constant $\epsilon<1$ insertions and deletions take
$O(\frac{1}{B^{1-\epsilon}}\log_{B}N)$ time (rather than $O(\log_BN)$ time for
the classic B-tree), queries take $O(\log_BN)$ time and range queries returning
$k$ items take $O(\log_BN+\frac{k}{B})$ time. Although the $B^{\epsilon}$-tree
has an optimal update/query tradeoff, the runtimes are amortized. Another
structure, the write-optimized skip list, introduced by Bender et al. [PODS
2017], has the same performance as the $B^{\epsilon}$-tree but with runtimes
that are randomized rather than amortized. In this paper, we present a variant
of the $B^{\epsilon}$-tree with deterministic worst-case running times that are
identical to the original's amortized running times.

Data Structures and Algorithms