File griglia - Grid file

In informatica , un file grid o bucket grid è un metodo di accesso ai punti che suddivide uno spazio in una griglia non periodica in cui una o più celle della griglia si riferiscono a un piccolo insieme di punti. I file griglia (una struttura di dati simmetrica ) forniscono un metodo efficiente per archiviare questi indici su disco per eseguire ricerche di dati complesse.

Fornisce una griglia di n dimensioni dove n rappresenta quante chiavi possono essere utilizzate per fare riferimento a un singolo punto.

I file griglia non contengono dati stessi, ma contengono invece riferimenti al bucket corretto .

Usi

Un file griglia viene solitamente utilizzato nei casi in cui un singolo valore può essere referenziato da più chiavi.

Un file di griglia ha iniziato a essere utilizzato perché "le strutture di file tradizionali che forniscono accesso multichiave ai record, ad esempio i file invertiti, sono estensioni di strutture di file originariamente progettate per l'accesso a chiave singola. Manifestano varie carenze in particolare per l'accesso multichiave a file altamente dinamici ."

In una tradizionale struttura dati unidimensionale (es. hash ), una ricerca su un singolo criterio è solitamente molto semplice ma la ricerca di un secondo criterio può essere molto più complessa.

I file di griglia rappresentano un tipo speciale di hashing, in cui l'hash tradizionale viene sostituito da una directory di griglia.

Esempi

Database del censimento

Considera un database contenente i dati di un censimento. Un singolo record rappresenta una singola famiglia e tutti i record sono raggruppati in bucket. Tutti i record in un bucket possono essere indicizzati in base alla loro città (che è la stessa per tutti i record nel bucket) e alle strade di quella città i cui nomi iniziano con la stessa lettera.

Un file griglia può essere utilizzato per fornire un indice efficiente per questa struttura, in cui i record sono raggruppati in 26, ciascuno relativo ai nomi delle strade di una città che iniziano con una delle lettere dell'alfabeto. Questa struttura può essere pensata come un array , una tabella o una griglia con due dimensioni che chiameremo assi x e y.

Si può considerare l'asse x come la città e l'asse y come ciascuna delle lettere dell'alfabeto o, in alternativa, la prima lettera di ogni strada.

Ogni record in questa struttura è noto come cella. Ogni cella conterrà un puntatore al bucket appropriato nel database in cui sono archiviati i dati effettivi. Potrebbe essere necessaria una cella aggiuntiva o un'intestazione del record per memorizzare il nome della città. Altre celle raggruppate con esso dovranno solo contenere il puntatore al rispettivo bucket, poiché la prima cella corrisponde ai nomi delle strade che iniziano con "A", la seconda a "B" e così via.

Il database può essere ulteriormente esteso per contenere un campo continente per espandere il censimento ad altri continenti. Ciò farebbe sì che i record nello stesso secchio corrispondano alle famiglie su una strada che inizia con la stessa lettera, nella stessa città, nello stesso continente.

Le celle nel file della griglia sarebbero quindi costituite da un'intestazione di città e sei raggruppamenti (uno per ogni continente, esclusa l' Antartide ) di 26 celle relative alle strade con la stessa lettera iniziale, nella stessa città, nello stesso continente e potrebbe ora essere pensato come un array tridimensionale.

Vantaggi

Poiché una singola voce nel file della griglia contiene puntatori a tutti i record indicizzati dalle chiavi specificate:

  • Non sono richiesti calcoli speciali
  • Vengono recuperati solo i record corretti
  • Può essere utilizzato anche per query chiave di ricerca singola
  • Facile da estendere alle query su n chiavi di ricerca
  • Miglioramento significativo del tempo di elaborazione per le query a più chiavi
  • Ha un limite superiore di accesso a due dischi per l'accesso ai dati.

Svantaggi

Tuttavia, a causa della natura del file griglia, che gli conferisce i suoi vantaggi, ci sono anche alcuni svantaggi:

  • Impone spazio in alto
  • Sovraccarico delle prestazioni durante l'inserimento e l'eliminazione

Strutture dati correlate

Guarda anche

Riferimenti