B+ puut ja LSM-puut ovat kaksi perustietorakennetta, kun puhumme rakennuspalikoista Tietokannat. B+-puita käytetään, kun tarvitsemme vähemmän haku- ja lisäysaikaa, ja toisaalta LSM-puita käytetään, kun meillä on kirjoitusintensiivisiä tietojoukkoja ja lukumäärät eivät ole niin korkeat.

Tämä artikkeli opettaa aiheesta Log Strukturoitu yhdistämispuu aka LSM-puu . LSM-puut ovat monien erittäin skaalautuvien NoSQL-hajautetun avainarvotyyppisten tietokantojen, kuten Amazonin DynamoDB, Cassandra ja ScyllaDB, taustalla oleva tietorakenne.

LSM-puut

Yksinkertainen LSM Trees -versio sisältää kaksi puumaista tietorakennetta:

• Muistettavissa ja pysyy täysin muistissa (oletetaan T0)
• Levylle tallennetut SStablet (oletetaan T1)

Yksinkertainen LSM-puu

Uudet tietueet lisätään muistiin tallennettavaan T0-komponenttiin. Jos lisäys saa T0-komponentin ylittämään tietyn kokokynnyksen, peräkkäinen merkintöjen segmentti poistetaan T0:sta ja yhdistetään levyllä olevaan T1:een.

LSM-työnkulku

LSM käyttää ensisijaisesti kolmea käsitettä luku- ja kirjoitustoimintojen optimointiin:

• Lajiteltu merkkijonotaulukko (SST-taulukot) : Tiedot lajitellaan lajiteltuun järjestykseen siten, että aina kun dataa luetaan, sen aikamonimutkaisuus on O( Log(N) ) pahimmassa tapauksessa, missä N on tietokantataulukon merkintöjen määrä.

  1. SSTable

• Muistettava :
  • Muistissa oleva rakenne
  • Tallentaa tiedot lajiteltuna
  • Toimii takaisinkirjoitusvälimuistina
  • Kun se on saavuttanut tietyn koon, sen tiedot huuhdellaan SST-taulukkona tietokantaan
  • Kuten, määrä SSTable kasvaa levyllä, ja jos jokin avain ei ole tietueissa
    • Kun luemme tätä avainta, meidän on luettava kaikki SST-taulukot, mikä lisää lukuajan monimutkaisuutta.
    • Tämän ongelman ratkaisemiseksi kuvaan tulee Bloom-suodatin.
    • Bloom-suodatin on tilaa säästävä tietorakenne, joka voi kertoa meille, jos avain puuttuu tietueistamme 99,9 prosentin tarkkuudella.
    • Tämän suodattimen käyttämiseksi voimme lisätä merkintöjä siihen, kun ne kirjoitetaan, ja tarkistaa avaimen lukupyyntöjen alussa, jotta voimme palvella pyyntöjä tehokkaammin, kun ne tulevat ensimmäiseksi.

Muistettava esitys

• Tiivistys :
  • Koska tallennamme tietoja SSTable-muodossa levylle, oletetaan, että niitä on N SSTable ja jokaisen pöydän koko on M
  • Sitten pahimmassa tapauksessa Lukea aika monimutkaisuus on O( N* loki(M) )
  • Joten kun SST-taulukkojen määrä kasvaa Lue Aika monimutkaisuus myös lisääntyy.
  • Lisäksi, kun vain huuhtelemme tietokannan SST-taulukoita, sama avain on läsnä useissa SST-taulukoissa
  • Tässä tulee tiivistimen käyttö
  • Compactor toimii taustalla, yhdistää SST-taulukot ja poistaa useita rivejä samalla ja lisää uuden avaimen uusimmilla tiedoilla ja tallentaa ne uuteen yhdistettyyn/tiivistettyyn SST-taulukkoon.

3.1. SSTables huuhdeltu levylle

3.6. Tiivistetty 2 SST-pöytää 1 SST-pöytään

Johtopäätös:

• Kirjoitukset tallennetaan muistipuuhun (Memtable). Myös mahdolliset tukitietorakenteet (bloom-suodattimet ja harvalukuindeksi) päivitetään tarvittaessa.
• Kun tämä puu tulee liian suureksi, se huuhdellaan levylle avaimet lajiteltuina.
• Kun lukema tulee, tarkistamme sen käyttämällä kukintasuodatinta. Jos Bloom-suodatin osoittaa, että arvoa ei ole, ilmoitamme asiakkaalle, että avainta ei löydy. Jos Bloom-suodatin tarkoittaa, että arvo on läsnä, aloitamme SSTable-tiedostojen iteroinnin uusimmasta vanhimpaan.
• LSM-ajan monimutkaisuus
  • Lukuaika: O(log(N)) missä N on levyllä olevien tietueiden lukumäärä
  • Kirjoitusaika: O(1) kuten se kirjoittaa muistiin
  • Poista aika: O(log(N)) missä N on levyllä olevien tietueiden lukumäärä
• LSM-puita voidaan muokata tehokkaammiksi tietorakenteiksi käyttämällä enemmän kuin kahta suodatinta. Jotkut niistä ovat bLSM, Diff-Index LSM.