Stratified B-trees and Versioned Dictionaries

External-memory versioned dictionaries are fundamental to file systems, databases and many other algorithms. The ubiquitous data structure is the copy-onwrite (CoW) B-tree. 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. We describe the ‘stratified B-tree’, which is the first versioned dictionary offering fast updates and an optimal tradeoff between space, query and update costs.
Publisher:Acunu Published:11/20/2012 Type:
5 pages
No votes yet
Share:Send to a friend
Topics: Java Web Design Architecture Infrastructure Tools & Methods Languages Computer Science Industry

Spotlight Resources

Camel Essential Components

DZone's 170th Refcard is an essential reference to Camel, an open-source, lightweight, integration library.  This Refcard is authored by...

Want your resource here? Contact our team today.