Stratified B-trees and versioning dictionaries

Preprint English OPEN
Twigg, Andy ; Byde, Andrew ; Milos, Grzegorz ; Moreton, Tim ; Wilkes, John ; Wilkie, Tom (2011)
  • Subject: 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.
  • References (8)

    [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.

  • Metrics
    No metrics available
Share - Bookmark