publication . Preprint . 2011

Stratified B-trees and versioning dictionaries

Twigg, Andy; Byde, Andrew; Milos, Grzegorz; Moreton, Tim; Wilkes, John; Wilkie, Tom;
Open Access English
  • Published: 22 Mar 2011
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 all known semi-external memory versioned B-trees, including the CoW B-tree. In particular, it is the first versioned dictionary to achieve optimal tradeoffs between space, query and update performance.
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Databases
Download from

[1] R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173-189, 1972.

[2] Bruno Becker and Stephan Gschwind. An asymptotically optimal multiversion b-tree. The VLDB Journal, 5(4):264-275, 1996.

[3] Michael A. Bender and Martin Farach-Colton et al. Cache-oblivious streaming b-trees. In SPAA '07, pages 81-92, New York, NY, USA, 2007. ACM.

[4] Jeff Bonwick and Matt Ahrens. The zettabyte file system, 2008.

[5] Gerth Stolting Brodal and Rolf Fagerberg. Lower bounds for external memory dictionaries. In SODA '03, pages 546-554, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics.

[6] A. Byde and A. Twigg. Optimal query/update tradeoffs in versioned dictionaries. 1103.2566. ArXiv e-prints, March 2011. [OpenAIRE]

[7] J R Driscoll and N Sarnak. Making data structures persistent. In STOC '86, pages 109-121, New York, NY, USA, 1986. ACM.

[14] Ohad Rodeh. B-trees, shadowing, and clones. Trans. Storage, 3:2:1-2:27, February 2008. [OpenAIRE]

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue