Gli archivi

Materie:Riassunto
Categoria:Informatica
Download:125
Data:25.05.2005
Numero di pagine:4
Formato di file:.doc (Microsoft Word)
Download   Anteprima
archivi_2.zip (Dimensione: 7.41 Kb)
trucheck.it_gli-archivi.doc     38.5 Kb
readme.txt     59 Bytes



Testo

U.D. 1 - GLI ARCHIVI
Un archivio è un insieme d’informazioni (record) caratterizzate da alcuni aspetti:
• tra esse esiste un nesso logico;
• sono rappresentate secondo un formato che ne rende possibile l’interpretazione;
• sono scritte su un formato che consente la lettura a distanza nel tempo;
• sono organizzate in modo in modo di avere una facile consultazione.
Un record è caratterizzato da campi (le singole informazioni); l’elenco dei campi è chiamato tracciato del record.
Per creare un archivio occorre:
1) Nome archivio
2) Tracciato del record
3) Supporto di memoria da usare
4) Dimensione massima dell’archivio
5) Tipo di struttura
Operazioni di manipolazione:
• Inserimento nuovi dati
• Modifica dati
• Cancellazione dati
Operazioni d’interrogazione:
• Reperire i dati all’interno dell’archivio
Per memorizzare dati si possono usare tra gli altri:
• nastro magnetico → copie di sicurezza (backup)
• disco magnetico → settore (traccia) = corona + settore + testina (faccia)
• floppy disk, dischi zip, dischi ottici.
Il collegamento tra il programma dell’utente e i file è gestito da due moduli del sistema operativo: il gestore delle periferiche e il gestore dei file.
Il gestore delle periferiche è il modulo che ha il compito di controllare il funzionamento fisico delle apparecchiature collegate all’unità centrale.
Il modulo che svolge le funzioni di gestore dei file è chiamato file system. Il file system consente di riferirsi alle informazioni registrate in termini di identificatori piuttosto che d’indirizzi fisici, adoperando allo scopo le directory.
Organizzare un archivio significa ottimizzare l’uso dello spazio disponibile sul supporto e ridurre i tempi d’accesso e ritrovamento dei dati. Inoltre la progettazione deve avere due obiettivi: l’integrazione degli archivi, l’indipendenza dello schema logico dei dati dall’implementazione software. Questo rende più facile la manutenzione.
ORGANIZZAZIONE SEQUENZIALE
L’organizzazione più semplice consiste nel registrare i record uno di seguito all’altro, in modo sequenziale: in lettura i record possono essere ritrovati scorrendo tutti i record del file dal primo all’ultimo però occorre segnalare la fine del file (eof). Questo sistema è svantaggioso quando è elevato il numero dei record.
ORGANIZZAZIONE AD ACCESSO DIRETTO
Utilizzato con record di lunghezza fissa punta direttamente alla posizione del record nel file con la formula:
( nr° record ricercato – 1) * sizeof (record) + 1
L’organizzazione ad accesso diretto può essere conveniente se utilizzata negli archivi per i quali i record vengono identificati attraverso un numero progressivo.
ORGANIZZAZIONE AD INDICI
Nei file con organizzazione ad indici accanto alla zona dove sono registrati i record viene gestita una tabella delle chiavi: la ricerca dei record avviene leggendo le chiavi e non i record come avviene nei file sequenziali. Ad ogni chiave è associato il puntatore al record, cioè la posizione che il record occupa all’interno del file.
La chiave può essere primaria, quando identifica univocamente un record, o secondaria.
Gli accessi consentiti per un archivio indexed sono:
➢ sequenziale → quando le operazioni di lettura e scrittura sono fatte in base all’ordine crescente delle chiavi;
➢ diretto → quando è possibile effettuare una ricerca diretta;
➢ dinamico → quando il programmatore può scegliere se utilizzare il sequenziale o il diretto.
ARCHIVIO RANDOM
Questa organizzazione perde il concetto di sequenzialità, conseguentemente l’utilizzo dell’eof è inutile. I file con organizzazione random contengono dei record che vengono identificati attraverso il numero di posizione che essi occupano all’interno del file. Volendo associare a ciascun record un valore chiave occorre determinare una funzione che possa trasformare la chiave in numero. Questa tecnica di indicizzazione si chiama metodo di trasformazione della chiave o metodo hash.

Metodi di Randomizzazione (tecniche hash)
In generale la conversione della chiave in indirizzo si articola nei seguenti passi:
1) se la chiave non è numerica occorre convertirla in un valore numerico;
2) si applica alla chiave trasformata l’algoritmo di randomizzazione scelto;
3) si opera sul numero ottenuto per adattare questo valore al range di indirizzi di memoria effettivamente disponibili.

Algoritmo 1
La chiave numerica è composta da molte cifre e il range d’indirizzi disponibili è limitato.
Blocchi 10000 a partire da 0
Chiave 901102311 → estraggo le ultime 4 cifre → Indirizzo 2311
Funziona quando le chiavi sono numeri consecutivi con poche interruzioni.
Algoritmo 2
Blocchi 10000 a partire da 0
Chiave 901102311 → faccio il quadrato → 81153659686278431 → prendo le 4 cifre centrali → Indirizzo 5968
Algoritmo 3
Blocchi 7429 a partire dall’indirizzo 4001
Chiave 901102311 → Prendo il resto di (Chiave / Blocchi) e sommo indirizzo di partenza →
→ 469 + 4001 → Indirizzo 4470
Si possono però verificare delle collisioni, ovvero due key potrebbero puntare allo stesso indirizzo. Per evitare le collisioni occorre gestire i sinonimi.
Ci sono tre metodi principali per la gestione delle collisioni:
1) Con il metodo più semplice, detto scansione lineare, il software controlla il record successivo per vedere se contiene una registrazione. Se non c’è nessuna registrazione, il nuovo record viene messo in quella locazione. Se invece la posizione è gia occupata, si va a verificare quella immediatamente successiva. Se si raggiunge la fine del file, si riparte dall’inizio.
2) Un metodo alternativo è rappresentato dalla scansione quadratica: viene calcolato il numero di record, se il posto è già occupato si va a controllare il primo posto successivo, poi il quarto, poi il nono e così via. Il processo termina quando sono stati esaminati la metà dei record del file con un messaggio di errore del file pieno.
3) Una terza soluzione consiste nel creare un’area separata, detta anche area di overflow, adatta a contenere i record che hanno valori di chiave corrispondenti a situazioni di collisione con le chiavi già esistenti.

1

Esempio