Fraktalbaum-Index
Ein B-Baum, der Schreibvorgänge auf dem Weg nach unten in Puffern sammelt, statt bei jedem Zugriff bis ganz zum Blatt zu laufen.
Die Konstruktion stammt von Tokutek und beruht auf sogenannten Bε-Bäumen. Jeder innere Knoten trägt zusätzlich zu seinen Zeigern einen Puffer, in dem eingehende Änderungen abgelegt werden. Ist der Puffer voll, wird er eine Ebene tiefer entleert. Ein Schreibvorgang kostet somit keinen zufälligen Plattenzugriff bis zur Blattebene, sondern wird über viele Änderungen amortisiert, die gebündelt nach unten wandern.
Das Ergebnis liegt zwischen den beiden üblichen Extremen: deutlich geringere Schreibverstärkung als bei einem B-Baum, bei gleichzeitig erhaltener sortierter Ordnung und damit schnellen Bereichsabfragen, um die sich LSM-Bäume erst erkämpfen müssen. Die Technik trieb TokuDB für MySQL an und lebt in Perconas Codebasis weiter, erreichte aber nie die Verbreitung von LSM.