John Iacono

External-memory dictionaries with worst-case update cost

2022 · arXiv (Cornell University)

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$ …