As mentioned in parts 1 and 2, having many disk seeks are bad (they slow down performance). Fractal tree data structures minimize disk seeks on ad-hoc insertions, whereas B-trees practically guarantee that disk seeks are performed on ad-hoc insertions. As a result, fractal tree data structures can insert data up to two orders of magnitude faster than B-Trees can.

In this post, let’s examine deletions, and get an intuitive understanding for why fractal-tree data structures exhibit the same two orders of magnitude faster deletions than B-trees. In MySQL 5.1, this advantage is really eye-popping for TokuDB v. InnoDB, because InnoDB does not use its insert buffer for deletions. I understand there is a delete buffer in 5.5, which I …

In part 1, I discussed why having many disk seeks are bad (they slow down performance), and how fractal tree data structures minimize disk seeks on ad-hoc insertions, whereas B-trees practically guarantee that disk seeks are performed on ad-hoc insertions. As a result, fractal tree data structures can insert data up to two orders of magnitude faster than B-Trees can.

Now that insertion disk seeks are out of the way (and I don’t want to shortchange the importance of getting rid of these seeks!), let’s look at other places where databases perform seeks, and see if we can get rid of them. Over my next couple of posts, I will look at several use cases and analyze whether disk seeks are required. If disk seeks are required, then performance will suffer on large amounts of data, for TokuDB and any other disk-based storage engines.

I recently discovered that there’s a youtube video of the talk I gave at OpenSQL Camp in Portland in 2009.

This is a whiteboard presentation and is less well developed than the talk I gave a the MySQL conference (I posted those slides two days ago. But since it includes audio it may be easier to understand.

This talk presents the data structure underlying the TokuDB storage engine for MySQL.

Here’s the talk I presented at the MySQL User Conference. This talk is a fairly technical talk on how fractal trees work.

You can find this talk and other mostly technical material at http://tokutek.com/technology/.

I (Bradley C. Kuszmaul) am presenting two talks at the MySQL User Conference.

The first talk is a 5-minute talk at tonight’s Ignite MySQL session organized by Brian Aker. I’ll present some performance measurements on the Intel X25E SSD. The bottom line is that although I can get the 3,300 random 4KB writes per second, as the spec sheet advertises, I cannot seem to get more than about 11,000 reads per second, although the spec sheet says I should get 35,000.

My second talk is tomorrow (Thursday) at 10:50am, where I’ll talk about Fractal Trees. I’ll explain how Fractal Trees work, and show why they can get one to two orders of magnitude speedup on insertions compared to B-tree indexes. The talk is about data structures and algorithms, but I think it should be easy for everyone to understand. If you want to know why Fractal …