B+ trær og LSM trær er to grunnleggende datastrukturer når vi snakker om byggesteinene til Databaser. B+-trær brukes når vi trenger mindre søke- og innsettingstid og på den annen side brukes LSM-trær når vi har skriveintensive datasett og lesningene ikke er så høye.

Denne artikkelen vil lære om Loggstrukturert sammenslåingstre aka LSM-tre . LSM-trær er datastrukturen som ligger til grunn for mange svært skalerbare NoSQL-distribuerte nøkkelverdi-databaser som Amazons DynamoDB, Cassandra og ScyllaDB.

LSM trær

En enkel versjon av LSM Trees består av 2 nivåer med trelignende datastruktur:

• Memtable og ligger fullstendig i minnet (la oss si T0)
• SStables lagret på disk (La oss si T1)

Enkelt LSM-tre

Nye poster settes inn i den memtable T0-komponenten. Hvis innsettingen fører til at T0-komponenten overskrider en viss størrelsesterskel, fjernes et sammenhengende segment av oppføringer fra T0 og slås sammen til T1 på disken.

LSM arbeidsflyt

LSM bruker primært 3 konsepter for å optimalisere lese- og skriveoperasjoner:

• Sortert strengtabell (SSTables) : Data sorteres i sortert rekkefølge, slik at hver gang dataene leses vil kompleksiteten i tid være O( Log(N) ) i verste fall, der N er antall oppføringer i en databasetabell.

  1. SSTable

• Memtable :
  • En struktur i minnet
  • Lagrer data på en sortert måte
  • Fungerer som en tilbakeskrivningsbuffer
  • Etter å ha nådd en viss størrelse, tømmes dataene som en SSTable til database
  • Som, antall SSTable økning i Disk, og hvis noen nøkkel ikke er til stede i postene
    • Mens vi leser den nøkkelen, må vi lese alle SSTablene, noe som øker lesetidskompleksiteten.
    • For å overvinne dette problemet kommer Bloom-filteret inn i bildet.
    • Bloom-filter er en plasseffektiv datastruktur som kan fortelle oss om nøkkelen mangler i postene våre med en nøyaktighetsgrad på 99,9 %.
    • For å bruke dette filteret kan vi legge til oppføringene våre i det når de er skrevet, og sjekke nøkkelen i begynnelsen av leseforespørsler for å betjene forespørsler mer effektivt når de kommer på første plass.

Memtable representasjon

• Komprimering :
  • Ettersom vi lagrer data som SSTable på disken, la oss si at det er det N SSTable og hvert bords størrelse er M
  • Så i verste fall Lese tidskompleksitet er O( N* logg(M) )
  • Så, ettersom antall SSTables øker Les Tidskompleksitet øker også.
  • Dessuten, når vi bare tømmer SSTables i databasen, er den samme nøkkelen til stede i flere SSTables
  • Her kommer bruken av en Compactor
  • Compactor kjører i bakgrunnen, slår sammen SSTables og fjerner flere rader med det samme og legger til den nye nøkkelen med de nyeste dataene, og lagrer dem i en ny sammenslått/komprimert SSTable.

3.1. SSTables tømt til disk

3.6. Kompaktor komprimert 2 SSTables til 1 SSTable

Konklusjon:

• Skrivinger lagres i et tre i minnet (Memtable). Eventuelle støttedatastrukturer (oppblomstringsfiltre og sparsom indeks) oppdateres også om nødvendig.
• Når dette treet blir for stort, skylles det til disk med nøklene i sortert rekkefølge.
• Når en avlesning kommer inn, sjekker vi den ved hjelp av blomstringsfilteret. Hvis bloom-filteret indikerer at verdien ikke er til stede, forteller vi klienten at nøkkelen ikke ble funnet. Hvis bloom-filteret betyr at verdien er tilstede, begynner vi å iterere SSTables fra nyeste til eldste.
• LSM tidskompleksiteter
  • Lesetid: O(log(N)) hvor N er antall poster på disken
  • Skrivetid: O(1) som den skriver i minnet
  • Slett tid: O(log(N)) hvor N er antall poster på disken
• LSM-trær kan endres til mer effektive datastrukturer ved å bruke mer enn 2 filtre. Noen av dem er bLSM, Diff-Index LSM.