External-memory dictionaries with worst-case update cost
share
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(1/B^1-ϵlog_BN) 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+k/B) 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.
READ FULL TEXT