Copy-on-write B-tree finally beaten by Andy Twigg, Andrew Byde, Grzegorz Mi?o´s, Tim Moreton, John Wilkesy and Tom Wilkie.
Abstract:
A classic versioned data structure in storage and computer science is the copy-on-write (CoW) B-tree – it underlies many of today’s file systems and databases, including WAFL, ZFS, Btrfs and more. Unfortunately, it doesn’t inherit the B-tree’s optimality properties; it has poor space utilization, cannot offer fast updates, and relies on random IO to scale. Yet, nothing better has been developed since. We describe the ‘stratified B-tree’, which beats the CoW B-tree in every way. In particular, it is the first versioned dictionary to achieve optimal tradeoffs between space, query and update performance. Therefore, we believe there is no longer a good reason to use CoW B-trees for versioned data stores.
I was browsing a CS blog aggregator when I ran across this. Looked like it would be interesting for anyone writing a versioned data store for a topic map application.
A more detailed account appears as: A. Byde and A. Twigg. Optimal query/update tradeoffs in versioned dictionaries. http://arxiv.org/abs/1103.2566. ArXiv e-prints, March 2011.
******
The Copy-on-write B-tree finally beaten paper has been updated: See: http://arxiv.org/abs/1103.4282v2