Gli alberi B e altre strutture dati diventeranno obsolete con l'avvento delle unità a stato solido?

Gli alberi B vengono spesso utilizzati per indici di database su hard disk, ma presentano vantaggi anche come struttura dati in memoria, data la moderna gerarchia di memoria con più livelli di cache e con memoria virtuale. Anche se la memoria virtuale è su un SSD, ciò non cambierà.

Uso una libreria ad albero a più vie in memoria B + che ho scritto parecchio in C ++. può avere vantaggi in termini di prestazioni - il motivo per cui è stato originariamente scritto era cercare di usare meglio la cache - ma devo ammettere che spesso non funziona in questo modo. Il problema è il trade-off, il che significa che gli oggetti devono spostarsi all'interno dei nodi su inserimenti ed eliminazioni, cosa che non accade per gli alberi binari. Inoltre, alcuni degli hack di codifica di basso livello che ho usato per ottimizzarlo - beh, probabilmente confondono e sconfiggono l'ottimizzatore, a dire la verità.

Comunque, anche se i tuoi database sono memorizzati su un SSD, è ancora un dispositivo di archiviazione orientato ai blocchi e c'è ancora un vantaggio nell'usare B-Trees e altri alberi a più vie.

MA circa dieci anni fa, sono stati inventati algoritmi e strutture dati cache-ignari. Questi sono ignari delle dimensioni e della struttura delle cache, ecc. - rendono (asintoticamente) il miglior uso possibile di qualsiasi memoria dell'erarchia. Gli alberi B devono essere "sintonizzati" su una particolare gerarchia di memoria per utilizzarli al meglio (sebbene funzionino abbastanza bene per una vasta gamma di variazioni).

Le strutture dati ignare della cache non sono spesso viste in natura ma, se non del tutto, ma potrebbero anche rendere obsoleti i soliti alberi binari in memoria. Inoltre, potrebbero rivelarsi utili anche per dischi rigidi e unità SSD, dal momento che non si preoccupano delle dimensioni della pagina della cache del cluster o del disco rigido.

Il layout di Van Emde Boas è molto importante nelle strutture dati cache-ignote.

Il corso sugli algoritmi OpenCourseware del MIT include una copertura delle strutture di dati della cache ignari.

A priori, sì, la maggior parte dei motori di database dovrà essere riscritta poiché B-Tree non sarà più la struttura dati più efficiente per archiviare i dati, dato che la località è importante in un disco rigido in cui il disco si muove lentamente e i dati vengono recuperati in blocchi, il che significa che qualsiasi modifica ai dati deve essere:

1. Sposta la testa nella posizione corretta sul disco (~ 10 ms).
2. Attendi che il disco ruoti (a 10k rpm, ovvero 167 rotazioni al secondo, ma in media aspettiamo solo mezza rotazione, quindi ~ 3ms).
3. Leggi il blocco (~ 3 ms).
4. Modifica nella RAM. (~ 10ns)
5. Spostare nuovamente la testa nella posizione corretta sul disco (~ 10 ms di nuovo).
6. Attendi che il disco ruoti di nuovo (~ 3ms di nuovo).
7. Scrivi il blocco (~ 3 ms).

Questo è 10 + 3 + 3 + 10 + 3 + 3 = 34 ms

In media, fare lo stesso su un SSD è solo 1ms, indipendentemente dalla posizione sul disco.

E dal momento che una tabella hash è molto più veloce, potremmo pensare che una tabella hash potrebbe essere una sostituzione migliore.

L'unico problema è che gli hashtables non sono di tipo order preserving e quindi non è possibile trovare next e previous come fa Van Emde Boas.

Vedi:

1. link
2. link

Perché trovare il prossimo e il precedente è importante? Immagina di ottenere tutti gli elementi più grandi di x e minori di z, devi usare gli indici con trova precedente e trova successivo.

Bene, l'unico problema è che non abbiamo trovato gli hashtables con le abilità di conservazione degli ordini. Forse la dimensione del bucket nell'albero B sarà importante ma verrà risolta con algoritmi cache ignari.

Quindi direi che questo è un problema aperto.