HackerPapers

arXiv:1103.4282cs.DS

Stratified B-trees and versioning dictionaries

Andy Twigg, Andrew Byde, Grzegorz Milos, Tim Moreton, John Wilkes, 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 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.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.DBDatabases

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 2 threads, from Apr 2011 to May 2016. Found in 2 HN submissions from Apr 2011 to Jan 2018. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. An LSM-Tree-based Ultra-Large Key-Value Store for Small Data [pdf] 1 comment

    • Every time I come across a new KV store, I go out looking for an userland implementation from the Acunu guys: http://arxiv.org/abs/1103.4282. So far, none seen yet. I'd like to see Stratified B Trees kick LSMs' butts. Or the other way around. I can't code this yet. But I can…

      eyanView on HNParent context

  2. Copy-on-write B-tree finally beaten. 3 comments

    • I strongly prefer links to the abstract: http://arxiv.org/abs/1103.4282v2 This lets you: (a) read the abstract before deciding whether or not to read the paper (b) easily find earlier (or later) versions of the paper (c) easily search for other papers the authors have on the…

      wnoiseView on HNParent context

    • If we're replacing blog links with arXiv abstract links, note that there are actually two papers linked, both interesting. "Stratified B-trees and versioning dictionaries" http://arxiv.org/abs/1103.4282 This is actually the newer paper, and presents the "Stratified B-Tree" data…

      jholmanView on HNParent context

    • Right, but the blog post does give a second reference. I prefer giving the Arxiv abstract list, which always links to the current version of the PDF. http://arxiv.org/abs/1103.4282

      chalstView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.