Gli Archivi
Un archivio è un insieme organizzato di informazioni caratterizzate da alcune proprietà:
- tra esse esiste un nesso logico (cioè sono in qualche modo inerenti ad un medesimo
argomento)
- sono rappresentate secondo un formato che ne rende possibile l’interpretazione
- sono registrate con un supporto su cui è possibile scrivere e rileggere informazioni anche a
distanza di tempo
- sono organizzate in modo da permettere una facile consultazione
Nella società moderna, con il crescere del volume delle informazioni e dell’importanza di renderle disponibili in tempi
rapidi, la facile reperibilità dei dati è diventata una caratteristica fondamentale degli archivi gestiti da un calcolatore è
diventata la prassi nella quasi totalità delle attività organizzate
1
Operazioni sugli archivi
La gestione di un archivio di dati viene realizzata attraverso le seguenti operazioni principali:
-La creazione dell’archivio stessa, cioè tutto ciò che riguarda la realizzazione, sul supporto di
memorizzazione dello spazio destinato a contenere i dati
- la consultazione o interrogazione, cioè il reperimento all’interno dell’archivio delle informazioni
necessarie per l’elaborazione desiderata. Es. L’archivio della contabilità di un azienda viene
interrogato per conoscere quali sono le fatture emesse che non sono ancora state pagate dai clienti
- l’inserimento di nuovi dati dopo che l’archivio è stato creato: es. l’inserimento di un nuovo
abbonato nell’elenco telefonico…..
- la modifica o aggiornamento dei dati già presenti nell’archivio ma non più corrispondenti ai dati
reali: se un utente trasferisce la propria residenza nella successiva edizione dell’elenco telefonico
viene stampato il nuovo indirizzo
- la cancellazione delle informazioni che non si vogliono più conservare perché non esiste più un
nesso logico rispetto alle altre informazioni presenti nell’archivio
- l’ordinamento dei dati secondo un determinato criterio per facilitare una facile consultazione
- la fusione tra due o più archivi, cioè la formazione di un nuovo archivio utilizzando i dati contenuti
negli archivi di partenza
2
In un archivio le informazioni sono raggruppate secondo un’unità logica: nel caso dell’elenco telefonico i dati
relativi ad ogni abbonato, in un archivio notarile i dati contenuti nell’incartamento relativo a un cliente. Questi insiemi di
informazioni logicamente organizzate e riferite a un unico soggetto vengono chiamati record
(registrazione); le singole informazioni che compongono il record si chiamano campi; l’elenco dei
campi che lo compongono viene detto tracciato del record. Es il tracciato record dell’archivio
costituito dall’elenco telefonico può essere descritto con i seguenti campi: cognome, titolo
professionale, nome, altre descrizioni, indirizzo, numero di telefono.
La creazione di un archivio richiede la definizione delle seguenti specifiche:
- nome dell’archivio, che lo identifica e serve a ricordarne il contenuto
- tracciato record (quali informazioni compongono il record)
- supporto da usare per archiviare i dati (fogli di carta, dischi o nastri magnetici, dischi ottici)
- dimensione massima dell’archivio (es. num. di abbonati in un elenco telefonico)
- il modo con cui i dati sono strutturati e collegati tra loro cioè l’organizzazione dell’archivio
La decisione su queste specifiche fa parte dell’analisi del problema e deve precedere la fase di
realizzazione fisica dell’archivio.
3
Supporti fisici
Per ragioni di velocità nella ricerca e nell’elaborazione dei dati e di spazio nella loro memorizzazione,
si è passati da archivi registrati su supporti cartacei contenuti in armadi a supporti ideati per essere
trattati in modo automatico dai computer. Gli archivi memorizzati su tali supporti vengono detti file
(anche se in informatica questo termine serve a indicare in modo generico qualsiasi informazione che
può essere registrata sui supporti di memoria, come un testo, un programma, un comando di S.O….)
Nelle procedure gestionali gli archivi sono costituiti da insiemi di record omogenei, nel senso che
ciascun archivio possiede un tracciato predefinito e uguale per tutti i record in esso contenuti (file di
record). Le apparecchiature atte a leggere e scrivere informazioni contenute nei file vengono dette
periferiche.
Oltre ai file con record a lunghezza fissa esistono file con record a lunghezza variabile: in essi è
necessario trovare un modo per specificare la posizione dove termina il singolo record (end of record).
Ci sono fondamentalmente due modi per risolvere il problema: il numero di caratteri in ogni record è
indicato in un campo di dimensione fissa all’interno del record stesso, in alternativa ogni record è
seguito da una speciale sequenza per indicare la fine del medesimo (es. in DOS impiega la coppia di
caratteri ASCII 13 e 10)
4
Le memorie di massa
Per molti anni la scheda perforata è stata il più diffuso supporto per la registrazione dei dati. Gli
inconvenienti delle schede perforate sono stati superati dai nastri e dischi magnetici. La loro adozione
ha portato all’uso sempre più esteso di supporti di grandi capacità che prendono il nome di memorie
di massa. Si chiamano anche memorie ausiliarie perché costituiscono un’estensione della memoria
centrale e consentono la permanenza delle registrazioni.
Rispetto ai nastri magnetici che permettono solo l’accesso sequenziali alle informazioni (la lettura di
un record implica la lettura di tutti i record che lo precedono) il disco permette l’accesso diretto
(random) al singolo blocco di dati.
Le memorie di massa sono caratterizzate da alcuni parametri fondamentali:
-il tipo di accesso ai dati che può essere diretto come nei dischi, o sequenziale come nei nastri
- la capacità: la quantità di dati che il supporto è in grado di contenere (MB, GB, TB)
- il tempo medio di accesso (access time): tempo medio necessario per ritrovare i dati e trasferirli
nell’unità centrale (ms)
- la velocità di trasferimento dei dati (transfer rate) dalla memoria di massa alla memoria centrale
(KB/sec, MB/sec)
5
Ci sono poi alcune caratteristiche delle memorie di massa che devono essere prese in considerazione:
-la compatibilità, cioè la possibilità di utilizzare i drive e i supporti su un determinato sistema di
elaborazione, rendendo disponibili i dati in esso contenuti alle altre unità del sistema
- la gestione del fault tolerance (tolleranza al guasto), con il quale si prevede la possibilità di duplicare
i sistemi di memorizzazione o parti di esse, per consentire di continuare il lavoro di elaborazione dei
dati, anche se uno dei due si rovina
- la garanzia della sicurezza e dell’integrità dei dati, nei confronti dei rischi di cancellazioni
accidentali, della modifica indesiderata dei dati registrati, di effetti dannosi provocati da fenomeni fisici
o ambientali, di interventi distruttivi esterni (virus o pirati dell’informatica)
- l’operatività, cioè la facilità d’uso da parte dell’operatore e la diminuzione dei tempi dovuti alla
sostituzione di dischi e nastri
- la durata delle registrazioni sui supporti nel tempo
- l’utilizzo di memorie di tipo diverso (dischi, nastri e dischi ottici) nello stesso sistema di
elaborazione, integrando diverse tecnologie di memorizzazione per le registrazioni e nelle operazioni
per le copie di salvataggio
- il trasferimento dei dati, organizzati nei file e memorizzati sui supporti, da un sistema di elaborazione
a un altro, avente anche S.O. diverso
- l’espansione delle unità di memorie di massa, con l’aggiunta di nuove unità o con l’uso di supporti di
maggiori capacità
- il costo dei drive, dei supporti e del sw di gestione
6
Il nastro magnetico e l’unità a nastri
Il nastro magnetico (streaming tape) è formato da una lunga striscia di materiale plastico, ricoperta da
materiale ferromagnetico. La superficie del nastro è suddivisa in nove piste longitudinali: otto piste
servono per memorizzare i bit di un byte e una pista per il bit di parità. La superficie è suddivisa in molte
colonne (frame) 8+1 caselle magnetizzate in modo N-S o S-N (bit 1 oppure 0)
P
I
S
T
e
frame
La capacità di memorizzazione del singolo nastro è dell’ordine di alcuno GB fino a diversi centinaia
di GB. La capacità dipende dalla quantità di bit che possono essere registrati in un pollice bpi (bits
per inch). La velocità di trasferimento dei dati è dello stesso ordine di grandezza dei dischi (decine o
centinaia di MB/sec). Una bobina di nastro magnetico viene chiamata volume. Le informazioni che
permettono l’identificazione e il controllo di un nastro e dei file in esso registrati, sono contenute in
particolari gruppi di caratteri detti label.
7
Le label più significative sono:
- la label di volume che è il primo blocco registrato sul nastro, contenente informazioni atte a
identificare la bobina (es. nome del proprietario….)
- la label di file, che è posta all’inizio del file, contiene informazioni sul nome e il codice del file, la
data di registrazione, il n. d’ordine della bobina nel caso nel caso che il file sia multivolume
-La label di fine file, è il blocco contenente il gruppo di caratteri che chiude ogni file
- la label di fine volume, è posta alla fine di un nastro per indicare che è terminata la bobina
Oltre a questi blocchi informativi, sul nastro vengono registrati blocchi di un solo carattere, detti tape
mark ™, per il controllo del nastro. Esistono tratti non registrati che separano un blocco dall’altro
detti gap.
L’uso dei nastri è conveniente per l’alto numero di informazioni immagazzinate con scarso ingombro e
per il basso costo delle bobine stesse. Svantaggi sono invece le probabili alterazioni della
magnetizzazione e soprattutto l’accesso sequenziale alle informazioni.
Conviene usare i nastri per memorizzare i file da consultare non frequentemente (archivi storici), per le
copie di sicurezza dei dischi (copie di backup),
8
Il disco magnetico e l’unità a dischi
I disco magnetico è costituito da un sottile disco metallico con le facce ricoperte da materiale
magnetizzabile. Più dischi possono essere montati su un medesimo asse centrale intorno al quale
ruotano con velocità uniforme (disk-pack). Le due facce del disco (superfici) sono suddivise in piste
(tracce) concentriche, le quali a loro volta sono divise in settori (tipicamente di 512 byte). I settori
sono separati da gap. L’insieme delle piste a uguale distanza dal centro viene detto cilindro. Un
gruppo di settori di un disco si chiama cluster e costituisce la quantità di dati che viene effettivamente
trasferita in un operazione di I/O da disco.
9
Contrariamente alle testine delle unità a nastro, le testine delle unità a dischi non sono a diretto contatto
con la superficie del disco bensì a una distanza inferiore al millesimo di millimetro; questo fatto
permette velocità di rotazione dell’ordine delle migliaia di giri al minuto ed evita fenomeni di usura. In
ogni settore sono presenti: informazioni per identificare il settore, informazioni per dichiarare il settore
difettoso e non più utilizzabile, i dati accessibili dall’utente, codici di controllo per garantire l’integrità
dei dati, gap di separazione tra i settori. Tali informazioni sono memorizzate sul disco nel corso della
sua formattazione a basso livello (attualmente effettuata direttamente dal costruttore del disco).
Vi è anche una formattazione ad alto livello, effettuata dall’utente, che prepara il disco per essere
utilizzato secondo le richieste del file system del S.O.
Nei dischi magnetici si parla di accesso diretto alle informazioni in quanto l’accesso a un blocco è
indipendente dalla posizione degli altri e il tempo di accesso è indipendente dalla posizione del blocco
sul disco: per poter accedere in lettura o scrittura al blocco contenente il record desiderato occorre
specificare il numero del cilindro, il numero della testina e il numero del settore che identifica una
posizione nell’ambito di una specifica traccia.
Il tempo di ritrovamento dei dati risulta formato dal:
-tempo di posizionamento del braccio (seek time). Varia in funzione del numero di tracce che devono essere
attraversate per posizionarsi sul cilindro desiderato ( da 0,2 – 0,6 ms per traccia attraversata)
- tempo di latenza rotazionale, cioè il tempo occorrente perché il settore cercato passi sotto la testina. Mediamente è
pari al tempo necessario per compiere mezza rotazione del disco e dipende dalla sua velocità di rotazione (da 2 a 8
ms). La somma dei due tempi costituisce il tempo di accesso e assume valori compresi tra 5 e 10 ms. La velocità di
trasferimento dei dati varia tra 10 MB/sec e 300 MB/sec.
La capacità dei dischi varia da alcune decine ad alcune centinaia di gigabyte per singolo drive. I dischi moderni hanno
densità lineare superiore a 350.000 bit per inch e una densità di traccia superiore a 15.000 tracce per inch.
10
I dischi ottici
I CD-ROM sono basati sulla medesima tecnologia dei CD musicali (compact Disk) musicali. Lo standard
del CD-ROM è stato definito nel 1984 e ha portato allo sviluppo di una serie di dischi ottici per realizzare
memorie di massa rimovibili, di sola lettura, a basso costo e di facile duplicabilità. In lettura un raggio
laser a bassa potenza invia un raggio che viene riflesso dalla superficie del disco in modo differente, a
seconda delle depressioni presenti sulla superficie, permettendo il riconoscimento di due stati distinti. Il
passaggio da uno stato all’altro viene riconosciuto come un 1, l’assenza di cambiamento è associata
invece allo 0.
Le informazioni sono disposte sul disco, con densità lineare costante, su un’unica traccia a forma di
spirale che parte dal centro del disco verso l’esterno. Se il numero di bit per cm è lo stesso nelle tracce
interno e nelle tracce esterne, il disco deve ridurre la velocità angolare nel passare dalle tracce più interne
della spirale a quelle più esterne per permettere lo scorrimento delle informazioni alla velocità costante di
1,2 m/sec.
I dati sono distribuiti in un’unica traccia che contiene 333.000 settori di 2352 byte l’uno. Ogni settore
inizia con un preambolo di 16 byte che serve a riconoscere l’inizio di un nuovo settore e la sua
identificazione.
La capacità di un CD-ROM è di 333.000 x 2048( 288 byte contengono un codice a correzione d’errore) =
650MB.
11
I primi lettori operavano alla velocità di 150 KBps (Kilobytes per secondo) indicata con 1X. Le velocità
dei lettori prodotti successivamente sono indicate con i multipli di quella velocità.
Le caratteristiche più interessanti sono date dalla non modificabilità delle informazioni memorizzate,
dalla rimovibilità del supporto e dalla loro duplicabilità a basso costo per elevati volumi di copiatura.
I dischi ottici sono disponibili anche nelle versioni che ne consentono la scrittura e la riscrittura (con
masterizzatori). La tecnica di registrazione dei dati utilizza il riscaldamento prodotto da un raggio laser
ad alta potenza e consiste nello scorrimento di punti della superficie colorata del disco che vengono così
resi opachi e nello sfruttamento delle proprietà riflettenti dello strato dorato sottostante. La superficie
del disco esposta al laser può quindi passare da uno strato amorfo (opaco) a uno strato cristallino
(trasparente) e viceversa.
E’ possibile fare registrazioni in multisessione aggiungendo dati in momenti successivi.
Negli anni più recenti la tecnologia ha creato i nuovi lettori e i nuovi supporti per la tecnologia DVD
(Digital Versatile Disc). La capacità di memorizzazione di un disco DVD può essere di 4,7 GB su uno
dei suoi lati (corrispondenti a circa 133 minuti di filmato). Alcuni dischi DVD poi sono non solo a
doppia faccia (9,4 GB), ma anche a doppia densità di registrazione (8,5 GB su un solo lato), poi
possono potenzialmente contenere circa 17 GB di video, audio o altri dati.
I dischi ottici presentano come vantaggi:
- l’accesso random che li rende preferibili ai nastri, per i quali l’accesso è solo sequenziale
- le discrete capacità che li rendono particolarmente adatti nelle applicazioni che prevedono l’uso di
archivi di grandi dimensioni aggiornati raramente
- l’affidabilità, anche con frequenti operazioni di accesso.
12
L’alto tempo di accesso è dell’ordine di diverse centinaia di millisecondi, e il transfer rate massimo di
7,6 MB/sec.
Elementi caratterizzanti di CD-ROM e DVD sono:
- l’essere memorie stabili, a sola lettura, molto affidabili
- l’essere memorie rimuovibili e , di conseguenza, trasportabili e immagazzinabili
- la possibilità di duplicare i contenuti di un disco ottico in migliaia di copie a basso costo e a grande
velocità
- la discreta capacità e il basso costo del volume
Di conseguenza i dischi ottici risultano adatti nelle seguenti applicazioni:
- registrazione di documenti originali e ritrovamento in modo facile
- costruzioni di grande archivi integrati
- versione elettronica di manuali tecnici
- distribuzione di programmi didattici per l’apprendimento delle discipline
- archiviazione di dati storici: es. analisi mediche, bilanci, posta…
- applicazioni editoriali quali: versioni elettroniche di dizionari, enciclopedie, atlanti, stradali
- distribuzione di sw e relativi manuali
13
Le copie di sicurezza
E’ assolutamente necessario tenere più di una copia degli archivi, ovviamente su supporti diversi e non
nel medesimo ambiente: le copie di sicurezza o di backup.
Il procedimento inverso per ricuperare i dati da una copia precedente si chiama restore.
Di solito la copia dei dischi viene effettuata su nastri (nastri di piccole dimensioni ma dalla capacità di
svariati GB (cartridge o cartucce) che hanno sostituito i tradizionali nastri a bobina). Nei piccoli
sistemi la copia avviene anche da disco a disco Zip, oppure a disco ottico riscrivibile.
La copia deve essere fatta con regolarità e con frequenza legata alla quantità di lavoro che viene
effettuata. Alcune tecniche di backup prevedono la possibilità di copiare solamente quei file che sono
stati modificati di recente, attraverso un controllo sulla data di creazione o dell’ultima modifica, senza
dover effettuare integralmente la copia di tutti i file.
Un’altra precauzione da adottare in merito alla sicurezza dei dati, consiste nell’utilizzo di un gruppo di
continuità, detto UPS (Uninterruptible Power Supply), che serve a proteggere il computer da
inconvenienti sulla rete elettrica, quali cadute di tensioni o interruzione temporanee di energia elettrica.
14
Fault tolerance
Nelle situazioni dove non è consentita l’interruzione dell’attività di un sistema di elaborazione, come
per es. in una banca o nel caso di un server Internet, la sicurezza viene garantita anche nella parte hw
attraverso la duplicazione di parti o dell’intero sistema: queste tecniche vengono indicate con il termine
fault tolerance (tolleranza del guasto) e riguardano principalmente la memoria di massa nei server
delle reti.
Il fault tolerance viene realizzato a livelli diversi:
- il metodo più semplice si chiama mirroring e consente di avere nelle unità di memoria di massa due
copie identiche dello stesso disco; quando un’operazione di I/O riscontra un errore, l’elaborazione non
viene interrotta potendo essa utilizzare la copia alternativa. Le operazioni di lettura vengono eseguite
sulla copia disponibile, mentre le operazioni di scrittura vengono effettuate due volte sulle due copie.
- un secondo livello di tolleranza del guasto viene realizzato con la tecnica del duplexing, che consiste
nella duplicazione dell’unità di controllo dei dischi (controller) oltre che dei dischi. L’utente può
continuare l’attività di elaborazione anche nel caso di guasto al controller o al disco
- il terzo livello di fault tolerance riguarda la duplicazione dell’intero sistema, del server nel caso di reti
locali, e del mainframe nel caso di un sistema di grandi dimensioni. Viene garantita la continuità del
lavoro a fronte di un guasto a una qualsiasi delle parti del sistema: alimentatore, CPU, schede, bus,
15
unità a disco, controller (costi raddoppiati).
RAID
La tecnologia dei dischi RAID (Redundant Array of Inexpensive Disk) mette a disposizione ulteriori
tecniche di tolleranza ai guasti. Distribuendo le informazioni su un array di più dischi si puo pensare
di operare i trasferimenti da e verso i dischi in parallelo aumentando il transfer rate di tante volte
quante sono i dischi. Per il S.O. l’array RAID è un disco logico con il quale opera in modo
tradizionale; il controller del disco RAID provvede a parallelizzare le letture e le scritture su più
dischi. La tecnologia dei dischi RAID può essere sfruttata per realizzare tecniche alternative alla
duplicazione dei dischi. Per es., nel caso in cui la serie RAID sia costituita da cinque dischi, quattro
contengono i dati, mentre il quinto garantisce la ridondanza e viene utilizzato come disco di parità.
La tecnica RAID sopporta il guasto di un disco in questo modo:
- se il malfunzionamento riguarda il disco di parità, i dati vengono letti dagli altri dischi e il disco di
parità viene ricostruito, su uno nuovo, utilizzando gli algoritmi di parità
- se, invece, il guasto si riferisce a uno dei dischi della serie, i dati vengono costruiti sulla base dei
dati presenti sugli altri dischi e delle informazioni di parità presenti sul disco di parità
Ci sono diverse modalità di usare un array di dischi RAID e sono indicate come: RAID0…,RAID6.
La modalità sopra descritta ricorda il RAID4. Gli schemi più diffusi sono il RAID1 che attua il
mirroring dei dischi, e il RAID5, una specie di RAID4 modificato per migliorare l’efficienza del
sistema in scrittura. Nello schema RAID5 i blocchi che contengono le informazioni di parità non
sono collocate su un unico disco, ma sono distribuite ciclicamente su tutti gli array, per evitare di
dover accedere sempre al medesimo disco per registrare i controlli di parità.
16
I vantaggi delle tecnologie RAID sono:
- l’unità centrale del computer vede comunque i dati che servono per
l’elaborazione in modo trasparente, anche nel caso di guasto a uno
dei supporti
- non ci sono tempi di downtime imprevisti dovuti al
malfunzionamento di una delle componenti
- il sistema può continuare a operare anche durante la sostituzione di
un componente danneggiata
- vengono ridotte al minimo le operazioni di manutenzione del
sistema non programmate
17
Il sw per la gestione dei file
Il modulo del sw di base che svolge le funzioni di gestore dei file viene chiamato file system. Esso è
l’insieme delle routine del sistema operativo che consentono all’utente-programmatore di usufruire
degli archivi sulle memorie di massa, senza preoccuparsi dei dettagli delle operazioni di I/O e facendo
riferimento ai file solo con nomi simbolici.
Infatti il file system regola l’organizzazione, l’assegnamento, la protezione e il ritrovamento di insiemi
di dati, cioè file.
In particolare esso svolge le seguenti funzioni:
- tiene traccia dei file, della loro posizione, del loro stato, usando particolari tabelle dette file directory
- decide secondo le richieste, le protezioni e i diritti di accesso a quale programma assegnare un file
- assegna un file al programma che lo ha richiesto
- toglie l’uso di un file a un programma rendendolo disponibile ad altri programmi
Quando il file system riceve da un programma la richiesta di leggere un record, questa richiesta viene
convertita nei comandi di lettura del blocco che contiene il record cercato. L’intero blocco viene letto
dal supporto fisico esterno e copiato in un area di memoria detta buffer di I/O
18
L’organizzazione degli archivi
Quando si progetta l’organizzazione dei dati in archivi spazio occupato e tempo di accesso devono
essere tenuti ben presenti:
- qual è l’organizzazione che consente di ritrovare i dati in modo sicuro e in tempi brevi?
- quanto spazio occorre riservare sul supporto di memoria di massa per gli archivi?
Occorre osservare anche che gli archivi possono aumentare le loro dimensioni nel tempo secondo due
direzioni: aumento del numero dei campi dei record per l’inserimento di nuove informazioni, e
aumento del numero di record per registrare una maggiore quantità di informazioni.
A questi problemi è stata data una risposta adeguata con i database, basati sull’importanza
dell’integrazione degli archivi, evitando ridondanze di registrazione, e sull’indipendenza dello schema
logico dei dati dalle implementazioni sw, dalle applicazioni che usano quei dati e dal modo con il quale
i dati sono fisicamente registrati su memoria di massa. Tutto questo rende più facile il lavoro di
manutenzione degli archivi nel tempo, dovuto a diversi motivi:
- eliminazione degli errori presenti negli archivi o nel sw che li gestiscono
- necessità di ampliare gli archivi in corrispondenza dell’aumento delle informazioni per un’azienda
che cresce nelle sue dimensioni
- adeguamento dei dati a disposizione e del sw applicativo a nuove norme legislative o fiscali
- conversione e adeguamento degli archivi per nuove piattaforme hw
19
I principali tipi di organizzazione
Di seguito vengono presentate le caratteristiche degli archivi secondo l’organizzazione tradizionale dei
dati (applicazioni che non utilizzano i database):
- organizzazione sequenziale: consiste nel registrare i record uno di seguito all’altro, in modo
sequenziale; in fase di lettura i record possono essere ritrovati scorrendo tutti i record del file a partire
dal primo.
Questo tipo di organizzazione, semplice da gestire, consente l’uso di record aventi lunghezza diversa
uno dall’altro. E’ evidente che l’organizzazione sequenziale presenta dei limiti in fase di ritrovamento
dei dati quando il numero dei record diventa elevato. Risulta invece un’organizzazione efficace per file
di piccole dimensioni, per es, file di testo, e che comunque possono essere pensati come un flusso di
caratteri (byte stream) intervallati da sequenze di caratteri che indicano la fine del record.
Un file ad organizzazione sequenziale può essere utilizzato solo per scrivere nuovi record, per leggere
record o per aggiungere record in coda a quelli già registrati. La scrittura di record a partire da una
qualsiasi posizione, eseguita su un file già esistente, provoca di norma la cancellazione di tutti i record
che lo seguono; la riscrittura dei record non è permessa.
20
Organizzazione ad accesso diretto
Se possiamo utilizzare record di lunghezza fissa (record del cliente, record dell’articolo di
magazzino….), si può pensare di associare a ogni record un numero d’ordine e ritrovare facilmente
all’interno del file il numero del primo carattere del record richiesto, considerando il file come una
sequenza di byte. Questo tipo di organizzazione si chiama diretta; si chiama anche random volendo
mettere in evidenza la contrapposizione all’organizzazione sequenziale, cioè l’utente può accedere al
record che interessa senza leggere tutti quelli che lo precedono.
In un archivio ad organizzazione diretta, ciascun record viene identificato dalla posizione che esso
occupa all’interno del file. Se i record vengono inseriti uno di seguito all’altro, il numero di record
viene assegnato aggiungendo una unità al numero dell’ultimo record registrato.
Organizzazione a indici
Nelle applicazioni concrete sono abbastanza rari i casi nei quali si conosce la posizione di un record in
un file. In genere ci si trova di fronte a problemi del tipo “Trovare il record anagrafico dello studente
di nome Pino Bianchi”, ovvero trovare un record in base al valore contenuto in un campo del record
medesimo. La soluzione consiste nell’impiegare file ad accesso diretto integrati con metodi utili per
costruire l’abbinamento tra il valore del campo cercato e la posizione occupata dal record nel file.
Nelle applicazioni informatiche le entità che devono essere rappresentate con record vengono
identificate attraverso un elemento caratteristico (chiave) che di norma è una variabile alfanumerica
(es. matricola del dipendente di un’azienda, il codice di un articolo….)
21
L’organizzazione dell’archivio, per facilitare il ritrovamento dei dati, deve essere simile a quella di un
libro dotato di indice analitico: in tale indice sono elencate in ordine alfabetico le parole chiave
affiancate ciascuna dalla pagina corrispondente del libro. Nel nostro caso basta costruire un indice
ordinato in base al valore del campo Codice e abbinare a ogni valore del codice un puntatore al record
22
posto in un file ad accesso diretto.
In un file con organizzazione sequenziale a indici (indexed
sequential) accanto alla zona dove sono registrati i record nell’ordine
di immissione viene gestita una tabella delle chiavi o file indice: la
ricerca del record avviene leggendo la tabella delle chiavi e non i
record come avviene nei file sequenziali. In questo modo l’utente
può accedere al record specificandone solo la chiave.
E’ possibile comunque accedere a tutti i record del file leggendoli in
modo sequenziale a partire dal primo, sempre seguendo l’ordine
delle chiavi.
23
Organizzazione a indici su più livelli
Al crescere della dimensione del file l’organizzazione sequenziale a indice diventa inefficiente: in lettura a causa del
crescere del numero di accessi al disco necessari per identificare la chiave nel file indice e in scrittura per la necessità
di mantenere ordinato un file di dimensioni crescenti. L’organizzazione a indici su più livelli cerca di risolvere questi
problemi riducendo la dimensione dello spazio di ricerca per gli indici. L’idea è molto semplice: il file degli indici
viene a sua volta indicizzato costruendo un indice (indice di livello 2) per accedere al file degli indici vero e proprio
(indice di livello 1), in una posizione vicina a quella dell’indice cercato. Se anche l’indice di livello 2 è troppo grande
si può costruire un indice di livello 3 per accedere all’indice di livello 2 che punta all’indice vero e proprio.
24
Per accedere al record che ha come codice Dott si scandisce l’indice
di livello 3 alla ricerca di un valore maggior od uguale a Dott, Lore
soddisfa a questa condizione. Il puntatore accanto a Lore indica in
quale blocco dell’indice di livello 2 si deve proseguire la ricerca: si
esamina allora il blocco 7 sino a identificare un valore maggiore o
uguale a Dott e lo si identifica in Ermo. La ricerca prosegue al
blocco 13 dove sono conservati gli indici veri e propri e tra questi
quello cercato.
Nella maggior parte dei casi sono sufficienti indici su tre livelli per
indicizzare un file e solo per file veramente grandi sono richiesti
quattro o più livelli.
25
Operazioni sui file
Sui file possono essere eseguite le seguenti operazioni:
- l’apertura di un archivio stabilisce un collegamento tra la memoria centrale e il file registrato sulla
memoria di massa, riservando un buffer per le operazioni di I/O e individuando nella tabella dei
descrittori di file le informazioni necessarie per accedere ai blocchi fisici del file. Il comando di
apertura deve essere eseguito prima di iniziare qualsiasi operazione di lettura o scrittura.
- l’operazione di lettura copia in memoria centrale dalla memoria di massa il contenuto dei campi di
un record registrato nel file
- l’operazione di scrittura trasferisce sulla memoria di massa il contenuto del record composto in
memoria centrale con i valori assegnati ai campi
- il posizionamento individua il record sul quale si deve leggere o scrivere oppure a partire dal quale si
deve iniziare una lettura o scrittura sequenziale
- l’operazione di riscrittura aggiorna nel file su memoria di massa il contenuto di un record
modificato durante l’operazione
- la cancellazione di un record elimina le informazioni che non servono più nelle applicazioni
utilizzate. L’operazione di cancellazione va effettuata con molta cautela
- la chiusura del file interrompe il collegamento tra memoria centrale e file, liberando la memoria
26
riservata per le operazioni di I/O e aggiornando le informazioni sul file nella tabella dei descrittori.
Le applicazioni gestionali
Le applicazioni informatiche, che riguardano problemi gestionali nelle aziende, negli studi
professionali o negli Enti pubblici, sono basate sull’uso di dati organizzati in archivi. I dati devono
essere raccolti, registrati sui supporti di memoria, per metterli poi a disposizione degli utenti con
procedure di interrogazione o di stampa di report.
Gli archivi sono di solito:
- anagrafiche, contenenti le informazioni sui soggetti, persone o prodotte
- movimenti, che riguardano gli elementi riferiti ai soggetti descritti nelle anagrafiche
- parametri, con i dati che rimangono costanti per un certo periodo di tempo
Per es. nella gestione di uno studio dentistico:
- l’anagrafica è l’archivio dei clienti dello studio con cognome, nome, indirizzo, telefono, codice
fiscale
- i movimenti sono le prestazioni che il medico ha svolto per i clienti, con data e tipo di prestazione
- i parametri sono i dati riguardanti il costo degli interventi o delle protesi
27
Le procedure per la gestione degli archivi comprendono da una parte programmi
per la creazione degli archivi e la loro manutenzione nel tempo, e dall’altra
programmi per ritrovare i dati che servono attraverso l’interrogazione degli
archivi.
Nelle attività di inserimento di nuovi dati, modifica dei dati esistenti o
cancellazione di quelli che non servono, l’utente finale utilizza maschere a video
per facilitare il loro inserimento o di aggiornamento.
I dati che servono possono essere ottenuti con operazioni di interrogazione che
presentano i dati con visualizzazioni sul monitor o stampe su carta.
Le stampe (report) sono costituite da elenchi su carta, come nelle liste alfabetiche
o nei listini prezzi
28
Le operazioni sugli archivi sequenziali
-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
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
29
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
30
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
libero ed infine procedere al reale inserimento dei nuovi dati. Anche in questo caso, se vi sono già blocchi
logicamente liberi all’interno dell’archivio, basterà spostare tutte le registrazioni solo fino al primo spazio libero,
31
riducendo così i tempi dell’operazione
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……
Per contro l’uso degli archivi sequenziali può essere sconsigliato in tutti i casi in cui occorre velocizzare i tempi di
ricerca e le operazioni ad essa legate.
32
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.
33
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.
34
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.
35
Gli archivi ad accesso diretto
Le organizzazioni sequenziali e sequenziali con indice rispondono in modo adeguato a buona
parte delle problematiche legate alla gestione di grandi masse di dati, ma non risultano
sufficientemente efficienti nei casi in cui gli archivi siano dinamici e di frequente consultazione.
Infatti, dato che tutte le predette operazioni prevedono lo scorrimento di tutto o di una parte non
trascurabile dell’archivio, i tempi di accesso possono risultare lunghi, soprattutto se le richieste si
susseguono in modo casuale.
L’organizzazione in grado di rispondere con maggiore efficienza a questo problema viene detta ad
accesso diretto, poiché si basa sull’idea di ricavare direttamente dal valore della chiave
l’indirizzo della registrazione ad essa associata. Occorre una funzione che trasformi la chiave in
un indirizzo all’interno dell’archivio. La corrispondenza è garantita da un algoritmo, detto
algoritmo di randomizzazione, e il metodo di accesso viene spesso indicato come indirizzamento
hash. Questo algoritmo deve creare un’associazione chiave-indirizzo tale che ad ogni valore k
della chiave faccia corrispondere in indirizzo I(k). La situazione ideale si otterrebbe con una
funzione che, ad ogni valore ipotetico della chiave, faccia corrispondere un indirizzo distinto, in
modo che ogni elemento possa essere raggiunto con un unico accesso. Ciò comporterebbe che il
numero di record che compongono l’archivio fisico sia pari al numero di tutti i possibili valori
assegnabili alla chiave.
E’evidente che, poiché nella realtà il numero di chiavi reali è di gran lunga più basso di quello
delle chiavi ipotetiche, un’organizzazione di questo tipo porterebbe ad un inaccettabile spreco di
memoria.
36
La scelta dell’algoritmo di calcolo risulta quindi cruciale e richiede un’attenta considerazione sui
seguenti aspetti:
- l’algoritmo usato per la trasformazione deve sempre produrre lo stesso indirizzo a partire dalla
medesima chiave
- l’algoritmo dovrebbe essere il più semplice possibile, in modo da non appesantire le operazioni di
conversione della chiave ed abbassare il tempo di accesso
- la trasformazione dovrebbe coprire l’intero intervallo degli indirizzi, poiché, se l’algoritmo non
genera mai un indirizzo i, lo spazio di memoria ad esso associato non verrà mai occupato
- occorrerebbe evitare che due o più chiavi vengono trasformate dall’algoritmo di randomizzazione
nello stesso indirizzo (collisione)
37
Algoritmo 1
Quando la chiave numerica è formata da un numero elevato di cifre e il range degli indirizzi è
piuttosto limitato, si può estrarre dalla chiave numerica un sottoinsieme di cifre in grado di
rappresentare l’indirizzo.
Ad es. sono disponibili 10000 blocchi a partire dall’indirizzo 0
Chiave numerica:
901 102 311
Indirizzo ottenuto estraendo le ultime 4 cifre: 2311
Questo metodo è particolarmente efficiente nei casi in cui le chiavi numeriche siano per la maggior
parte consecutive e con poche interruzioni
Algoritmo 2
Si eleva il valore della chiave numerica al quadrato e si seleziona un certo numero di cifre (spesso le
centrali) del risultato.
Ad es. sono disponibili 10000 blocchi a partire dall’indirizzo 0
Chiave numerica:
901 102 311
Quadrato:
811 853 659 686 278 431
Indirizzo ottenuto estraendo le ultime 4 cifre: 5 968
Questo metodo produce buone organizzazioni casuali
38
Algoritmo 3
Il valore della chiave viene diviso per il numero di blocchi disponibili in memoria e si considera come
indirizzo il resto della divisione
Es. sono disponibili 7429 blocchi a partire dall’indirizzo 4001
Chiave numerica:
901 123 311
Chiave/7429=121298 resto=469
Indirizzo: 40001 + 469 = 4 470
Algoritmo 4
Si tratta di una estensione del metodo precedente, in cui la chiave numerica viene divisa per un numero
primo abbastanza grande. Questo metodo può ottenere risultati molto vicini alla vera randomizzazione
39