B+ Bomen En LSM-bomen zijn twee fundamentele datastructuren als we het hebben over de bouwstenen van Databases. B+ Trees worden gebruikt wanneer we minder zoek- en invoegtijd nodig hebben en aan de andere kant worden LSM-bomen gebruikt wanneer we schrijfintensieve datasets hebben en de leesbewerkingen niet zo hoog zijn.

Dit artikel zal meer leren Gestructureerde samenvoegingsboom loggen oftewel LSM-boom . LSM Trees vormen de datastructuur die ten grondslag ligt aan veel zeer schaalbare, door NoSQL gedistribueerde databases met sleutelwaarden, zoals Amazon's DynamoDB, Cassandra en ScyllaDB.

LSM-bomen

Een eenvoudige versie van LSM Trees bestaat uit 2 niveaus van boomachtige datastructuur:

• Memtabel en bevindt zich volledig in het geheugen (laten we zeggen T0)
• SStables opgeslagen op schijf (laten we zeggen T1)

Eenvoudige LSM-boom

Nieuwe records worden ingevoegd in de geheugentabel T0-component. Als het invoegen ervoor zorgt dat de TO-component een bepaalde groottedrempel overschrijdt, wordt een aaneengesloten segment van invoeren verwijderd uit TO en samengevoegd met T1 op schijf.

LSM-workflow

LSM gebruikt voornamelijk 3 concepten om lees- en schrijfbewerkingen te optimaliseren:

• Gesorteerde tekenreekstabel (SSTables) : Gegevens worden in gesorteerde volgorde gesorteerd, zodat wanneer de gegevens worden gelezen, de tijdscomplexiteit in het ergste geval O( Log(N) ) zal zijn, waarbij N het aantal vermeldingen in een databasetabel is.

  1. SSTabel

• Memtabel :
  • Een in-memory-structuur
  • Slaat gegevens op een gesorteerde manier op
  • Fungeert als een terugschrijfcache
  • Nadat een bepaalde grootte is bereikt, worden de gegevens ervan als SSTable naar Database gespoeld
  • Als het aantal SSTables op de schijf toeneemt, en als een sleutel niet aanwezig is in de records
    • Tijdens het lezen van die sleutel moeten we alle SSTables lezen, wat de complexiteit van de leestijd vergroot.
    • Om dit probleem te ondervangen komt het Bloom-filter in beeld.
    • Bloom-filter is een ruimtebesparende gegevensstructuur die ons kan vertellen of de sleutel ontbreekt in onze administratie met een nauwkeurigheidspercentage van 99,9%.
    • Om dit filter te gebruiken, kunnen we onze vermeldingen eraan toevoegen wanneer ze worden geschreven, en de sleutel aan het begin van leesverzoeken controleren om verzoeken efficiënter te kunnen afhandelen wanneer ze op de eerste plaats komen.

Memtabel representatie

• Verdichting :
  • Omdat we gegevens als SSTable op de schijf opslaan, laten we zeggen dat dat zo is N SSTable en de grootte van elke tafel is M
  • Dan in het slechtste geval Lezen tijdscomplexiteit is O( N* Logboek(M) )
  • Dus naarmate het aantal SSTables toeneemt, wordt de Lees Tijdcomplexiteit neemt ook toe.
  • Wanneer we alleen de SSTables in de database leegmaken, is dezelfde sleutel aanwezig in meerdere SSTables
  • Hier komt het gebruik van een Compactor
  • Compactor draait op de achtergrond, voegt SSTables samen en verwijdert meerdere rijen met dezelfde en voegt de nieuwe sleutel toe met de nieuwste gegevens, en slaat deze op in een nieuwe samengevoegde/gecompacteerde SSTable.

3.1. SSTables naar schijf gespoeld

3.6. Compactor comprimeerde 2 SSTables tot 1 SSTable

Conclusie:

• Schrijfbewerkingen worden opgeslagen in een in-memory boom (Memtable). Eventuele ondersteunende datastructuren (bloomfilters en sparse index) worden indien nodig ook bijgewerkt.
• Wanneer deze boom te groot wordt, wordt deze in gesorteerde volgorde met de sleutels naar schijf gespoeld.
• Wanneer er een waarde binnenkomt, controleren we deze met behulp van het bloeifilter. Als het bloeifilter aangeeft dat de waarde niet aanwezig is, vertellen we de klant dat de sleutel niet kan worden gevonden. Als het bloeifilter betekent dat de waarde aanwezig is, beginnen we SSTables te itereren van de nieuwste naar de oudste.
• LSM-tijdcomplexiteit
  • Leestijd: O(log(N)) waarbij N het aantal records op de schijf is
  • Schrijftijd: O(1) zoals het in het geheugen schrijft
  • Tijd verwijderen: O(log(N)) waarbij N het aantal records op de schijf is
• LSM Trees kunnen worden aangepast aan efficiëntere datastructuren met behulp van meer dan 2 filters. Sommigen van hen zijn bLSM, Diff-Index LSM.