Abstract
I present the cache-oblivious streaming B-tree, a high performance alternative to the traditional B-tree. Modern databases and file systems are based on B-trees. As a result, they can exhibit performance cliffs and unpredictable run times. Replacing B-trees with cache-oblivious streaming B-trees can remove some of these performance deficiencies.
I explain some of the technical issues that we needed to address to turn the streaming B-tree prototype into an industrial-strength product. Then I explain how legacy and established practice influenced our engineering decisions.
Chapter PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bender, M.A. (2009). From Streaming B-Trees to Tokutek: How a Theoretician Learned to be VP of Engineering. In: Vahrenhold, J. (eds) Experimental Algorithms. SEA 2009. Lecture Notes in Computer Science, vol 5526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02011-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-02011-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02010-0
Online ISBN: 978-3-642-02011-7
eBook Packages: Computer ScienceComputer Science (R0)