Struttura dati per l'archiviazione dei dati ordinati

-1

Quale è un buon modo per archiviare carichi di stringhe ordinate su un file in modo che gli inserimenti e le letture siano veloci?

Potrei memorizzarlo su un albero e leggerlo / modificarlo / memorizzarlo secondo necessità, ma ciò sembra uno spreco per operazioni come "cercare l'ennesimo oggetto". Non esiste una struttura di dati indicizzata utilizzata specificamente per archiviare e recuperare informazioni ordinate?

Ovviamente un database funzionerebbe, ma in che modo i database memorizzano il loro indice per un accesso più rapido? Dubito che eseguano una scansione lineare attraverso un indice per capire l'ennesimo elemento di una lista e leggono / scrivono tutti gli indici per aggiornare una singola riga nel mezzo.

    
posta Lorenzo Boccaccia 08.04.2016 - 15:55
fonte

1 risposta

0

Se stai parlando di enormi dati, dovresti prendere in considerazione l'uso della struttura dati BTree (o delle sue varianti). I BTrees sono usati dalla maggior parte dei database relazionali per l'indicizzazione di dati enormi.

Puoi controllare B-tree su Wikipedia per ulteriori dettagli.

In base alla quantità di dati che devi gestire, le tue funzioni obiettive variano. Ad esempio, se devi gestire enormi quantità di dati, la tua funzione obiettivo è ottimizzare (ridurre al minimo) il numero di letture del disco (/ cerca). Nel caso in cui si abbia a che fare con un piccolo insieme di dati (che possono essere contenuti nella RAM), la funzione obiettivo è ottimizzare (ridurre al minimo) il numero di cicli della CPU.

    
risposta data 08.04.2016 - 16:38
fonte

Leggi altre domande sui tag