Physical Sciences and Mathematics Commons^™

External-Memory Dictionaries With Worst-Case Update Cost, Rathish Das, John Iacono, Yakov Nekrich

Michigan Tech Publications

The Bϵ-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 ϵ < 1 insertions and deletions take O(B11-ϵ logB N) time (rather than O(logB N) time for the classic B-tree), queries take O(logB N) time and range queries returning k items take O(logB N + Bk) time. Although the Bϵ-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ϵ-tree but with runtimes that are randomized rather than amortized. In this paper, we present a variant of the Bϵ-tree with deterministic worst-case running times that are identical to the original’s amortized running times.