External-memory dictionaries with worst-case update cost

2022/11/11 by Das, Rathish, Iacono, John, Nekrich, Yakov
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2211.06044

Abstract

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(\frac1B^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.

Related

• Buffered Partially-Persistent External-Memory Search Trees
• Stratified B-trees and versioning dictionaries
• Optimal query/update tradeoffs in versioned dictionaries
• Using Hashing to Solve the Dictionary Problem (In External Memory)
• Belga B-trees