Personal tools

Performance of Fractal-Tree Databases

— filed under:

Michael Bender, Stony Brook University and Tokutek, Inc.

  • Computer Science Seminar
When Fri, Apr 30, 2010
from 11:00 AM to 12:00 PM
Where RH316
Contact Name
Add event to calendar vCal

Insertion bottlenecks lie at the heart of database and file-system innovations, best practices, and system workarounds. Most databases and file systems are based on B-tree data structures, and suffer from the performance cliffs and unpredictable run times of B-trees.  In this talk, I introduce the Fractal Tree data structure and explain how it provides dramatically improved performance in both theory and in practice.

From a theoretical perspective, if B is the block-transfer size, the B-tree performs O(log_B N) block transfers per insert in the worst case. In contrast, the Fractal Tree structure performs O((log_B N)/B) memory transfers per insert, which translates to run-time improvements of two orders of magnitude.

To relate that theory to practice, I present an algorithmic model for B-tree performance bottlenecks. I explain how the bottlenecks affect best practice and how database designers typically modify B-trees to try to mitigate the bottlenecks.  Then I show how Fractal Tree structures can attain faster insertion rates, intuitively by transforming disk-seek bottlenecks into disk-bandwidth bottlenecks

I conclude with performance results.  Tokutek has developed a transaction-safe Fractal-Tree storage engine for MySQL.  I present performance results, showing how the system can maintain rich indexes more efficiently than B-trees.  Surprisingly, Fractal Tree structures seem to maintain their order-of-magnitude competitive advantage over B-trees on both traditional rotating media as well as SSDs.

« May 2019 »