Gli archivi sequenziali

Piero Gallo Fabio Salerno
Task
Corso di informatica
2
il libro si estende sul web
Gli archivi
sequenziali
il libro si estende sul web
LEZIONE
L’organizzazione
sequenziale
L’organizzazione logica sequenziale
Con archivio logico sequenziale intendiamo un archivio in cui i record sono registrati in posizioni contigue a partire dalla prima.
Quando su uno o più campi del record è possibile stabilire un ordinamento, allora si può definire anche un ordinamento logico tra le registrazioni che, in determinate circostanze, può anche coincidere con l’ordine fisico. Se i due ordinamenti coincidono, l’archivio viene detto sequenziale ordinato.
Nella seguente figura riportiamo un esempio di archivio sequenziale ordinato: la
funzione di chiave primaria è stata associata al nome del personaggio e le varie
registrazioni sono ordinate alfabeticamente.
Indirizzo
1
...
i
i+1
i+2
i+3
i+4
Chiave
Informazioni
...
...
Minni
Paperino
Paperoga
Pluto
Topolino
...
...
...
...
...
...
...
Tra le caratteristiche fondamentali di questo tipo di organizzazione ricordiamo:
• la possibilità di immissione solo in coda che consente di non perdere l’ordine
di immissione;
• l’utilizzo vantaggioso per le operazioni batch (offline);
• l’utilizzo svantaggioso, ossia inefficiente, per elaborazioni di tipo interattivo
(online) a causa degli elevati tempi di risposta;
• la possibilità di utilizzare esclusivamente un metodo di accesso sequenziale
puro.
L’organizzazione fisica sequenziale
Occupiamoci, ora, dell’aspetto fisico dell’archivio.
Con archivio fisico sequenziale si indica il modo in cui i file sono scritti su disco e non la natura logica degli stessi, descritta nel precedente paragrafo di
questa lezione.
In questo paragrafo, pertanto, quando parliamo di “archivi sequenziali” facciamo
riferimento ad “archivi fisici sequenziali”.
Gli archivi sequenziali sono memorizzati sulla memoria di massa attraverso la
tecnica dell’allocazione contigua. In questo modo, i blocchi che costituiscono il
file sono memorizzati uno di seguito all’altro, ossia in ordine sequenziale, come
si osserva nella figura a pagina seguente.
2
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
L’organizzazione sequenziale
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LEZIONE 1
File
Blocco iniziale Lunghezza
compito
5
3
lezione
18
5
programma 12
1
...
Come si vede, l’allocazione contigua di un file è definita dando l’indirizzo del primo blocco sul quale il file stesso è allocato e il numero di blocchi che compongono quest’ultimo. Se ad esempio il file è memorizzato a partire dalla locazione b
ed è lungo n, allora occuperà i blocchi: b, b+1, b+2, ..., b+n–1.
Questo tipo di allocazione presenta vantaggi e svantaggi. Il vantaggio principale
consiste nella semplificazione dell’operazione di accesso al file, che consente un
risparmio di tempo in fase di lettura dei dati, in quanto la testina del disco non è
costretta a effettuare grandi movimenti per poter leggere i vari blocchi. Inoltre,
considerato che si conosce a priori la dimensione dei vari blocchi e l’indirizzo su
disco del primo blocco occupato, è possibile realizzare l’accesso diretto in modo
sostanzialmente semplice.
L’accesso a un file allocato in modo contiguo è, quindi, piuttosto semplice, ma le
difficoltà sorgono ogniqualvolta si ha la necessità di allocare un nuovo file. Se il
file da memorizzare è “lungo” n blocchi, si deve cercare all’interno della lista dello spazio libero se esiste una serie di n blocchi contigui. Ciò non è sempre possibile. Questa operazione di ricerca di uno spazio idoneo può essere effettuata dal
sistema operativo utilizzando diverse strategie:
• ricercando la prima area libera sufficientemente grande (first-fit);
• ricercando la prima area libera sufficientemente grande, iniziando l’operazione di scansione dal punto in cui si trova la testina (next-fit);
• ricercando l’area libera più piccola che possa contenere il file (best-fit);
• ricercando l’area libera più grande possibile (worst-tit).
Qualsiasi tecnica si utilizzi, però, sorgeranno comunque dei problemi: il disco
continuerà a essere frammentato sempre di più, fino a trovarsi in una situazione
che potrebbe sembrare assurda, ma purtroppo è assolutamente reale: non sarà
possibile memorizzare un file poiché non esisterà uno spazio contiguo abbastanza capiente da contenerlo, nonostante lo spazio libero complessivo sia sensibilmente maggiore di quello necessario.
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
3
ESEMPI
LEZIONE
L’organizzazione sequenziale
Oggigiorno la gestione degli archivi di dati (in forma di database) è oramai delegata ad appositi software denominati DMBS (Database Management System), poiché la loro semplicità di utilizzo e la loro sicurezza ne consente l’utilizzo anche
senza conoscere neppure marginalmente le varie modalità con cui organizzano i
dati e li memorizzano. Nonostante ciò, è comunque utile conoscere alcuni tipi di
organizzazione logica che consentono di organizzare archivi per applicazioni personalizzate. Quelli che andremo ad analizzare non sono indispensabili: sono semplicemente comodi!
I file di testo
Un archivio organizzato come file di testo contiene solo semplici caratteri di
scrittura, senza alcuna informazione sul loro formato (dimensione, colore e
così via). Solitamente rappresenta un testo che può essere letto con semplici
editor di testo senza bisogno di installare sofisticati word processor.
I byte dei file di testo rappresentano quindi lettere, numeri, punteggiatura, spazi
e altri normali simboli stampabili, ma possono contenere anche specifici caratteri di controllo come tab (per la tabulazione), carriage return (CR) per il ritorno a
capo e line feed (LF) per l’avanzamento alla riga successiva.
I file di testo sono molto utilizzati dai software ad esempio durante la fase di installazione, poiché contengono i dati per compiere la configurazione. Pensa ai file
.ini quali, ad esempio, system.ini, win.ini e boot.ini di Windows che memorizzano alcuni dati relativi alla configurazione del sistema.
Un motivo della diffusione dei file di testo è la facile interpretabilità da parte dell’uomo. Un esempio di struttura di questo tipo di file è riportata nella seguente figura: esempio:
[Sezione1]
; Un commento su questa sezione.
Parametro1 = Questo è un valore assegnato, come quello seguente.
Parametro2 = 1
[Sezione2]
; Un ulteriore commento.
Parametro1 = Un esempio...
Parametro2 = 25
4
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
L’organizzazione sequenziale
ESEMPI 1
Analizziamolo:
• una sezione inizia con la dichiarazione del suo nome racchiuso fra parentesi
quadre (nel nostro caso [Sezione1] e [Sezione2]);
• all’interno di una sezione, l’assegnazione di un valore a un parametro si effettua con un’assegnazione matematica (variabile = valore);
• una riga che inizia con un punto e virgola (‘;’) è un commento, e in quanto tale
viene ignorata.
I file CSV
CSV (Comma Separated Values = valori separati da virgola) è un formato per
file di testo utilizzato per memorizzare dati nei fogli elettronici, nei database e
per lo scambio di dati tra sistemi differenti che operano su piattaforme incompatibili.
Al suo interno, ogni riga rappresenta un record composto da campi separati da
una virgola (nel caso in cui la virgola sia una carattere da rappresentare all’interno di un campo, il carattere separatore viene sostituito con un altro, ad esempio
il punto e virgola, oppure il campo stesso viene racchiuso tra virgolette). Ogni record è separato dal successivo dalla sequenza di caratteri CR+LF (Carriage Return
+ Line Feed) che consentono, rispettivamente, di ritornare all’inizio della riga e di
aggiungere una nuova riga al file.
OPERA
AUTORE
CASA EDITRICE
I Robot e l’Impero
Isaac Asimov
Mondadori
Mondo senza fine
Ken Follett
Mondadori
Java Step by Step “2° Edizione”
Gallo, Salerno
Scuola & Azienda
Paura della matematica
Peter Cameron
La Feltrinelli
L’esempio qui sopra si potrebbe rappresentare in CSV come:
OPERA,AUTORE,CASA EDITRICE
I Robot e l’Impero,Isaac Asimov,Mondadori
Mondo senza fine,Ken Follett, Mondadori
“Java Step by Step “”2° Edizione”””,”Gallo, Salerno”,Scuola & Azienda
Paura della matematica,Peter Cameron,La Feltrinelli
Da notare che:
• i campi sono separati da virgola e vengono racchiusi tra doppi apici se contengono virgole;
• è preferibile non lasciare spazi prima e dopo i campi (se intenzionali, tali spazi devono essere racchiusi tra doppi apici);
• per rappresentare un carattere doppi apici in un campo occorre raddoppiarlo:
“ diventa “”.
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
5
ESEMPI
LEZIONE
L’organizzazione sequenziale
I file XML
L’HTML (Hypertext Markup Language) è un linguaggio che consente di creare in
maniera standardizzata pagine di informazioni formattate in grado di raggiungere attraverso Internet gli utenti di tutto il mondo. Insieme al protocollo HTTP
(Hypertext Transport Protocol), l’HTML ha rivoluzionato il modo in cui le persone
trasmettono e ricevono informazioni; il suo scopo principale, però, è sempre stato inerente la visualizzazione dei dati. L’HTML, infatti, considera particolarmente
il modo in cui le informazioni vengono presentate e non si occupa minimamente del tipo o della struttura di tali informazioni.
Per far fronte a tali aspetti è stato sviluppato il linguaggio XML (eXtensible Markup
Language) che espande le capacità di HTML grazie all’introduzione di nuovi marcatori. La sintassi di XML è molto scarna, non prevede tanti elementi di marcatura. Quando si crea un documento XML, invece di utilizzare un set di elementi predefiniti, è possibile crearne di nuovi e assegnare loro i nomi desiderati, il che
spiega il termine extensible, cioè estensibile.
Un file XML è un file di testo costituito da un insieme di tag. La sua struttura è
ad albero: esiste, infatti, un solo tag principale che può contenerne altri, ciascuno dei quali ne può contenere altri ancora e così via.
Come per gli altri tipi di file esaminati, anche i file XML sono utilizzati per memorizzare e scambiare dati tra applicazioni, o come file di configurazione. Sono file
ormai molto diffusi, al punto che alcuni gestori di database memorizzano i dati direttamente in questo formato oppure, pur non scrivendo i dati in XML, consentono di estrarne il contenuto in questo formato.
Proviamo a comporre un file XML con i dati presenti nel seguente elenco di amici:
Rossi
Maria
20134
Milano
Neri
Paolo
73100
Lecce
Verdi
Riccardo
70100
Bari
Gialli
Daniela
00195
Roma
<?xml version=”1.0” encoding”=ISO-8859-1”?>
<AMICI>
<AMICO>
<COGNOME>Rossi</COGNOME>
<NOME>Maria</NOME>
<CAP>20134</CAP>
<CITTA>Milano</CITTA>
</AMICO>
<AMICO>
<COGNOME>Neri</COGNOME>
<NOME>Paolo</NOME>
<CAP>73100</CAP>
<CITTA>Lecce</CITTA>
</AMICO>
<AMICO>
<COGNOME>Verdi</COGNOME>
<NOME>Riccardo</NOME>
<CAP>70100</CAP>
<CITTA>Bari</CITTA>
</AMICO>
<AMICO>
<COGNOME>Gialli</COGNOME>
6
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
L’organizzazione sequenziale
ESEMPI 1
<NOME>Daniela</NOME>
<CAP>00195</CAP>
<CITTA>Roma</CITTA>
</AMICO>
</AMICI>
È importante notare che i nomi degli elementi dei documenti XML (ad esempio:
AMICI, AMICO, COGNOME, NOME, CAP e CITTA), non fanno parte della definizione XML. I nomi degli elementi vengono creati durante la generazione di un determinato documento e possono essere scelti a proprio piacimento. Nell’ esempio
avremmo potuto continuare a scrivere tanti altri elementi AMICO e al loro interno gli elementi COGNOME, NOME, CAP e CITTA.
Pertanto, un documento XML è strutturato in base a una gerarchia strutturata, in
cui gli elementi risultano annidati in altri elementi, con un unico elemento di livello superiore (AMICI, nel nostro caso), il quale prende il nome di elemento del
documento o elemento principale.
I file binari
I file binari sono file contenenti dati generici che non sono direttamente leggibili dall’utente. In realtà, dal punto di vista della macchina, non c’è distinzione
tra file di testo e fil binari, poiché tutti entrambi non sono altro che sequenze
di byte. La differenza sta solo in ciò che i byte rappresentano e nel modo in cui
sono utilizzati.
Un file binario è una pura sequenza di byte, senza alcuna struttura particolare. È
un’astrazione di memorizzazione assolutamente generale, utilizzabile per memorizzare informazioni di qualsiasi natura come ”fotografie” della memoria, rappresentazioni interne binarie di numeri, immagini, canzoni campionate e, volendo,
anche caratteri!
I file binari sono solitamente concepiti come sequenze di byte: i singoli bit che costituiscono il file
sono raggruppati in gruppi di otto. Questi file contengono byte che devono generalmente essere interpretati in modo diverso dai caratteri: i file compilati sono un esempio (i programmatori si riferiscono
spesso al codice oggetto col termine “binario”), ma
si può trattare di immagini, musica, dati compressi
o di qualsiasi altro tipo.
Aprendo un file binario con un editor di testo, ogni
gruppo di otto bit viene regolarmente interpretato e
tradotto come un carattere e ne risulta una sequenza del tutto incomprensibile (a meno di coincidenze o inserti di testo nel file). Se
lo si apre con un diverso tipo di applicazione, questa interpreterà i singoli byte del
file a suo modo: potrebbe, quindi, farvi corrispondere una cifra e restituire una
sfilza pressoché casuale di numeri; oppure, se il file viene riconosciuto come eseguibile, il computer cercherà in essi delle istruzioni in linguaggio macchina.
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
7
Le operazioni logiche
sugli archivi
sequenziali
il libro si estende sul web
LEZIONE
Le operazioni consentite su un archivio a organizzazione sequenziale sono riassunte nel seguente diagramma:
ORGANIZZAZIONE
LOGICA
ACCESSO SEQUENZIALE
Inserimento:
Modifica:
Cancellazione:
Ricerca:
ARCHIVI
SEQUENZIALI
in coda
usa file differenziale
usa file differenziale
completa
ACCESSO DIRETTO
SINGOLO
FILE
NON
ORDINATO
ORDINATO
CON USO
DI INDICI
Inserimento:
Modifica:
Cancellazione logica:
Cancellazione fisica:
Ricerca:
in coda
immediata
immediata
solo al riordino
completa
ACCESSO SEQUENZIALE
Inserimento:
Modifica:
Cancellazione:
Ricerca:
usa aree dei trabocchi
usa file differenziale
usa file differenziale
usa file differenziale
sequenziale
ACCESSO DIRETTO
INDICE
SEMPLICE
INDICE TRAMITE
LISTA CONCATENATA
Inserimento:
usa aree dei trabocchi
Modifica:
immediata
Cancellazione logica:
immediata
Cancellazione fisica: solo al riordino
Ricerca:
sequenziale
binaria
interpolata
Inserimento
Per l’operazione di inserimento occorre distinguere sempre tra archivi non ordinati e archivi ordinati.
Su un archivio non ordinato, l’inserimento non comporta problemi: il record si
aggiunge in coda o, se nell’archivio esistono delle posizioni libere, può essere inserito nella prima di esse.
I problemi, questa volta, sorgono se l’archivio è ordinato. In questo caso, infatti,
occorre individuare l’esatta posizione in cui collocare il record: appare evidente
che, una volta individuata la posizione, occorrerà traslare tutti i record successivi
in modo da creare lo spazio. Se nell’archivio ci fossero posizioni libere, l’inserimento sarebbe meno oneroso, in quanto potremmo limitare la traslazione soltanto fino al primo spazio libero. Considerato che la presenza di tali spazi agevola
questa operazione, perché non crearli di proposito in fase di progettazione dell’archivio? Operando in questo modo, occorre distribuire un congruo numero di aree
libere lungo l’archivio, scegliendo opportunamente il numero e la dimensione in
funzione del problema e delle risorse a disposizione.
È ovvio, comunque, che se la presenza di tali aree agevola l’inserimento, ostacola, però, la ricerca. Alternative efficienti possono essere applicate solo su archivi
ordinati. Vediamone qualcuna.
Una prima soluzione consiste nel registrare i nuovi record in un archivio temporaneo o differenziale. Si procede poi, periodicamente, a una fusione tra i due archivi, così da rigenerare l’archivio principale. Questa soluzione non è delle miglio-
8
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
Le operazioni logiche
sugli archivi sequenziali
LEZIONE 2
ri, in quanto alcune operazioni, come ad esempio la ricerca, sarebbero eseguite
in modo poco efficiente perché, per reperire un record, occorrerebbe operare sia
sull’archivio principale che su quello temporaneo, con conseguente aumento dei
tempi di risposta.
La soluzione ottimale consiste nel predisporre nell’archivio delle aree libere, dette aree di overflow (o aree dei trabocchi), destinate ad accogliere i nuovi record
inseriti. Queste aree possono essere disposte uniformemente nell’archivio principale o in un altro archivio differenziale (aree di overflow distribuito), oppure essere allocate in un unico punto dell’archivio o, ancora una volta, in un altro archivio differenziale (aree di overflow concentrato).
Aree di overflow
distribuito
Area di overflow
concentrato
Aggiornamento (riscrittura)
La fase di aggiornamento, ossia l’operazione che consente di apportare modifiche ai campi di un record (a eccezione della chiave), può essere svolta, come al
solito, in due modi diversi dipendenti dal metodo di accesso.
Se l’accesso è sequenziale, l’aggiornamento di un record può essere svolto solo
riscrivendo l’intero archivio. Le modifiche vengono raccolte in un altro archivio e,
successivamente, si provvede all’aggiornamento dell’archivio principale.
Nel caso di accesso diretto, invece, l’aggiornamento è una delle operazioni più
semplici da realizzare, in quanto consta solo di tre semplici fasi:
• ricerca del record di chiave K che si intende aggiornare;
• modifica del record;
• riscrittura del record modificato nella stessa posizione.
Cancellazione
Anche per la cancellazione valgono le medesime considerazioni svolte per l’aggiornamento. Pertanto, nel caso di archivi sequenziali ad accesso sequenziale
l’unico modo per poter cancellare un record (e quindi mantenere la corrispondenza tra la struttura logica e quella fisica) è quello di riscrivere l’intero archivio
privato del record stesso servendosi di un archivio di appoggio.
Nel caso di archivi sequenziali ad accesso diretto, si ovvia a questo increscioso inconveniente effettuando una cancellazione logica, ossia predisponendo un apposito campo in grado di contenere un valore la cui presenza indica, appunto, la
cancellazione del record. Periodicamente si provvederà alla compattazione dell’archivio, eliminando fisicamente i record marcati per la cancellazione (cancellazione fisica).
Ordinamento
È ormai evidente che l’ordinamento riveste un ruolo di fondamentale importanza per garantire l’efficienza di talune operazioni. Per questo, occorre fare molta
attenzione nella scelta del metodo da applicare per ordinare l’archivio. Senza
scendere in dettagli, ricordiamo che molti dei metodi di ordinamento descritti nel
primo volume del testo possono essere tranquillamente applicati anche agli archivi sequenziali ad accesso diretto. Ciò, ovviamente, non è valido per gli archivi memorizzati su dispositivi a esclusivo accesso sequenziale.
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
9
Le operazioni logiche:
la ricerca
il libro si estende sul web
LEZIONE
Le esigenze maggiormente diffuse nell’uso degli archivi sono quelle di inserimento, consultazione e aggiornamento di record. In presenza di tali esigenze, la ricerca dei record registrati è una delle operazioni più importanti e più frequenti. È ovvio, quindi, che tale operazione debba essere compiuta utilizzando una tecnica
che consenta di ottenere il miglior risultato nel minor tempo possibile. La scelta
del metodo riveste un ruolo di fondamentale importanza e varia in base al tipo di
supporto di memoria utilizzato e alla presenza o meno di un ordinamento. In passato gli archivi venivano memorizzati sui nastri magnetici e, su di essi, l’unico
metodo di ricerca attuabile era quello della ricerca completa dell’archivio, sino al
reperimento del record di chiave desiderata. Il numero medio di accessi di tale
metodo è il seguente:
• successo: (N + 1)/2 accessi;
• insuccesso: N accessi;
dove N è il numero di record presenti nell’archivio.
Quando si cominciò a trattare con archivi in cui si interveniva con frequenza solo
su alcuni record, si cercò di ridurre il numero medio di accessi collocando tali record nelle prime posizioni dell’archivio. Questo metodo apportò un parziale incremento di efficienza solo in caso di successo: infatti, più probabile era la chiave, meno accessi erano necessari. In caso di insuccesso, invece, la situazione non
mutava: erano sempre necessari N accessi. Con gli archivi ordinati si poté ricorrere a un altro metodo di ricerca, la ricerca sequenziale, ottenuta mediante l’ottimizzazione della scansione (la ricerca, infatti, si interrompe quando si trova la chiave
cercata oppure quando ci si posiziona su un record di chiave maggiore di quella
cercata). In tal caso, il numero medio di accessi diveniva:
• successo: (N + 1)/2 accessi;
• insuccesso: (N + 1)/2 accessi.
Ricapitoliamo:
RICERCA in archivi a
ORGANIZZAZIONE Sequenziale
e ACCESSO Sequenziale
Archivio
non ordinato
Archivio
ordinato
Archivio con chiavi
di frequente
movimento in testa
Successo
Insuccesso
Successo
Insuccesso
Successo
Insuccesso
(N + 1)/2
accessi
N
accessi
(N + 1)/2
accessi
(N + 1)/2
accessi
In funzione
della probabilità
della chiave
N
accessi
Analizziamo, ora, il problema della ricerca applicato ad archivi a organizzazione
sequenziale memorizzati su supporti ad accesso diretto. Quando è consentito
l’accesso diretto, si possono verificare le seguenti situazioni:
• se si conosce l’indirizzo del record da ricercare, il problema non sussiste: mediante un accesso, ci si posiziona direttamente sul record;
• se l’indirizzo del record non è noto e l’archivio è disordinato, la situazione resta
analoga a quella descritta per l’accesso sequenziale;
• se l’indirizzo del record non è noto, ma l’archivio è ordinato, il problema viene
risolto con l’impiego di tecniche di ricerca molto efficienti, quali la ricerca binaria. Per quanto riguarda questo metodo di ricerca, sia in caso di insuccesso
che di successo (sia riferito al caso medio che a quello pessimo) si può dimo-
10
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
Le operazioni logiche: la ricerca
LEZIONE 3
strare che il numero di accessi è pari a log(N). Il numero medio di accessi della ricerca interpolata, invece, è pari a log(log(N)), quindi è nettamente inferiore
a quello della ricerca binaria.
Riportiamo la soluzione di massima dell’algoritmo della ricerca binaria espresso
in forma ricorsiva.
FUNZIONE RicercaBinaria
INIZIO
Posizionati sulla posizione centrale della porzione di archivio da esaminare
Leggi il record corrispondente
SE la chiave cercata è uguale a quella del record
ALLORA
restituisci “Chiave trovata”
ALTRIMENTI
SE ci sono altri record da esaminare
ALLORA
SE la chiave cercata è maggiore di quella del record
ALLORA
Applica la ricerca binaria alla seconda metà della porzione
di archivio da esaminare
ALTRIMENTI
Applica la ricerca binaria alla prima porzione dell’archivio
da esaminare
FINESE
ALTRIMENTI
Restituisci “Chiave non trovata”
FINESE
FINESE
Restituisci l’esito della funzione
FINE
In sintesi:
RICERCA in archivi a
ORGANIZZAZIONE Sequenziale
e ACCESSO Diretto
Indirizzo
conosciuto
Indirizzo
sconosciuto
Archivio
ordinato
1
accesso
Archivio
disordinato
Successo
Insuccesso
Ricerca
binaria
Ricerca
interpolata
Ricerca
binaria
log2 N
log2 N (log2 N)
log2 N
log2 (log2 N)
Sia nel caso
medio sia in
quello pessimo
Solo se le chiavi
sono
uniformemente
distribuite
Sia nel caso
medio sia in
quello pessimo
Caso medio
Analogo all’accesso
sequenziale
Ricerca
interpolata
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
11
L’organizzazione
sequenziale con indice
il libro si estende sul web
LEZIONE
Gli archivi registrati su supporti fisici che permettono l’accesso diretto possono essere gestiti anche con una variante dell’organizzazione sequenziale, caratterizzata
dalla possibilità di velocizzare la ricerca di un record mediante uno o più indici.
Nell’organizzazione sequenziale a indici (indexed sequential) si possono distinguere due elementi fondamentali:
• un archivio primario, caratterizzato da record consecutivi che possono anche
essere ordinati;
• un archivio secondario o indice ordinato (dizionario) o una gerarchia di indici, i cui elementi sono composti, generalmente, da due campi:
– un campo chiave, contenente la chiave del record;
– un campo puntatore, contenente la posizione del record all’interno dell’archivio primario.
Questa tipologia di organizzazione prevede, quindi, la suddivisione del file in
gruppi di record e la conservazione della chiave, la maggiore o la minore tra tutte
quelle dei record presenti in ciascun gruppo, in una sovrastruttura di indici che diventa un vero e proprio file di indici distinto da quello dei dati. L’acceso indicizzato a un record avviene in due fasi: prima si ricerca nel file di indici quello del gruppo che lo contiene e poi si leggono in modo sequenziale tutti i record del gruppo
fino a raggiungere quello cercato.
L’indice, quindi, consente di stabilire una corrispondenza tra ogni chiave e la posizione del relativo record memorizzato nell’archivio.
Analizziamo la seguente figura. Si nota come l’indice debba contenere necessariamente tutte le chiavi presenti nell’archivio primario. Per cercare un record di
cui si conosce la chiave, si cerca questa nell’indice; se esiste, tramite il puntatore,
si accede direttamente all’archivio primario.
Chiave
A
B
D
E
F
G
Puntat.
8
5
6
9
2
4
O
X
Z
7
1
3
Parte informativa
Informazioni su X
2
3
4
5
6
Chiave
X
F
Z
G
B
D
7
8
9
O
A
E
Informazioni su O
1
Indice ordinato (dizionario)
Informazioni su Z
Archivio primario
Questa soluzione è dispendiosa sia in termini di occupazione di memoria, sia di
gestione delle informazioni. Per sfruttare la totalità dei vantaggi offerti da questo
tipo di organizzazione, e in particolare potenziare le operazioni di ricerca dei record, occorre innanzitutto distinguere fra:
• strutture sequenziali con indice ordinate;
• strutture sequenziali con indice non ordinate;
e tenere conto del metodo di costituzione dell’indice.
12
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
L’organizzazione sequenziale con indice
LEZIONE 4
Nelle strutture ordinate, l’archivio primario viene implementato in una struttura a
pagine (o sottoarchivi che sono costituiti da blocchi contigui con ugual numero di
record) e l’indirizzo della chiave più alta di ciascun sottoarchivio è contenuto nell’indice i cui record sono del tipo:
(Kh, P)
dove Kh indica la chiave più alta e P il numero di sottoarchivio.
In questo modo, quindi, l’indice viene utilizzato esclusivamente per la ricerca dei
vari sottoarchivi. Analizziamo la seguente figura:
Chiave
Altri dati
2
5
20
...
...
...
48
52
85
...
...
...
125
154
190
...
...
...
199
211
214
...
...
...
Sottoarchivio
1
Sottoarchivio
2
Chiave
20
85
190
214
Puntat.
1
2
3
4
Sottoarchivio
3
Sottoarchivio
4
In pratica, il valore della chiave nell’indice indica esplicitamente la chiave di valore più alto contenuta all’interno del sottoarchivio, mentre il puntatore indica implicitamente la posizione della chiave più bassa poiché rappresenta l’indirizzo del
sottoarchivio e, quindi, il primo record presente, cioè quello con la chiave di valore più basso.
Generalmente, la ricerca di una chiave K avviene rispettando la seguente procedura:
• ricerca nell’indice la prima chiave Kh ≥ K
• accedi al sottoarchivio P associato alla chiave Kh
• ricerca la chiave K nel sottoarchivio P
La ricerca all’interno dell’archivio indice può avvenire con qualsiasi metodo di ricerca (sequenziale, binaria, interpolata e così via). In questo tipo di organizzazione, la chiave Kh ha la stessa funzione svolta dalla parola riportata nella parte più
alta di ogni dizionario. Ricordiamo che, nella precedente figura, le frecce che collegano i sottoarchivi sono state appositamente inserite per suggerire che, nonostante la suddivisione, è possibile eseguire la scansione sequenziale dell’archivio
primario utilizzando diverse tecniche. Si può, ad esempio, ricorrere a un puntatore esplicito, per mezzo dello stesso archivio indice, oppure sfruttare la contiguità
delle pagine.
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
13
L’organizzazione
sequenziale con indice:
l’aggiornamento
il libro si estende sul web
LEZIONE
Poiché l’archivio primario è pur sempre un archivio sequenziale, le operazioni che
comportano qualche problema nella loro implementazione sono quelle di inserimento e di cancellazione di record, le quali richiedono successive riorganizzazioni
dell’archivio. Queste operazioni vengono eseguite nello stesso modo previsto per
l’organizzazione sequenziale, ossia servendosi di apposite aree di overflow.
Una tra le tecniche più frequentemente utilizzate prevede che il record dell’archivio indice sia così strutturato:
(Kh, P, Kovf, Povf)
dove Kovf e Povf indicano, rispettivamente, la chiave più alta presente nell’area di
overflow e il puntatore di accesso a tale area.
Durante l’esecuzione delle varie operazioni logiche relative a un record di chiave
K, l’area di overflow sarà consultata solo se la pagina P è piena e se la chiave K risulta compresa tra Kh e Kovf.
Riprendiamo l’esempio riportato nella precedente lezione e proviamo a inserire il
record di chiave 58. L’inserimento verrà effettuato nel sottoarchivio 2 che, essendo pieno, provocherà il trabocco del record di chiave 85.
Dopo l’inserimento la situazione sarà la seguente:
Chiave
Altri
dati
1
2
5
20
...
...
...
...
Sottoarchivio
2
48
52
58
...
...
...
...
Sottoarchivio
3
125
154
190
...
...
...
...
Sottoarchivio
4
199
211
214
...
...
...
...
85
...
...
...
...
Sottoarchivio
Chiave
20
58
190
214
Punt.
1
2
3
4
Kovf
Nil
85
Nil
Nil
Povf
Nil
5
Nil
Nil
Sottoarchivio
5
(overflow)
14
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
L’organizzazione sequenziale con indice:
l’aggiornamento
LEZIONE 5
Riportiamo la soluzione di massima relativa all’operazione di inserimento appena compiuta.
Siano:
• Kh’ la penultima chiave presente nella pagina Pag;
• Ktrab la chiave traboccata.
PROCEDURA Inserisci
INIZIO
Ricerca nell’archivio indice la prima chiave Kh o Kovf che è più grande di K
SE(K < Kh)
ALLORA
Inserisci il record nella pagina Pag rispettando l’ordinamento
SE c’è trabocco di pagina
ALLORA
Inserisci il record traboccato in testa all’area di overflow
SE è il primo trabocco
ALLORA
Sostituisci nell’archivio indice (Kh, Pag, Nil, Nil)
con (Kh’, Pag, Ktrab, Povf)
ALTRIMENTI
Sostituisci nell’archivio indice Kh con Kh’
FINESE
FINESE
ALTRIMENTI
Inserisci il record nell’area di overflow rispettando l’ordinamento
FINESE
FINE
Ricordiamo, infine, che l’allocazione e l’organizzazione dell’area di overflow possono variare in funzione del metodo implementativo adottato. Una delle possibili soluzioni prevede di riservare un sottoarchivio di overflow ogni N sottoarchivi
dell’archivio primario.
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
15
il libro si estende sul web
LEZIONE
Indici multipli
o a più livelli
Nel caso in cui il numero di sottoarchivi diventi rilevante e, di conseguenza, il numero di record presenti nell’indice cominci a divenire considerevole (appesantendo la ricerca), è possibile organizzare l’indice a sua volta come un archivio sequenziale con indice. Si dà così luogo a sottoindici di differente livello, che
permettono di ottenere una diminuzione del tempo di scansione dell’indice stesso. In presenza di più livelli di indice, nella fase di ricerca la gerarchia viene utilizzata per poter individuare (partendo da un indice a livello k) quale indice a livello
k + 1 debba essere esaminato al fine di selezionare il sottoarchivio all’interno del
quale si trova il record cercato.
Per comprendere l’uso degli indici a più livelli, si può fare riferimento al reperimento di un’informazione di un volume mediante il suo indice analitico. Un indice analitico è composto da un insieme di termini accanto ai quali è specificata la
pagina del libro all’interno della quale essi sono trattati.
I vari termini sono ordinati alfabeticamente e sono raggruppati secondo le lettere dell’alfabeto con la quale iniziano. Se, ad esempio, si vuole ricercare il termine
indice, si procede nel seguente modo:
1.. si ricerca la lettera i;
2. nel blocco che racchiude tutti i termini che iniziano con i, si ricerca il termine
indice e si preleva il numero di pagina;
3. si apre il libro alla pagina ottenuta e si leggono le informazioni.
Questa struttura è, quindi, un valido esempio di indici multipli: il primo livello è
rappresentato dalle lettere dell’alfabeto, il secondo livello è costituito da tanti indici quante sono le lettere e ciascun indice è composto da tutti i termini che iniziano con la lettera collegata.
Talvolta, questo tipo di organizzazione viene utilizzato su hard disk, cioè su supporti a disco di tipo disk-pack, al fine di ottimizzare i movimenti del pettine.
Generalmente, un’organizzazione sequenziale con indice utilizza tre livelli di indice, in particolare:
• un indice di unità, che consente di determinare su quale unità di memoria secondaria occorre ricercare il record, nel caso in cui l’archivio sia memorizzato
su più unità;
• per ogni unità, un indice di cilindro che consente di determinare su quale cilindro dell’unità deve avvenire la ricerca;
• per ogni cilindro, un indice di traccia che consente di determinare su quale
traccia di quel cilindro deve avvenire la ricerca.
Nel caso di strutture non ordinate, l’indice è più complesso e può essere articolato anche su più livelli. Tuttavia, nonostante il numero di indici e le loro dimensioni ragguardevoli, la gestione non ordinata facilita notevolmente l’operazione di
inserimento, poiché nuovi record saranno semplicemente aggiunti in coda all’archivio primario, senza che si verifichino appesantimenti dovuti alla gestione delle aree di overflow.
16
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
Indici multipli o a più livelli
INDICE AL
LIVELLO 1
INDICE AL
LIVELLO 2
LEZIONE 6
INDICE AL
LIVELLO 3
ARCHIVO
PRIMARIO
...
5
98
152
2
152
21 5
527
900
2
3
4
1154
1896
9
10
2380
2585
11
12
4
4931
5650
6888
7590
6
202
21 5
114
115
250
527
116
117
850
900
118
119
1000
1154
120
121
112
12
15
25
54
64
72
98
...
...
...
...
...
...
...
7
3
1
900
2585
7590
5
6
7
8
112
113
8
113
102
120
125
130
132
140
152
...
...
...
...
...
...
...
9
13
14
15
16
114
160
200
201
202
...
...
...
...
...
...
...
16
6520
7590
140
141
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
17
Tutto in test...a
PROVE OGGETTIVE PER LA VERIFICA DELLE CONOSCENZE
1. Che cos’è un archivio sequenziale?
8. Quando un archivio sequenziale viene detto seriale?
2. Quali sono le caratteristiche fondamentali dell’organizzazione sequenziale?
9. Su un archivio sequenziale non ordinato, l’inserimento
non comporta problemi. Che cosa significa?
10. In fase di inserimento i problemi sorgono se l’archivio
sequenziale è ordinato. Che cosa significa?
3. Un file di testo
a
contiene solo semplici caratteri di scrittura
b
non necessita di sofisticati word processor per
la sua lettura
c
non può contenere simboli di punteggiatura
d
non può contenere numeri
11. Stabilisci se le seguenti affermazioni sono vere o false
in un archivio sequenziale ad accesso
diretto la ricerca sequenziale effettua
log2N accessi --------------------------------------------------------- V F
b nell’organizzazione ad indici si distinguono
tre elementi fondamentali ---------------------------------- V F
c le strutture sequenziali possono essere ordinate
o no ---------------------------------------------------------------------------- V F
d su archivi sequenziali è possibile effettuare la
cancellazione logica---------------------------------------------- V F
a
4. Che cosa sono i file ini?
5. Che cosa differenzia il linguaggio HTML dal linguaggio
XML?
12. Che cosa sono le aree di overflow (dette anche aree
dei trabocchi)?
6. I file binari
a
non sono direttamente leggibili dall’utente
b
possono essere letti solo con word processor
sofisticati
c
possono essere letti con qualsiasi word
processor
d
contengono una sequenza di numeri decimali
13. Che cosa sono le aree di overflow distribuito?
14. Che cosa sono le aree di overlow concentrato?
15. Stabilisci se le seguenti affermazioni sono vere o false
7. Stabilisci se le seguenti affermazioni sono vere o false:
in un archivio sequenziale l’ordinamento
logico può coincidere con l’ordinamento
fisico -------------------------------------------------------------------------b quando l’ordinamento, logico coincide
con quello fisico l’archivio viene detto
sequenziale puro --------------------------------------------------c le operazioni consentite su un archivio ad
organizzazione sequenziale sono la lettura,
la scrittura e la riscrittura ----------------------------------d la fase di aggiornamento consente
di apportare delle modifiche ai campi
di un record ad eccezione della chiave ----------
a
a
V
F
V
F
V
F
b
nell’organizzazione ad indici, il dizionario
può non essere ordinato------------------------------------gli indici possono essere gestiti solo su
dispositivi ad accesso diretto ---------------------------
V
F
V
F
16. In un’organizzazione a indice, quando si parla di archivio primario non paginato?
17. In un’organizzazione a indice, quando è necessario utilizzare i sottoarchivi?
V
F
18. Generalmente, un’organizzazione sequenziale con indice quanti livelli di indice utilizza?
18
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
Diamoci il voto!!!
Con questa scheda puoi autovalutare il tuo livello di acquisizione delle conoscenze e delle abilità insegnate nell’Unità formativa. Attribuisci un punto a ogni risposta esatta. Se totalizzi un punteggio:
<4
Tra 4 e 6
Rifletti un po’ sulle tue
“disgrazie”
Rivedi l’unità formativa
nelle sue linee generali
Rivedi con attenzione
tutta l’unità formativa
Ripeti il questionario
Tra 6 e 8
Rivedi l’unità formativa
nelle sue linee generali
>8
Tutto OK
Ripeti il questionario
1.
Nell’allocazione contigua:
6.
i file sono memorizzati uno di seguito all’altro,
ossia in ordine sequenziale
b i blocchi che costituiscono il file non sono
memorizzati uno di seguito all’altro
c i blocchi che costituiscono il file sono
memorizzati uno di seguito all’altro, ossia in
ordine sequenziale
d nessuna delle precedenti è corretta
a
2.
Nell’allocazione contigua, la ricerca dello spazio più
grande per contenere il file da parte del sistema operativo avviene grazie alla tecnica:
può essere svolto in due modi diversi dipendenti
dal metodo di accesso.
b può essere svolto solo riscrivendo l’intero
archivio se l’accesso è sequenziale
c non può essere eseguita se l’organizzazione è
ad accesso diretto
d non può comunque essere fatto su archivi
sequenziali
a
7.
può essere implementata su qualsiasi supporto
fisico
b può essere implementata solo su supporti fisici
che permettono l’accesso diretto
c può essere implementata solo su nastri
d nessuna delle precedenti è corretta
best-fit
worst-fit
c nest-fit
d first-fit
b
4.
Nell’allocazione contigua:
a
qualsiasi tecnica di gestione del disco è valida
b
qualsiasi tecnica si utilizzi, però, sorgeranno dei
problemi
c
il disco non sarà mai frammentato
d
si arriverà a una situazione in cui non esisterà
uno spazio contiguo abbastanza capiente da
contenere il file nonostante lo spazio libero sia
maggiore di quello necessario.
La sigla CSV fa riferimento:
a un formato per Internet
b a un formato per file di testo utilizzato per lo
scambio di dati tra sistemi differenti che
operano su piattaforme incompatibili
c a un formato per file di testo in cui i campi sono
separati da virgole
d a un formato per file di testo in cui i campi sono
separati da trattini
a
5.
L’organizzazione sequenziale con indice:
a
a
3.
L’aggiornamento di un archivio sequenziale:
L’archivio differenziale:
è un file XML
b è un file binario
c è un file che non può essere cancellato
d è un file temporaneo
a
8.
Nell’organizzazione sequenziale con indice, l’archivio
secondario è anche detto:
archivio indice ordinato
dizionario
c chiave primaria
d archivio differenziale
a
b
9.
Nell’organizzazione sequenziale con indice, l’indice
consente di stabilire:
una corrispondenza tra una sola chiave e la
posizione del relativo record nell’archivio
b una corrispondenza tra ogni chiave e la
posizione del relativo record nell’archivio
c una corrispondenza tra un campo del record e la
sua posizione nell’archivio
d una corrispondenza tra un archivio e il file
associato
a
10. Gli indici a più livelli sono utilizzati quando:
il numero di sottoarchivi diventa rilevante
i campi sono molti
c i record sono composti da un solo campo
d il numero di record presenti nell’indice diviene
notevole e appesantisce la ricerca
a
b
P. Gallo F. Salerno Task 2 – Gli archivi sequenziali
19