Stratified B-Tree and Versioned Dictionaries by Andy Twigg (Acunu). (video)
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.
I haven’t had time to watch the video but you can find some other resources on stratified B-Trees at Andy’s post All about stratified B-trees.
[…] While you are thinking about what that will mean for using MySQL engines, remember Stratified B-Tree and Versioned Dictionaries. […]
Pingback by Oracle rigs MySQL for NoSQL-like access « Another Word For It — October 2, 2011 @ 6:37 pm