Paper Info
Title
Simple, robust and highly concurrent b-trees with node deletion
Abstract
Why might B-tree concurrency control still be interesting? For two reasons: (i) currently exploited "real world" approaches are complicated; (ii) simpler proposals are not used because they are not sufficiently robust. In the "real world", systems need to deal robustly with node deletion, and this is an important reason why the currently exploited techniques are complicated. In our effort to simplify the world of robust and highly concurrent B-tree methods, we focus on exactly where B-tree concurrency control needs information about node deletes, and describe mechanisms that provide that information. We exploit the Blink -tree property of being "well-formed" even when index term posting for a node split has not been completed to greatly simplify our algorithms. Our goal is to describe a very simple but nonetheless robust method.
Year
DOI
Venue
2004
10.1109/ICDE.2004.1319981
ICDE
Keywords
Field
DocType
computational complexity,concurrency control,tree data structures,tree searching,B-tree,concurrency control,node deletion,robust method
Data mining,Timestamp-based concurrency control,Computer science,Multiversion concurrency control,Theoretical computer science,Optimistic concurrency control,Distributed computing,Isolation (database systems),Concurrency control,Distributed concurrency control,Concurrent computing,Non-lock concurrency control,Database
Conference
ISSN
ISBN
Citations 
1063-6382
0-7695-2065-0
10
PageRank 
References 
Authors
0.66
14
1
Name
Order
Citations
PageRank
David B. Lomet1100.66