B+ Alberi E Alberi LSM sono due strutture dati di base quando parliamo degli elementi costitutivi di Banche dati. Gli alberi B+ vengono utilizzati quando abbiamo bisogno di meno tempo di ricerca e inserimento e, d'altro canto, gli alberi LSM vengono utilizzati quando abbiamo set di dati ad alta intensità di scrittura e le letture non sono così elevate.

Questo articolo insegnerà Albero di unione strutturato del registro ovvero Albero LSM . Gli alberi LSM sono la struttura dati alla base di molti database di tipo chiave-valore distribuiti NoSQL altamente scalabili come DynamoDB, Cassandra e ScyllaDB di Amazon.

Alberi LSM

Una versione semplice di LSM Trees comprende 2 livelli di struttura dati ad albero:

• Memtable e risiede completamente in memoria (diciamo T0)
• SStables archiviate nel disco (diciamo T1)

Albero LSM semplice

I nuovi record vengono inseriti nel componente T0 memorizzabile. Se l'inserimento fa sì che il componente T0 superi una determinata soglia di dimensione, un segmento contiguo di voci viene rimosso da T0 e unito a T1 sul disco.

Flusso di lavoro LSM

LSM utilizza principalmente 3 concetti per ottimizzare le operazioni di lettura e scrittura:

• Tabella di stringhe ordinate (SSTables) : I dati vengono ordinati in modo tale che ogni volta che i dati vengono letti la loro complessità temporale sarà O( Log(N) ) nel caso peggiore, dove N è il numero di voci in una tabella di database.

  1. Tabella SST

• Memorabile :
  • Una struttura in memoria
  • Memorizza i dati in modo ordinato
  • Funziona come una cache di write-back
  • Dopo aver raggiunto una certa dimensione, i suoi dati vengono scaricati come SSTable nel database
  • Come, il numero di SSTable aumenta nel disco e se qualche chiave non è presente nei record
    • Durante la lettura di quella chiave, dobbiamo leggere tutte le SSTable, il che aumenta la complessità del tempo di lettura.
    • Per superare questo problema, entra in gioco il filtro Bloom.
    • Il filtro Bloom è una struttura dati efficiente in termini di spazio che può dirci se manca la chiave nei nostri record con un tasso di precisione del 99,9%.
    • Per utilizzare questo filtro, possiamo aggiungervi le nostre voci quando vengono scritte e controllare la chiave all'inizio delle richieste di lettura per servire le richieste in modo più efficiente quando arrivano al primo posto.

Rappresentazione memorizzabile

• Compattazione :
  • Poiché stiamo memorizzando i dati come SSTable nel disco, diciamo che ci sono N SSTable e la dimensione di ogni tabella è M
  • Poi il caso peggiore Leggere la complessità temporale è O( N* Ceppo(M) )
  • Pertanto, man mano che il numero di SSTable aumenta, il file Leggi Complessità temporale aumenta anche.
  • Inoltre, quando stiamo semplicemente svuotando le SSTable nel database, la stessa chiave è presente in più SSTable
  • Ecco l'uso di un compattatore
  • Compactor viene eseguito in background, unisce SSTable e rimuove più righe con le stesse, aggiunge la nuova chiave con i dati più recenti e li memorizza in una nuova SSTable unita/compatta.

3.1. SSTables scaricate su disco

3.6. Il compattatore ha compattato 2 SSTable in 1 SSTable

Conclusione:

• Le scritture vengono archiviate in un albero in memoria (Memtable). Se necessario, vengono aggiornate anche le eventuali strutture dati di supporto (filtri Bloom e indice sparso).
• Quando questo albero diventa troppo grande viene scaricato sul disco con le chiavi in ​​ordine.
• Quando arriva una lettura, la controlliamo utilizzando il filtro Bloom. Se il filtro Bloom indica che il valore non è presente allora diciamo al client che non è stato possibile trovare la chiave. Se il filtro Bloom indica che il valore è presente, iniziamo a ripetere le SSTable dalla più recente alla più vecchia.
• Complessità temporali dell'LSM
  • Tempo per leggere: O(log(N)) dove N è il numero di record nel disco
  • Tempo di scrittura: O(1) come scritto in memoria
  • Ora di eliminazione: O(log(N)) dove N è il numero di record nel disco
• Gli alberi LSM possono essere modificati in strutture dati più efficienti utilizzando più di 2 filtri. Alcuni di essi sono bLSM, Diff-Index LSM.