Build Your Own Database. Am Ende steht ein LSM-Tree!
Posts mit Tag "tree"
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.
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: 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:
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: 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: Der Prefix-Tree bzw. “Trie”.
Grundidee: Ein Baum, bei dem jeder Knoten ein Buchstabe ist. Will man einen String ablegen, “geht” bzw. erstellt man den entsprechenden Pfad, der zu dem String gehört. Man muss den Key deshalb nicht separat abspeichern. Der Pfad zum Wert ist der Key. Die Menge der Keys ist dadurch die Menge der Pfade, die in einem Blatt enden.
Neulich habe ich hiermit ein bisschen geliebäugelt, um es ggf. als optimierte Variante anstelle einer Hashmap zu verwenden. Die Keys, die ich in die Map gesteckt habe, waren alle sehr ähnliche Strings. Vor allem waren es Strings, die semantisch mehr miteinander zu tun hatten, je gleicher der Prefix ist. Das hätte vor allem die Lookup-Zeiten aufgrund von CPU-Caches reduzieren können.
Bevor ich ausprobiert hab, ob es sich lohnt, hab ich natĂĽrlich gegooglet. Wichtige Erkenntnisse dabei haben dieser und dieser post geliefert. tl;dr: Eine Standard-Hashmap (z. B. aus Java) ist ziemlich optimiert und ein Prefix-Tree lohnt sich meistens eher nicht. Manche sehen das auch als Contest an, die schnellste Hashtable zu schreiben.
Datenstrukturdienstag: Diese Woche keine probabilistische Datenstruktur. Stattdessen etwas eher klassischeres: Merkle-Tree.
Grundidee: Man hat Daten(-Blöcke), welche man hasht. Diese Hashes hasht man dann in Zweierpaaren zu einem neuen Hash. Das macht man so lange, bis man nur noch einen Hash übrig hat, der implizit einen Hash über alle Datenblöcke repräsentiert. Ein Knoten in dem Baum ist dabei ein Hash, die Kind-Zweige jeweils die Vorgänger-Hashes. Wer alle Datenblöcke vor sich liegen hat, kann den Merkle-Tree berechnen. Ist ein Datenblock fehlerhaft, stimmt am Ende der Root-Hash nicht.
Das Konzept kommt ursprünglich aus 1979 von Ralph Merkle. Eine der bekanntesten Anwendungen heutzutage ist die Bitcoin-Blockchain. Dort wird ein Merkle-Tree verwendet, um einen Hash über die Transaktionen innerhalb eines Blocks zu berechnen. Die Wurzel dieses Merkle-Trees ist bei Bitcoin dann Teil von dem, was als Grundlage für den SHA-1-Hash verwendet wird, der “gemined” wird. Ursprünglich erfunden wurde der Merkle-Tree, um P2P-Dateiaustausch zu vereinfachen. Hier ist ein Artikel dazu.