Tokutek and some staff where common vititors to the boston mysql meetup. If I remember they were using "fractal trees" instead of b-trees. Trading cpu cycles for disk io. It was interesting tech.
Quote:"The idea behind FT(fractal Trees) 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."
http://highscalability.com/blog/2014/8/6/tokutek-white-paper...
Quote:"The idea behind FT(fractal Trees) 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."
some other links:
http://web.archive.org/web/20150414215556/http://www.tokutek...
http://assets.en.oreilly.com/1/event/36/How%20TokuDB%20Fract...