-Creazione e caricamento: queste operazioni (molto elementari) consistono nella generazione di un archivio vuoto e in un ciclo di caricamento in cui i singoli record vengono registrati in modo
sequenziale. Nel caso in cui si voglia lavorare con archivi sequenziali ordinati, sarà necessario far seguire questa fase da un ordinamento.
- Ricerca: se si effettuano interrogazioni ed aggiornamenti su di un archivio una delle operazioni più frequenti è quella della ricerca di una registrazione. Naturalmente la tecnica varierà in rapporto al tipo di supporto usato e al fatto che esista o meno un ordinamento.
Ricerca completa: si tratta del metodo più semplice, che può essere applicato in tutte le situazioni e
consiste nella scansione dell’intero archivio fino al raggiungimento del record cercato.
Procedura RicercaCompleta
acquisisci la chiave di ricerca posizionati all’inizio dell’archivio
mentre (non è finito l’archivio) e (non hai trovato la registrazione) leggi record
Dato che la probabilità di ritrovare un certo record di un blocco qualsiasi è equiripartita su tutti gli elementi dell’archivio, la lunghezza media di ricerca LM su un archivio di N elementi sarà (N+1)/2 -Ricerca sequenziale: è applicato agli archivi sequenziali ordinati e rappresenta un’ottimizzazione del metodo precedente:
Procedura RicercaSequenziale
acquisisci la chiave di ricerca posizionati all’inizio dell’archivio
mentre ((non è finito l’archivio) o (non si è superato il valore della chiave cercata)) e (non hai trovato la registrazione) leggi record
se la chiave del record coincide con quella cercata allora si è trovata la registrazione fine ciclo
se non si è trovata la registrazione allora comunica che non esiste
fine
Dato che la probabilità di ritrovare un certo record di un blocco qualsiasi è equiripartita su tutti gli elementi dell’archivio, la lunghezza media sarà (N+1)/2. L’efficienza della ricerca sequenziale è
indipendente dal fatto che il record cercato sia presente o meno nell’archivio poiché il tempo di ricerca di una registrazione non esistente coincide con quello che si avrebbe nel caso la chiave esistesse.
-Ricerca binaria
Questo metodo di ricerca può essere applicato solo ad archivi ordinati, memorizzati su un supporto ad accesso diretto
Procedura RicercaBinaria
acquisisci la chiave di ricerca
posizionati a metà dell’archivio selezionato leggi un record
se la chiave del record coincide con quella cercata allora si è trovata la registrazione
altrimenti se l’archivio è formato da più di una registrazione allora se la chiave del record è minore di quella cercata
allora applica la procedura RICERCABINARIA alla prima metà dell’archivio altrimenti applica la procedura alla seconda metà dell’archivio
altrimenti il record non esiste
fine
L’archivio presentato è chiaramente di tipo ricorsivo e si riferisce ad archivi privi di record vuoti. Questo metodo se applicato ad archivi di grandi dimensioni e con alto fattore di riempimento, riduce drasticamente i tempi di ricerca, fino a portare il valore medio di ricerca a circa log2N
Inserimento
Se l’archivio non è ordinato l’operazione di inserimento non presenta grossi problemi; infatti è sufficiente
aggiungere il nuovo elemento in coda o, nel caso in cui esistano blocchi liberi all’interno della struttura, nel primo record fisico logicamente libero.
Se invece la struttura è ordinata l’operazione risulta più onerosa, in quanto sarà necessario individuare la posizione corretta in cui porre la nuova registrazione, spostare tutte le registrazioni successive in modo da creare uno spazio
32
Aggiornamento
Con questo termine intendiamo far riferimento a quell’operazione con cui si modificano i valori di uno o più campi (eccetto la chiave) di un record già esistente. Nel caso dell’organizzazione sequenziale su supporto ad accesso diretto l’operazione sopra citata si compone di due fasi: la ricerca del record e la sua riscrittura con le modifiche.
Cancellazione
Se si vuole mantenere una corrispondenza reale tra struttura logica e struttura fisica, per cancellare una registrazione occorre effettuare la riscrittura dell’intero archivio, tralasciando il record eliminato, in modo da ottenere una nuova organizzazione priva di spazi vuoti.
Dato che questa operazione è onerosa si può pensare di sostituire la cancellazione fisica con una logica, ponendo un’apposita marca o nel campo chiave o in un apposito campo del record da eliminare. In questo caso è sufficiente provvedere periodicamente alla ristrutturazione dell’archivio.
Considerazioni conclusive
Ancora oggi, nonostante la diffusione delle banche dati, una grande quantità di applicazioni utilizza organizzazioni sequenziali per i seguenti motivi:
- molti programmi richiedono le stesse operazioni su tutti gli elementi dell’archivio, elaborandoli nello stesso ordine in cui sono memorizzati
- la realizzazione di programmi applicativi di complessità limitata è facilitata dall’uso di strutture semplici quali quella sequenziale
- la ristrutturazione degli archivi sequenziali, per quanto lunga, non presenta grossi problemi e di conseguenza è possibile effettuare questa operazione con maggiore frequenza
- l’organizzazione sequenziale non richiede l’uso di memoria aggiuntiva per la gestione di strutture di supporto quali indici, tabelle……
Operazioni sugli archivi sequenziali con indice
Gli archivi sequenziali con indice non ordinati possono essere assimilati a quelli ordinati se si considera l’ultimo livello di indice come immagine dell’archivio principale.
Ricerca
La ricerca di una registrazione in una struttura sequenziale con indice avviene attraverso i seguenti passi:
- si scandisce l’indice di livello più esterno fino a raggiungere la prima chiave di valore maggiore o uguale a quello cercato, individuando così l’indirizzo del blocco dell’indice di livello più basso in cui proseguire la ricerca
- si ripete, di volta in volta, la procedura del passo precedente sul blocco selezionato, scendendo via via negli indici di livello inferiore, finchè si è individuato l’indirizzo del blocco dell’archivio principale in cui è contenuta la
registrazione desiderata.
- si scandisce il blocco alla ricerca della registrazione
Aggiornamento
Se si vogliono modificare i contenuti di alcuni campi di un record, è necessario procedere alla sua individuazione nell’archivio principale con una ricerca attraverso gli indici e, solo successivamente, passare alla registrazione dei nuovi valori. Tuttavia, nei casi in cui venga richiesto di effettuare la medesima variazione su tutti i record
dell’archivio è inutile effettuare ogni volta la ricerca del record da modificare, ma conviene, data la struttura sequenziale dell’archivio principale, operare direttamente su quest’ultimo, senza passare attraverso gli indici.
Inserimento e cancellazione
Mentre le operazioni di ricerca e aggiornamento non presentano particolari problemi, poiché non implicano alcuna variazione nell’organizzazione complessiva dell’archivio, quelle di inserimento e cancellazione possono indurre ristrutturazioni non solo nell’archivio principale, ma anche in uno o più indici. Infatti, l’inserimento o la cancellazione di un elemento in una struttura sequenziale ordinata comportano al minimo lo scorrimento di tutte le registrazioni successive, operazione che, pur non complessa dal punto di vista algoritmico, può rivelarsi onerosa in termini di tempo.
Come abbiamo già visto, però, il numero degli spostamenti può essere sensibilmente ridotto, ricorrendo ad un’opportuna gestione di aree di overflow.
Overflow distribuito
Questa tecnica prevede la creazione di uno spazio libero in coda ad ogni blocco dell’archivio principale da usare per collocare eventuali inserimenti. All’interno del singolo blocco l’inserimento può avvenire in due modi:
-La nuova registrazione viene inserita direttamente nella zona di overflow associata al blocco,
mantenendo l’ordinamento logico attraverso appositi puntatori: in questo caso la ricerca all’interno del blocco deve essere effettuata esclusivamente in modo sequenziale
- la nuova registrazione viene inserita nel posto corretto, facendo scorrere tutte le registrazione seguenti verso l’area di overflow: in questo caso viene mantenuto l’ordine fisico delle registrazioni e quindi possono essere applicati metodi di ricerca ottimizzati, quali quello dicotomico.
Overflow concentrato
Questa tecnica prevede un’unica area di overflow indipendente, posta in fondo all’archivio principale per memorizzare i record provenienti da un qualsiasi blocco.
Dunque la successione logica dell’ordinamento viene mantenuta attraverso puntatori tra le
registrazioni, così da formare delle liste indipendenti. Poiché una tecnica ottimizza i tempi di ricerca a scapito dello spazio di memoria occupato, mentre l’altra ottimizza l’occupazione di memoria
penalizzando però i tempi di accesso, può essere conveniente optare per una terza modalità che
rappresenta un compromesso tra le due. Si possono infatti prevedere delle aree di dimensione limitata alla fine di ogni blocco e un’area di overflow indipendente, a cui accedere solo nei casi in cui ci si trovi di fronte ad un trabocco da una delle aree di overflow distribuito.