Tokutek White Paper: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing
Wednesday, August 6, 2014 at 8:56AM
Todd Hoff in Database, Paper

What data structure does your database use? It's not something the typical database user spends much time pondering. Since data structure is destiny, what data structure your database uses is a key point to consider in your selection process.

We know CouchDB uses a modified B+ tree. We've learned a lot fascinating details over the years about the use of Log-structured merge-trees in Cassandra, HBase and LevelDB. So B+ trees and LSMs seem familiar by now.

What may not be so familiar is Tokutek's Fractal Tree Indexing technology that is supposed to be even better than B+ trees and LSMs.

As a comparison between Fractal Tree Indexing and LSMs, Bradley Kuszmaul, Chief Architect at Tokutek, has written a detailed paper, a must read for the algorithmically inclined or someone interested in database internals: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing.

Here's a quick intro to Fractal Tree (FT) indexes:

The idea behind FT indexes is to maintain a B tree in which each internal node of the tree contains a buffer. When a data record is inserted into the tree, instead of traversing the entire tree the way a B tree would, we simply insert the Eventually the root buffer will fill up with new data records. At that point the FT index copies the inserted records down a level of the tree. Eventually the newly inserted records will reach the leaves, at which point they are simply stored in a leaf node as a B tree would store them. The data records descending through the buffers of the tree can be thought of as messages that say “insert this record”. FT indexes can use other kinds of messages, such as messages that delete a record, or messages that update a record.

The paper starts with an explanation of write amplification, read amplification, and space amplification, the metrics that will be used to compare B trees, FT indexes, and LSMs. These are nicely detailed sections and well worth the price of admission.

Write amplification: the amount of data written to storage compared to the amount of data that the application wrote. Read amplification: the number of I/O’s required to satisfy a particular query. Space amplification: the space required by a data structure can be inflated by fragmentation or requirements for temporary copies of the data.

The paper then has sections explaining in great detail the inner magic of B trees, FT indexes, and LSMs. Which are also worth the price of admission.

B-tree index: a search tree in which every node of the tree can have many children. LSM: The idea behind LSM trees is to maintain a collection of sorted runs of data, each run containing key-value pairs with the keys sorted in ascending order. FT indexes were explained above.

 

As you might expect the analysis shows FT indexes the winner:

A solid data structure concept is not enough. The paper points out that the data structure a database uses is only one part of entire product. You must also consider features like MVCC, transactions with ACID recovery, two-phase distributed commit, backup, and compression.

Paper: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing.

 

On Hacker News

Article originally appeared on (http://highscalability.com/).
See website for complete article licensing information.