Ein Blog

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.

Datenstrukturdienstag: B-Bäume und B+-Bäume (nein, das B steht nicht für “Binary”). Beides selbst-balancierende Suchbäume.

Was ist “Balancierend”? Wenn man einen Baum hat, in dem man Daten sucht, ist die Zeit, die man braucht, um ein Element zu finden, häufig an die Höhe des Baums gebunden. Es ist also von Vorteil, wenn der Baum möglichst niedrig ist. Je nach Baum kann es aber vorkommen, dass es einen langen Pfad gibt, der deutlich länger als die anderen im Baum ist. Sowas ist immer ungünstig, wenn man dann genau eines der Elemente sucht, das sich in diesem langen Pfad befindet. Hierfür hat balanciert man Bäume - d.h. man ordnet die Knoten so um, dass die Blätter des Baums immer in etwa auf der gleichen Höhe hängen. “Selbst-balancierend” heißt hier, dass das nicht ein Prozess ist, der ab und zu mal angestoßen wird, sondern dass die Operationen auf dem Baum (einfügen, Löschen etc.) so definiert sind, dass er sich beim Verändern entsprechend balanciert.

Beide Strukturen werden häufig in Datenbanken und vor allem in Dateisystemen verwendet, z. B. bei NTFS und ext4.

Datenstrukturdienstag: Der Splay-Tree. Ist von den Zugriffszeiten im Prinzip wie viele andere selbst-balancierte Bäume, aber mit einem Unterschied: Er schreibt auch bei Lesezugriff. So sortiert er häufig zugegriffene Nodes so um, dass sie schneller gefunden werden.

Bei zufälligem Zugriff performt er wie andere Bäume. Aber wenn im Zugriff ein Muster ist, kann seine Optimierung richtig zutrage kommen und wird ggf. schneller als O(log(n)).

Ich wollte diesen Baum mal in Rust implementieren, als Übungsaufgabe. Dann ist mir aufgefallen, dass der echt nicht so geil für alles ist, was mehr als einen Thread hat, da auch Leseoperationen schreibend zugreifen (naja, das war ja auch sein Vorteil). Vielleicht gibt’s da eine bessere Variante von, die dieses Problem nicht hat? Vielleicht eine, bei der jeder Thread seine Thread-Local-Kopie hat und nur die “richtigen” schreibenden Operationen synchronisiert werden? Wenn jemand eine Idee hat, her damit!

Wie viele Datenstrukturen ist er schon etwas älter und kommt aus 1985.

Datenstrukturdienstag: Heute keine “Datenstruktur”, eher ein Algorithmus. Aber das ist ja quasi beides das gleiche bzw nicht voneinander zu trennen.

FP-Growth (Frequent-Pattern) kommt zusammen mit dem FP-Tree. Der Algorithmus ist etwas komplizierter. Hier ist noch ein Artikel und ein Video dazu.

Was macht der? Das ist der Algorithmus hinter “Kunden, die X und Y kauften, kauften auch…”, also er findet oft zusammen auftretende Einträge. Das macht er sehr effizient, sodass man das auch auf großen Datenmengen (TM) laufen lassen kann.

Datenstrukturdienstag: Rot-Schwarz-Baum (oder RB-Tree).

Ist ein selbst-balancierender Suchbaum, der in den meisten Implementierungen einer Map bzw. eines Dictionaries verwendet wird. Beispielsweise ist std::map in den meisten Implementierungen intern ein RB-Tree. Aber auch B-Bäume und AVL-Bäume werden gern verwendet.