Datenstrukturdienstag:
Log-Structured-Merge-Tree (LSM-Tree).

Das ist ein Suchbaum. Die Idee: Man hat mehrere Bäume (Bei Wikipedia C_0 und C_1). Der erste Baum liegt im RAM, der zweite auf der Festplatte. Neue Einträge kommen in den RAM. Wenn C_0 einen Threshold übersteigt, werden Daten von C_0 nach C_1 migriert, also auf die Festplatte.

Der Vorteil: Neu eingesetzte Daten liegen direkt im RAM und können schnell abgerufen werden. Aus diesem Grund wird diese Struktur auch gern bei In-Memory-Datenbanken verwendet.

Es kommt auch vor, dass man mehrere Level an Bäumen hat, z. B. ein C_2, das irgendwo auf einem anderen Server im Cluster liegt.