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.
DOWNLOAD NOW
Publisher:Acunu Published:11/20/2012 Type:
Length:
Format:
Whitepaper
5 pages
Rating:
No votes yet
Share:Send to a friend
Topics: Java Web Design Architecture Infrastructure Tools & Methods Languages Computer Science Industry