B+ medžiai ir LSM medžiai yra dvi pagrindinės duomenų struktūros, kai kalbame apie kūrimo blokus Duomenų bazės. B+ medžiai naudojami, kai mums reikia mažiau paieškos ir įterpimo laiko, o kita vertus, LSM medžiai naudojami, kai turime daug rašymo reikalaujančių duomenų rinkinių, o skaitymų skaičius nėra toks didelis.

Šis straipsnis mokys apie Rąstinis struktūrinis sujungimo medis dar žinomas LSM medis . LSM medžiai yra duomenų struktūra, kuri yra daugelio labai keičiamo dydžio NoSQL paskirstytų raktų verčių tipo duomenų bazių, tokių kaip Amazon DynamoDB, Cassandra ir ScyllaDB, pagrindas.

LSM medžiai

Paprastą LSM medžių versiją sudaro 2 į medį panašios duomenų struktūros lygiai:

• Įsiminė ir visiškai išlieka atmintyje (tarkime, T0)
• SStables, saugomos diske (tarkime, T1)

Paprastas LSM medis

Nauji įrašai įterpiami į įsimenamąjį T0 komponentą. Jei dėl įterpimo T0 komponentas viršija tam tikrą dydžio slenkstį, gretimas įrašų segmentas pašalinamas iš T0 ir sujungiamas į T1 diske.

LSM darbo eiga

LSM pirmiausia naudoja 3 koncepcijas, skirtas optimizuoti skaitymo ir rašymo operacijas:

• Rūšiuotų eilučių lentelė (SST lentelės) : Duomenys rūšiuojami tokia tvarka, kad kiekvieną kartą nuskaitant duomenis jų sudėtingumas būtų O(Log(N)) blogiausiu atveju, kur N yra duomenų bazės lentelės įrašų skaičius.

  1. SSTtable

• Įsiminė :
  • Struktūra atmintyje
  • Saugo duomenis rūšiuotu būdu
  • Veikia kaip atrašymo talpykla
  • Pasiekus tam tikrą dydį, jo duomenys išplaunami kaip SSTable į duomenų bazę
  • Kaip, SSTable skaičius didėja diske, ir jei kai kurių raktų nėra įrašuose
    • Skaitydami šį raktą turime perskaityti visas SST lenteles, o tai padidina skaitymo laiko sudėtingumą.
    • Norėdami išspręsti šią problemą, į paveikslėlį įtraukiamas „Bloom“ filtras.
    • „Bloom“ filtras yra erdvę taupanti duomenų struktūra, galinti 99,9% tikslumu mums pasakyti, ar įrašuose trūksta rakto.
    • Norėdami naudoti šį filtrą, galime pridėti savo įrašus, kai jie yra parašyti, ir patikrinti raktą skaitymo užklausų pradžioje, kad užklausos būtų veiksmingesnės, kai jos pateikiamos pirmoje vietoje.

Įsimintinas vaizdavimas

• Sutankinimas :
  • Kadangi duomenis saugome kaip SSTable diske, tarkime, kad yra N SSTable ir kiekvienos lentelės dydis yra M
  • Tada blogiausiu atveju Skaityti laiko sudėtingumas yra O ( N* žurnalas (M) )
  • Taigi, didėjant SST lentelių skaičiui Skaitykite Laiko sudėtingumą taip pat didėja.
  • Be to, kai tik nuplauname SST lenteles duomenų bazėje, tas pats raktas yra keliose SST lentelėse
  • Čia ateina kompaktoriaus naudojimas
  • Kompaktorius veikia fone, sujungia SST lenteles ir pašalina kelias eilutes su tomis pačiomis, prideda naują raktą su naujausiais duomenimis ir išsaugo juos naujoje sujungtoje / suglaudintoje SST lentelėje.

3.1. SSTtables išplautos į diską

3.6. Sutankintas 2 SST lenteles į 1 SST lentelę

Išvada:

• Įrašai saugomi atminties medyje (Memtable). Prireikus atnaujinamos ir visos pagalbinės duomenų struktūros (žydėjimo filtrai ir negausus indeksas).
• Kai šis medis tampa per didelis, jis nuplaunamas į diską su raktais surūšiuota tvarka.
• Kai gaunamas skaitymas, patikriname jį naudodami žydėjimo filtrą. Jei žydėjimo filtras rodo, kad vertės nėra, mes pranešame klientui, kad rakto nepavyko rasti. Jei žydėjimo filtras reiškia, kad reikšmė yra, pradedame kartoti SSTables nuo naujausio iki seniausio.
• LSM laiko sudėtingumas
  • Skaitymo laikas: O(log(N)) kur N yra įrašų skaičius diske
  • Rašymo laikas: O(1) kaip rašo atmintyje
  • Ištrynimo laikas: O(log(N)) kur N yra įrašų skaičius diske
• LSM medžius galima modifikuoti į efektyvesnes duomenų struktūras naudojant daugiau nei 2 filtrus. Kai kurie iš jų yra bLSM, Diff-Index LSM.