All about Stratified B-trees
By Andy Twigg
19 Jul 2011
Category:
Technical Articles
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. It also performs exceptionally well on SSDs.
Our paper at HotStorage'11 describes some details of the structure (a fuller, more theoretical version with proof will be published soon). A video of the talk can be found here.
LinkedIn techtalk
I was invited to give a techtalk at LinkedIn on Stratified B-trees, and the video of the talk is below (original blog post)
Tech Talk: Andy Twigg (Acunu) -- Stratified B-Tree and Versioned Dictionaries from Talks at LinkedIn on Vimeo.
blog comments powered by Disqus