Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Twigg, Andy; Byde, Andrew; Milos, Grzegorz; Moreton, Tim; Wilkes, John; Wilkie, Tom (2011)
Languages: English
Types: Preprint
Subjects: Computer Science - Data Structures and Algorithms, Computer Science - Databases
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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. http://arxiv.org/abs/ 1103.2566. ArXiv e-prints, March 2011.
    • [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.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Collected from