Computer Science Colloquium - Martin Farach-Colton, Rutgers

“Ubiquitous Write Optimization”

The B-tree was introduced some 45 years ago as a dictionary data structure for data that is too big to fit in memory. As an out-of-core replacement for a binary search tree, the B-tree has played a central role in indexed storage systems, such as databases and file systems. B-trees have optimal I/O performance on searches but substantially suboptimal I/O performance on insertions and deletions. Over the past two decades researchers have developed Òwrite-optimizedÓ dictionaries to address the insertion/deletion bottleneck of the B-tree. We say that a write-optimized dictionary (WOD) is a dictionary data structure that has (1) substantially better insertion performance than a B-tree and (2) query performance at or near that of a B-tree. Today, WODs are displacing B-trees in both SQL and NoSQL databases, and in file systems. This talk will review the algorithmic theory of WODs and the experience of deploying them in databases (at Tokutek, which I founded) and in file systems (in BetrFS).