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