Personal tools
 

Performance of Fractal-Tree Databases

— filed under:

Michael Bender, Stony Brook University and Tokutek, Inc.

What
  • 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
iCal

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.

« February 2018 »
February
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728
Upcoming Events
Computer Science Seminar
Mon, Feb 19, 2018
Software Systems Engineering with Evolutionary Algorithms Kate Holdener
Computer Science Seminar
Wed, Feb 21, 2018
Secure Software Development using Agile Approach: Issues and Potential Solutions Imran Ghani, Monash University Malaysia
Previous events…
Upcoming events…