B+ træer og LSM træer er to grundlæggende datastrukturer, når vi taler om byggestenene til Databaser. B+ Træer bruges når vi har brug for mindre søge- og indsættelsestid og på den anden side bruges LSM træer når vi har skrivetunge datasæt og læsninger ikke er så høje.

Denne artikel vil lære om Log struktureret flettetræ aka LSM træ . LSM-træer er datastrukturen, der ligger til grund for mange meget skalerbare NoSQL-distribuerede nøgleværdi-databaser, såsom Amazons DynamoDB, Cassandra og ScyllaDB.

LSM træer

En simpel version af LSM Trees omfatter 2 niveauer af trælignende datastruktur:

• Huskes og ligger fuldstændigt i hukommelsen (lad os sige T0)
• SStables gemt på disk (Lad os sige T1)

Simpelt LSM-træ

Nye poster indsættes i den memtable T0-komponent. Hvis indsættelsen får T0-komponenten til at overskride en vis størrelsestærskel, fjernes et sammenhængende segment af indtastninger fra T0 og flettes ind i T1 på disken.

LSM arbejdsgang

LSM bruger primært 3 koncepter til at optimere læse- og skriveoperationer:

• Sorteret strengtabel (SSTables) : Data sorteres i sorteret rækkefølge, så hver gang dataene læses, vil deres tidskompleksitet være O( Log(N) ) i værste fald, hvor N er antallet af poster i en databasetabel.

  1. SSTabel

• Huskes :
  • En struktur i hukommelsen
  • Gemmer data på en sorteret måde
  • Fungerer som en tilbageskrivningscache
  • Efter at have nået en vis størrelse, tømmes dens data som en SSTable til database
  • Som, antallet af SSTable stigning i Disk, og hvis nogle nøgle ikke er til stede i posterne
    • Mens vi læser den nøgle, skal vi læse alle SSTables, hvilket øger læsetidskompleksiteten.
    • For at overvinde dette problem kommer Bloom-filteret ind i billedet.
    • Bloom-filter er en pladseffektiv datastruktur, der kan fortælle os, om nøglen mangler i vores Records med en nøjagtighedsgrad på 99,9 %.
    • For at bruge dette filter kan vi tilføje vores poster til det, når de er skrevet, og kontrollere nøglen i begyndelsen af ​​læseanmodninger for at betjene anmodninger mere effektivt, når de kommer på førstepladsen.

Mindeværdig repræsentation

• Komprimering :
  • Da vi gemmer data som SSTable på disken, lad os sige, at der er det N SSTable og hvert bords størrelse er M
  • Så i værste fald Læs tidskompleksitet er O( N* Log(M) )
  • Så efterhånden som antallet af SSTables øges Læs Tidskompleksitet stiger også.
  • Når vi bare tømmer SSTablerne i databasen, er den samme nøgle til stede i flere SSTables
  • Her kommer brugen af ​​en Compactor
  • Compactor kører i baggrunden, fusionerer SSTables og fjerner flere rækker med det samme og tilføjer den nye nøgle med de seneste data og gemmer dem i en ny flettet/komprimeret SSTable.

3.1. SSTables tømmes til disk

3.6. Kompaktor komprimeret 2 SSTables til 1 SSTable

Konklusion:

• Skrivninger gemmes i et træ i hukommelsen (Memtable). Eventuelle understøttende datastrukturer (opblomstringsfiltre og sparsomt indeks) opdateres også om nødvendigt.
• Når dette træ bliver for stort, skylles det til disk med nøglerne i sorteret rækkefølge.
• Når der kommer en læsning, tjekker vi den ved hjælp af bloomfilteret. Hvis bloom-filteret indikerer, at værdien ikke er til stede, fortæller vi klienten, at nøglen ikke kunne findes. Hvis bloom-filteret betyder, at værdien er til stede, begynder vi at iterere SSTables fra nyeste til ældste.
• LSM tidskompleksiteter
  • Læsetid: O(log(N)) hvor N er antallet af poster på disken
  • Skrivetid: O(1) som den skriver i hukommelsen
  • Slet tid: O(log(N)) hvor N er antallet af poster på disken
• LSM-træer kan ændres til mere effektive datastrukturer ved hjælp af mere end 2 filtre. Nogle af dem er bLSM, Diff-Index LSM.