























In [SPAA2007], Bender et al. define a streaming B-tree (or index) as one that supports updates in amortized $o(1)$ IOs, and present a structure achieving amortized $O((\log N)/B)$ IOs and queries in $O(\log N)$ IOs. We extend their result to the partially-persistent case. For a version $v$, let $N_v$ be the number of keys accessible at $v$ and $N$ be the total number of updates. We give a data structure using space $O(N)$, supporting updates to a leaf version $v$ with $O((\log N_{v})/B)$ amortized IOs and answering range queries returning $Z$ elements with $O(\log N_{v} + Z/B)$ IOs on average (where the average is over all queries covering disjoint key ranges at a given version). This is the first persistent `streaming' index we are aware of, i.e. that supports updates in $o(1)$ IOs and supports efficient range queries.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。