B+ Bäume Und LSM-Bäume sind zwei grundlegende Datenstrukturen, wenn wir über die Bausteine ​​von sprechen Datenbanken. B+-Bäume werden verwendet, wenn wir weniger Such- und Einfügezeit benötigen, und andererseits werden LSM-Bäume verwendet, wenn wir schreibintensive Datensätze haben und die Lesevorgänge nicht so hoch sind.

In diesem Artikel erfahren Sie mehr darüber Strukturierter Zusammenführungsbaum protokollieren aka LSM-Baum . LSM-Bäume sind die Datenstruktur, die vielen hoch skalierbaren NoSQL-Datenbanken mit verteilten Schlüsselwerten wie DynamoDB, Cassandra und ScyllaDB von Amazon zugrunde liegt.

LSM-Bäume

Eine einfache Version von LSM Trees umfasst zwei Ebenen einer baumartigen Datenstruktur:

• Memtable und liegt vollständig im Speicher (sagen wir T0)
• Auf der Festplatte gespeicherte SStables (sagen wir T1)

Einfacher LSM-Baum

Neue Datensätze werden in die Memtable-T0-Komponente eingefügt. Wenn das Einfügen dazu führt, dass die T0-Komponente einen bestimmten Größenschwellenwert überschreitet, wird ein zusammenhängendes Segment von Einträgen aus T0 entfernt und in T1 auf der Festplatte zusammengeführt.

LSM-Workflow

LSM verwendet hauptsächlich drei Konzepte, um Lese- und Schreibvorgänge zu optimieren:

• Sortierte String-Tabelle (SSTables) : Daten werden in sortierter Reihenfolge sortiert, sodass ihre Zeitkomplexität beim Lesen der Daten im schlimmsten Fall O(Log(N)) beträgt, wobei N die Anzahl der Einträge in einer Datenbanktabelle ist.

  1. SSTable

• Merkbar :
  • Eine In-Memory-Struktur
  • Speichert Daten sortiert
  • Fungiert als Write-Back-Cache
  • Nach Erreichen einer bestimmten Größe werden die Daten als SSTable in die Datenbank geschrieben
  • B. wenn die Anzahl der SSTables auf der Festplatte zunimmt und wenn ein Schlüssel in den Datensätzen nicht vorhanden ist
    • Beim Lesen dieses Schlüssels müssen wir alle SSTables lesen, was die Komplexität der Lesezeit erhöht.
    • Um dieses Problem zu lösen, kommt der Bloom-Filter ins Spiel.
    • Der Bloom-Filter ist eine platzsparende Datenstruktur, die uns mit einer Genauigkeit von 99,9 % sagen kann, ob der Schlüssel in unseren Datensätzen fehlt.
    • Um diesen Filter zu verwenden, können wir unsere Einträge hinzufügen, wenn sie geschrieben werden, und den Schlüssel am Anfang von Leseanfragen überprüfen, um Anfragen effizienter zu bedienen, wenn sie an erster Stelle stehen.

Memtable-Darstellung

• Verdichtung :
  • Da wir Daten als SSTable auf der Festplatte speichern, nehmen wir an, dass es solche gibt N SSTable und die Größe jeder Tabelle ist M
  • Dann der schlimmste Fall Lesen Zeitkomplexität ist O( N* Log(M) )
  • Wenn also die Anzahl der SSTables zunimmt Lesen Sie Zeitkomplexität nimmt auch zu.
  • Auch wenn wir nur die SSTables in der Datenbank leeren, ist derselbe Schlüssel in mehreren SSTables vorhanden
  • Hier kommt der Einsatz eines Compactors zum Einsatz
  • Compactor läuft im Hintergrund, führt SSTables zusammen und entfernt mehrere Zeilen mit denselben, fügt den neuen Schlüssel mit den neuesten Daten hinzu und speichert sie in einer neuen zusammengeführten/komprimierten SSTable.

3.1. SSTables werden auf die Festplatte geleert

3.6. Compactor verdichtete 2 SSTables zu 1 SSTable

Abschluss:

• Schreibvorgänge werden in einem In-Memory-Baum (Memtable) gespeichert. Bei Bedarf werden auch alle unterstützenden Datenstrukturen (Bloom-Filter und Sparse-Index) aktualisiert.
• Wenn dieser Baum zu groß wird, wird er mit den Schlüsseln in sortierter Reihenfolge auf die Festplatte geschrieben.
• Wenn ein Messwert eingeht, überprüfen wir ihn mithilfe des Bloom-Filters. Wenn der Bloom-Filter anzeigt, dass der Wert nicht vorhanden ist, teilen wir dem Client mit, dass der Schlüssel nicht gefunden werden konnte. Wenn der Bloom-Filter bedeutet, dass der Wert vorhanden ist, beginnen wir mit der Iteration der SSTables vom neuesten zum ältesten.
• LSM-Zeitkomplexität
  • Lesezeit: O(log(N)) Dabei ist N die Anzahl der Datensätze auf der Festplatte
  • Schreibzeit: O(1) wie es im Speicher schreibt
  • Uhrzeit löschen: O(log(N)) Dabei ist N die Anzahl der Datensätze auf der Festplatte
• LSM-Bäume können mithilfe von mehr als zwei Filtern in effizientere Datenstrukturen umgewandelt werden. Einige davon sind bLSM, Diff-Index LSM.