论文标题
外部记忆词典具有最差的更新成本
External-memory dictionaries with worst-case update cost
论文作者
论文摘要
$ b^ε$ -Tree [Brodal和Fagerberg 2003]是一个简单的I/O高效外部内存模型数据结构，支持比B树快的更新速度，其查询性能与B-Tree可比性相当：对于任何积极的常数$ε<1 $插入和删除，则需要$（\ frac {1} {b^{1-ε}} \ log_ {b} n）$ time（而不是$ o（\ log_bn）$用于经典b-tree的时间），查询取得$ O（log_bn）$ o（log_bn）$ time和范围查询$ k $ k $ o o o o o（b log_bn $ o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o（log_bn）尽管$ b^ε$ -tree具有最佳的更新/查询权衡，但运行时间已摊销。另一个结构是Bender等人介绍的写作优化的跳过列表。 [PODS 2017]具有与$ b^ε$ -tree相同的性能，但具有随机而不是摊销的运行时间。在本文中，我们介绍了$ b^ε$ -tree的变体，这些变体具有确定性的最差运行时间，与原始的摊销运行时间相同。
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(\frac{1}{B^{1-ε}}\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^ε$-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.
