B+ Koki un LSM koki ir divas pamata datu struktūras, kad mēs runājam par elementiem Datu bāzes. B+ koki tiek izmantoti, ja mums ir nepieciešams mazāk meklēšanas un ievietošanas laika, un, no otras puses, LSM koki tiek izmantoti, ja mums ir intensīvas rakstīšanas datu kopas un nolasījumu skaits nav tik augsts.

Šis raksts mācīs par Baļķu strukturēts sapludināšanas koks aka LSM koks . LSM koki ir datu struktūra, kas ir pamatā daudzām ļoti mērogojamām NoSQL izplatītajām atslēgu vērtību tipa datu bāzēm, piemēram, Amazon DynamoDB, Cassandra un ScyllaDB.

LSM koki

Vienkāršā LSM Trees versija ietver divus koka veida datu struktūras līmeņus:

• Iegaumējams un pilnībā saglabājas atmiņā (teiksim, T0)
• SStables, kas glabājas diskā (pieņemsim, ka T1)

Vienkāršs LSM koks

Jauni ieraksti tiek ievietoti iegaumējamajā T0 komponentā. Ja ievietošanas rezultātā T0 komponents pārsniedz noteiktu lieluma slieksni, blakus esošais ierakstu segments tiek noņemts no T0 un diskā tiek apvienots ar T1.

LSM darbplūsma

LSM galvenokārt izmanto 3 koncepcijas, lai optimizētu lasīšanas un rakstīšanas darbības:

• Kārtoto virkņu tabula (SSTtables) : Dati tiek kārtoti sakārtotā secībā, lai ikreiz, kad dati tiek nolasīti, to laika sarežģītība sliktākajā gadījumā būtu O( Log(N) ), kur N ir ierakstu skaits datu bāzes tabulā.

  1. SSTable

• Iegaumējams :
  • Struktūra atmiņā
  • Saglabā datus sakārtotā veidā
  • Darbojas kā atpakaļrakstīšanas kešatmiņa
  • Pēc noteikta lieluma sasniegšanas tā dati tiek izskaloti kā SSTable datu bāzē
  • Kā, SSTable skaits palielinās diskā, un, ja kāda atslēga nav klāt ierakstos
    • Lasot šo atslēgu, mums ir jāizlasa visi SSTables, kas palielina lasīšanas laika sarežģītību.
    • Lai novērstu šo problēmu, attēlā tiek izmantots Bloom filtrs.
    • Bloom filtrs ir kosmosa ziņā efektīva datu struktūra, kas var mums paziņot, ja mūsu ierakstos trūkst atslēgas, ar precizitātes līmeni 99,9%.
    • Lai izmantotu šo filtru, mēs varam tam pievienot savus ierakstus, kad tie ir uzrakstīti, un pārbaudīt atslēgu lasīšanas pieprasījumu sākumā, lai efektīvāk apkalpotu pieprasījumus, kad tie nonāk pirmajā vietā.

Neaizmirstams attēlojums

• Blīvēšana :
  • Tā kā mēs diskā glabājam datus kā SSTable, pieņemsim, ka tādi ir N SSTable un katra galda izmērs ir M
  • Tad sliktākajā gadījumā Lasīt laika sarežģītība ir O( N* žurnāls(M) )
  • Tātad, palielinoties SSTable skaitam, Lasiet laika sarežģītību arī palielinās.
  • Turklāt, kad mēs tikai izskalojam SST tabulus datu bāzē, viena un tā pati atslēga atrodas vairākos SST tabulos.
  • Šeit tiek izmantots blīvētājs
  • Compactor darbojas fonā, apvieno SSTables un noņem vairākas rindas ar to pašu, pievieno jauno atslēgu ar jaunākajiem datiem un saglabā tos jaunā sapludinātā/saspiestā SSTable.

3.1. SSTables tika izskalotas diskā

3.6. Blīvētājs saspiests 2 SSTtables uz 1 SSTtable

Secinājums:

• Raksti tiek glabāti atmiņas kokā (Memtable). Ja nepieciešams, tiek atjauninātas arī visas atbalsta datu struktūras (ziedēšanas filtri un rets indekss).
• Kad šis koks kļūst pārāk liels, tas tiek izskalots diskā ar taustiņiem sakārtotā secībā.
• Kad tiek saņemts nolasījums, mēs to pārbaudām, izmantojot ziedēšanas filtru. Ja ziedēšanas filtrs norāda, ka vērtības nav, mēs paziņojam klientam, ka atslēgu nevarēja atrast. Ja ziedēšanas filtrs nozīmē, ka vērtība ir klāt, mēs sākam atkārtot SSTables no jaunākā uz vecāko.
• LSM laika sarežģītības
  • Lasīšanas laiks: O(log(N)) kur N ir ierakstu skaits diskā
  • Rakstīšanas laiks: O(1) kā raksta atmiņā
  • Dzēšanas laiks: O(log(N)) kur N ir ierakstu skaits diskā
• LSM Trees var pārveidot, lai iegūtu efektīvākas datu struktūras, izmantojot vairāk nekā 2 filtrus. Daži no tiem ir bLSM, Diff-Index LSM.