Persistent Cache-oblivious Streaming Indexes

2017/07/25 by Andrew Twigg, Twigg, Andrew
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1707.08186

openalex publication_date 2017/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• The Persistent Buffer Tree : An I/O-efficient Index for Temporal Data
• Buffered Partially-Persistent External-Memory Search Trees
• B-tree indexes for high update rates
• Cache-Oblivious Persistence
• Dynamic Indexability: The Query-Update Tradeoff for One-Dimensional Range Queries