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.
|Rating:||Share:||Send to a friend|
|Topics:||Java Web Design Architecture Infrastructure Tools & Methods Languages Computer Science Industry|