B+ Träd och LSM Träd är två grundläggande datastrukturer när vi talar om byggstenarna i Databaser. B+-träd används när vi behöver mindre sök- och infogningstid och å andra sidan används LSM-träd när vi har skrivintensiva datamängder och läsningarna inte är så höga.

Denna artikel kommer att lära ut om Loggstrukturerat sammanfogningsträd aka LSM-träd . LSM-träd är datastrukturen som ligger till grund för många mycket skalbara NoSQL-distribuerade nyckel-värdesdatabaser som Amazons DynamoDB, Cassandra och ScyllaDB.

LSM Träd

En enkel version av LSM Trees består av två nivåer av trädliknande datastruktur:

• Minnesbar och finns helt i minnet (låt oss säga T0)
• SStables lagrade på disk (låt oss säga T1)

Enkelt LSM-träd

Nya poster infogas i den memtable T0-komponenten. Om infogningen gör att T0-komponenten överskrider en viss storlekströskel, tas ett sammanhängande segment av poster bort från T0 och slås samman till T1 på disken.

LSM arbetsflöde

LSM använder i första hand 3 koncept för att optimera läs- och skrivoperationer:

• Sorterad strängtabell (SSTables) : Data sorteras i sorterad ordning så att närhelst data läses kommer dess tidskomplexitet att vara O( Log(N) ) i värsta fall, där N är antalet poster i en databastabell.

  1. SSTable

• Minnesbar :
  • En struktur i minnet
  • Lagrar data på ett sorterat sätt
  • Fungerar som en återskrivningscache
  • Efter att ha nått en viss storlek rensas dess data som en SSTable to Database
  • Som, antalet SSTable ökar på disk, och om någon nyckel inte finns i posterna
    • När vi läser den nyckeln måste vi läsa alla SSTables, vilket ökar lästidens komplexitet.
    • För att övervinna detta problem kommer Bloom-filtret in i bilden.
    • Bloom-filter är en utrymmeseffektiv datastruktur som kan tala om för oss om nyckeln saknas i våra register med en noggrannhetsgrad på 99,9 %.
    • För att använda det här filtret kan vi lägga till våra poster i det när de skrivs, och kontrollera nyckeln i början av läsbegäranden för att betjäna förfrågningar mer effektivt när de kommer på första plats.

Minnesbar representation

• Packning :
  • Eftersom vi lagrar data som SSTable på disken, låt oss säga att det finns N SSTable och varje bords storlek är M
  • Då i värsta fall Läsa tidskomplexitet är O( N* Log(M) )
  • Så när antalet SSTables ökar Läs Tidskomplexitet ökar också.
  • Dessutom, när vi bara rensar SSTables i databasen, är samma nyckel närvarande i flera SSTables
  • Här kommer användningen av en Compactor
  • Compactor körs i bakgrunden, slår samman SSTables och tar bort flera rader med samma och lägger till den nya nyckeln med de senaste data, och lagrar dem i en ny sammanfogad/komprimerad SSTable.

3.1. SSTables spolade till disk

3.6. Kompaktor komprimerad 2 SSTables till 1 SSTable

Slutsats:

• Skrivningar lagras i ett träd i minnet (Memtable). Eventuella stödjande datastrukturer (bloomfilter och sparsamt index) uppdateras också vid behov.
• När detta träd blir för stort spolas det till disk med nycklarna i sorterad ordning.
• När en läsning kommer in kontrollerar vi den med hjälp av blomfiltret. Om bloom-filtret indikerar att värdet inte finns så berättar vi för klienten att nyckeln inte kunde hittas. Om bloom-filtret betyder att värdet finns så börjar vi iterera SSTables från nyaste till äldsta.
• LSM tidskomplexitet
  • Lästid: O(log(N)) där N är antalet poster på disken
  • Skrivtid: O(1) som det skriver i minnet
  • Ta bort tid: O(log(N)) där N är antalet poster på disken
• LSM-träd kan modifieras till mer effektiva datastrukturer med hjälp av fler än 2 filter. Några av dem är bLSM, Diff-Index LSM.