Task Piero Gallo Fabio Salerno -...

TaskCorso di informatica

Piero Gallo Fabio Salerno

2il libro si estende sul web

Gli archivisequenziali

L’organizzazionesequenzialeLEZIONE

il libro si estende sul web

2 P. Gallo F. Salerno Task 2 – Gli archivi sequenziali

L’organizzazione logica sequenziale

Con archivio logico sequenziale intendiamo un archivio in cui i record sono re-gistrati in posizioni contigue a partire dalla prima.

Quando su uno o più campi del record è possibile stabilire un ordinamento, allo-ra si può definire anche un ordinamento logico tra le registrazioni che, in deter-minate circostanze, può anche coincidere con l’ordine fisico. Se i due ordinamen-ti coincidono, l’archivio viene detto sequenziale ordinato.Nella seguente figura riportiamo un esempio di archivio sequenziale ordinato: lafunzione di chiave primaria è stata associata al nome del personaggio e le varieregistrazioni sono ordinate alfabeticamente.

Tra le caratteristiche fondamentali di questo tipo di organizzazione ricordiamo:

• la possibilità di immissione solo in coda che consente di non perdere l’ordinedi 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 sequenzialeOccupiamoci, ora, dell’aspetto fisico dell’archivio.

Con archivio fisico sequenziale si indica il modo in cui i file sono scritti su di-sco e non la natura logica degli stessi, descritta nel precedente paragrafo diquesta lezione.

In questo paragrafo, pertanto, quando parliamo di “archivi sequenziali” facciamoriferimento ad “archivi fisici sequenziali”.Gli archivi sequenziali sono memorizzati sulla memoria di massa attraverso latecnica dell’allocazione contigua. In questo modo, i blocchi che costituiscono ilfile sono memorizzati uno di seguito all’altro, ossia in ordine sequenziale, comesi osserva nella figura a pagina seguente.

Indirizzo Chiave Informazioni

1 ... i Minni i+1 Paperino i+2 Paperoga i+3 Pluto i+4 Topolino

... ...

... ...

...

...

...

...

...

L’organizzazione sequenziale

P. Gallo F. Salerno Task 2 – Gli archivi sequenziali 3

Come si vede, l’allocazione contigua di un file è definita dando l’indirizzo del pri-mo blocco sul quale il file stesso è allocato e il numero di blocchi che compongo-no quest’ultimo. Se ad esempio il file è memorizzato a partire dalla locazione bed è lungo n, allora occuperà i blocchi: b, b+1, b+2, ..., b+n–1.

Questo tipo di allocazione presenta vantaggi e svantaggi. Il vantaggio principaleconsiste nella semplificazione dell’operazione di accesso al file, che consente unrisparmio 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 sudisco del primo blocco occupato, è possibile realizzare l’accesso diretto in modosostanzialmente semplice.

L’accesso a un file allocato in modo contiguo è, quindi, piuttosto semplice, ma ledifficoltà sorgono ogniqualvolta si ha la necessità di allocare un nuovo file. Se ilfile da memorizzare è “lungo” n blocchi, si deve cercare all’interno della lista del-lo spazio libero se esiste una serie di n blocchi contigui. Ciò non è sempre possi-bile. Questa operazione di ricerca di uno spazio idoneo può essere effettuata dalsistema operativo utilizzando diverse strategie:

• ricercando la prima area libera sufficientemente grande (first-fit); • ricercando la prima area libera sufficientemente grande, iniziando l’operazio-

ne 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 discocontinuerà a essere frammentato sempre di più, fino a trovarsi in una situazioneche potrebbe sembrare assurda, ma purtroppo è assolutamente reale: non saràpossibile memorizzare un file poiché non esisterà uno spazio contiguo abbastan-za capiente da contenerlo, nonostante lo spazio libero complessivo sia sensibil-mente maggiore di quello necessario.

LEZIONE 1

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

16 17 18 19

20 21 22 23

File Blocco iniziale Lunghezza

compito 5 3

lezione 18 5

programma 12 1

...


ESEMPI L’organizzazione sequenzialeLEZIONE Oggigiorno la gestione degli archivi di dati (in forma di database) è oramai dele-

gata ad appositi software denominati DMBS (Database Management System), poi-ché la loro semplicità di utilizzo e la loro sicurezza ne consente l’utilizzo anchesenza conoscere neppure marginalmente le varie modalità con cui organizzano idati e li memorizzano. Nonostante ciò, è comunque utile conoscere alcuni tipi diorganizzazione logica che consentono di organizzare archivi per applicazioni per-sonalizzate. Quelli che andremo ad analizzare non sono indispensabili: sono sem-plicemente comodi!

I file di testo

Un archivio organizzato come file di testo contiene solo semplici caratteri discrittura, senza alcuna informazione sul loro formato (dimensione, colore ecosì via). Solitamente rappresenta un testo che può essere letto con semplicieditor di testo senza bisogno di installare sofisticati word processor.

I byte dei file di testo rappresentano quindi lettere, numeri, punteggiatura, spazie altri normali simboli stampabili, ma possono contenere anche specifici caratte-ri di controllo come tab (per la tabulazione), carriage return (CR) per il ritorno acapo 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 in-stallazione, 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 memorizza-no alcuni dati relativi alla configurazione del sistema.Un motivo della diffusione dei file di testo è la facile interpretabilità da parte del-l’uomo. Un esempio di struttura di questo tipo di file è riportata nella seguente fi-gura: 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



Analizziamolo:

• una sezione inizia con la dichiarazione del suo nome racchiuso fra parentesiquadre (nel nostro caso [Sezione1] e [Sezione2]);

• all’interno di una sezione, l’assegnazione di un valore a un parametro si effet-tua con un’assegnazione matematica (variabile = valore);

• una riga che inizia con un punto e virgola (‘;’) è un commento, e in quanto taleviene ignorata.

I file CSV

CSV (Comma Separated Values = valori separati da virgola) è un formato perfile di testo utilizzato per memorizzare dati nei fogli elettronici, nei database eper lo scambio di dati tra sistemi differenti che operano su piattaforme incom-patibili.

Al suo interno, ogni riga rappresenta un record composto da campi separati dauna virgola (nel caso in cui la virgola sia una carattere da rappresentare all’inter-no di un campo, il carattere separatore viene sostituito con un altro, ad esempioil punto e virgola, oppure il campo stesso viene racchiuso tra virgolette). Ogni re-cord è separato dal successivo dalla sequenza di caratteri CR+LF (Carriage Return+ Line Feed) che consentono, rispettivamente, di ritornare all’inizio della riga e diaggiungere 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 conten-gono virgole;

• è preferibile non lasciare spazi prima e dopo i campi (se intenzionali, tali spa-zi devono essere racchiusi tra doppi apici);

• per rappresentare un carattere doppi apici in un campo occorre raddoppiarlo:“ diventa “”.

ESEMPI 1


ESEMPI L’organizzazione sequenzialeLEZIONE

� <?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>

Rossi Maria 20134 Milano

Neri Paolo 73100 Lecce

Verdi Riccardo 70100 Bari

Gialli Daniela 00195 Roma

I file XMLL’HTML (Hypertext Markup Language) è un linguaggio che consente di creare inmaniera standardizzata pagine di informazioni formattate in grado di raggiunge-re attraverso Internet gli utenti di tutto il mondo. Insieme al protocollo HTTP(Hypertext Transport Protocol), l’HTML ha rivoluzionato il modo in cui le personetrasmettono e ricevono informazioni; il suo scopo principale, però, è sempre sta-to inerente la visualizzazione dei dati. L’HTML, infatti, considera particolarmenteil modo in cui le informazioni vengono presentate e non si occupa minimamen-te del tipo o della struttura di tali informazioni.Per far fronte a tali aspetti è stato sviluppato il linguaggio XML (eXtensible MarkupLanguage) che espande le capacità di HTML grazie all’introduzione di nuovi mar-catori. La sintassi di XML è molto scarna, non prevede tanti elementi di marcatu-ra. Quando si crea un documento XML, invece di utilizzare un set di elementi pre-definiti, è possibile crearne di nuovi e assegnare loro i nomi desiderati, il chespiega 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, ciascu-no 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 memo-rizzare e scambiare dati tra applicazioni, o come file di configurazione. Sono fileormai molto diffusi, al punto che alcuni gestori di database memorizzano i dati di-rettamente in questo formato oppure, pur non scrivendo i dati in XML, consento-no di estrarne il contenuto in questo formato.Proviamo a comporre un file XML con i dati presenti nel seguente elenco di amici:



� <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 definizio-ne XML. I nomi degli elementi vengono creati durante la generazione di un deter-minato documento e possono essere scelti a proprio piacimento. Nell’ esempioavremmo potuto continuare a scrivere tanti altri elementi AMICO e al loro inter-no gli elementi COGNOME, NOME, CAP e CITTA.Pertanto, un documento XML è strutturato in base a una gerarchia strutturata, incui gli elementi risultano annidati in altri elementi, con un unico elemento di li-vello superiore (AMICI, nel nostro caso), il quale prende il nome di elemento deldocumento o elemento principale.

I file binari

I file binari sono file contenenti dati generici che non sono direttamente leggi-bili dall’utente. In realtà, dal punto di vista della macchina, non c’è distinzionetra file di testo e fil binari, poiché tutti entrambi non sono altro che sequenzedi byte. La differenza sta solo in ciò che i byte rappresentano e nel modo in cuisono utilizzati.

Un file binario è una pura sequenza di byte, senza alcuna struttura particolare. Èun’astrazione di memorizzazione assolutamente generale, utilizzabile per memo-rizzare informazioni di qualsiasi natura come ”fotografie” della memoria, rappre-sentazioni interne binarie di numeri, immagini, canzoni campionate e, volendo,anche caratteri!I file binari sono solitamente concepiti come se-quenze di byte: i singoli bit che costituiscono il filesono raggruppati in gruppi di otto. Questi file con-tengono byte che devono generalmente essere in-terpretati in modo diverso dai caratteri: i file compi-lati sono un esempio (i programmatori si riferisconospesso al codice oggetto col termine “binario”), masi può trattare di immagini, musica, dati compressio di qualsiasi altro tipo.Aprendo un file binario con un editor di testo, ognigruppo di otto bit viene regolarmente interpretato etradotto come un carattere e ne risulta una sequen-za del tutto incomprensibile (a meno di coincidenze o inserti di testo nel file). Selo si apre con un diverso tipo di applicazione, questa interpreterà i singoli byte delfile a suo modo: potrebbe, quindi, farvi corrispondere una cifra e restituire unasfilza pressoché casuale di numeri; oppure, se il file viene riconosciuto come ese-guibile, il computer cercherà in essi delle istruzioni in linguaggio macchina.

ESEMPI 1

Le operazioni logichesugli archivisequenziali


Le operazioni consentite su un archivio a organizzazione sequenziale sono rias-sunte nel seguente diagramma:

InserimentoPer l’operazione di inserimento occorre distinguere sempre tra archivi non ordi-nati e archivi ordinati.Su un archivio non ordinato, l’inserimento non comporta problemi: il record siaggiunge in coda o, se nell’archivio esistono delle posizioni libere, può essere in-serito 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 evidenteche, una volta individuata la posizione, occorrerà traslare tutti i record successiviin modo da creare lo spazio. Se nell’archivio ci fossero posizioni libere, l’inseri-mento sarebbe meno oneroso, in quanto potremmo limitare la traslazione soltan-to fino al primo spazio libero. Considerato che la presenza di tali spazi agevolaquesta operazione, perché non crearli di proposito in fase di progettazione dell’ar-chivio? Operando in questo modo, occorre distribuire un congruo numero di areelibere lungo l’archivio, scegliendo opportunamente il numero e la dimensione infunzione del problema e delle risorse a disposizione.È ovvio, comunque, che se la presenza di tali aree agevola l’inserimento, ostaco-la, però, la ricerca. Alternative efficienti possono essere applicate solo su archiviordinati. Vediamone qualcuna.Una prima soluzione consiste nel registrare i nuovi record in un archivio tempo-raneo o differenziale. Si procede poi, periodicamente, a una fusione tra i due ar-chivi, così da rigenerare l’archivio principale. Questa soluzione non è delle miglio-

LEZIONE


INDICESEMPLICE

INDICE TRAMITELISTA CONCATENATA

ORGANIZZAZIONELOGICA

ARCHIVISEQUENZIALI

SINGOLOFILE

CON USODI INDICI

NONORDINATO

ORDINATO

ACCESSO SEQUENZIALE

Inserimento:Modifica:Cancellazione:Ricerca:

in codausa file differenzialeusa file differenziale

completa

ACCESSO DIRETTO

Inserimento:Modifica:Cancellazione logica:Cancellazione fisica:Ricerca:

in codaimmediataimmediata

solo al riordinocompleta

ACCESSO SEQUENZIALE

Inserimento:

Modifica:Cancellazione:Ricerca:

usa aree dei trabocchiusa file differenzialeusa file differenzialeusa file differenziale

sequenziale

ACCESSO DIRETTO

Inserimento:Modifica:Cancellazione logica:Cancellazione fisica:Ricerca:

usa aree dei trabocchiimmediataimmediata

solo al riordinosequenziale

binariainterpolata

Le operazioni logichesugli archivi sequenziali

ri, in quanto alcune operazioni, come ad esempio la ricerca, sarebbero eseguitein modo poco efficiente perché, per reperire un record, occorrerebbe operare siasull’archivio principale che su quello temporaneo, con conseguente aumento deitempi di risposta.La soluzione ottimale consiste nel predisporre nell’archivio delle aree libere, det-te aree di overflow (o aree dei trabocchi), destinate ad accogliere i nuovi recordinseriti. Queste aree possono essere disposte uniformemente nell’archivio princi-pale o in un altro archivio differenziale (aree di overflow distribuito), oppure es-sere allocate in un unico punto dell’archivio o, ancora una volta, in un altro archi-vio differenziale (aree di overflow concentrato).

Aggiornamento (riscrittura)La fase di aggiornamento, ossia l’operazione che consente di apportare modifi-che ai campi di un record (a eccezione della chiave), può essere svolta, come alsolito, in due modi diversi dipendenti dal metodo di accesso.Se l’accesso è sequenziale, l’aggiornamento di un record può essere svolto soloriscrivendo 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.

CancellazioneAnche per la cancellazione valgono le medesime considerazioni svolte per l’ag-giornamento. Pertanto, nel caso di archivi sequenziali ad accesso sequenzialel’unico modo per poter cancellare un record (e quindi mantenere la corrispon-denza tra la struttura logica e quella fisica) è quello di riscrivere l’intero archivioprivato del record stesso servendosi di un archivio di appoggio.Nel caso di archivi sequenziali ad accesso diretto, si ovvia a questo increscioso in-conveniente effettuando una cancellazione logica, ossia predisponendo un ap-posito campo in grado di contenere un valore la cui presenza indica, appunto, lacancellazione del record. Periodicamente si provvederà alla compattazione del-l’archivio, eliminando fisicamente i record marcati per la cancellazione (cancel-lazione fisica).

OrdinamentoÈ ormai evidente che l’ordinamento riveste un ruolo di fondamentale importan-za per garantire l’efficienza di talune operazioni. Per questo, occorre fare moltaattenzione nella scelta del metodo da applicare per ordinare l’archivio. Senzascendere in dettagli, ricordiamo che molti dei metodi di ordinamento descritti nelprimo volume del testo possono essere tranquillamente applicati anche agli archi-vi sequenziali ad accesso diretto. Ciò, ovviamente, non è valido per gli archivi me-morizzati su dispositivi a esclusivo accesso sequenziale.

LEZIONE 2


Aree di overflowdistribuito

Area di overflowconcentrato

Le operazioni logiche:la ricerca


Le esigenze maggiormente diffuse nell’uso degli archivi sono quelle di inserimen-to, consultazione e aggiornamento di record. In presenza di tali esigenze, la ricer-ca dei record registrati è una delle operazioni più importanti e più frequenti. È ov-vio, quindi, che tale operazione debba essere compiuta utilizzando una tecnicache consenta di ottenere il miglior risultato nel minor tempo possibile. La sceltadel metodo riveste un ruolo di fondamentale importanza e varia in base al tipo disupporto di memoria utilizzato e alla presenza o meno di un ordinamento. In pas-sato gli archivi venivano memorizzati sui nastri magnetici e, su di essi, l’unicometodo di ricerca attuabile era quello della ricerca completa dell’archivio, sino alreperimento del record di chiave desiderata. Il numero medio di accessi di talemetodo è 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 solosu alcuni record, si cercò di ridurre il numero medio di accessi collocando tali re-cord nelle prime posizioni dell’archivio. Questo metodo apportò un parziale in-cremento di efficienza solo in caso di successo: infatti, più probabile era la chia-ve, meno accessi erano necessari. In caso di insuccesso, invece, la situazione nonmutava: erano sempre necessari N accessi. Con gli archivi ordinati si poté ricorre-re a un altro metodo di ricerca, la ricerca sequenziale, ottenuta mediante l’ottimiz-zazione della scansione (la ricerca, infatti, si interrompe quando si trova la chiavecercata oppure quando ci si posiziona su un record di chiave maggiore di quellacercata). In tal caso, il numero medio di accessi diveniva:

• successo: (N + 1)/2 accessi;• insuccesso: (N + 1)/2 accessi.

Ricapitoliamo:

Analizziamo, ora, il problema della ricerca applicato ad archivi a organizzazionesequenziale memorizzati su supporti ad accesso diretto. Quando è consentitol’accesso diretto, si possono verificare le seguenti situazioni:

• se si conosce l’indirizzo del record da ricercare, il problema non sussiste: me-diante un accesso, ci si posiziona direttamente sul record;

• se l’indirizzo del record non è noto e l’archivio è disordinato, la situazione restaanaloga a quella descritta per l’accesso sequenziale;

• se l’indirizzo del record non è noto, ma l’archivio è ordinato, il problema vienerisolto con l’impiego di tecniche di ricerca molto efficienti, quali la ricerca bi-naria. Per quanto riguarda questo metodo di ricerca, sia in caso di insuccessoche di successo (sia riferito al caso medio che a quello pessimo) si può dimo-

LEZIONE


RICERCA in archivi aORGANIZZAZIONE Sequenziale

e ACCESSO Sequenziale

Archivioordinato

Archivio con chiavidi frequente

movimento in testa

Archivionon ordinato

Successo

(N + 1)/2accessi

Naccessi

(N + 1)/2accessi

(N + 1)/2accessi

In funzionedella probabilità

della chiave

Naccessi

Insuccesso Successo Insuccesso Successo Insuccesso

Le operazioni logiche: la ricerca

strare che il numero di accessi è pari a log(N). Il numero medio di accessi del-la ricerca interpolata, invece, è pari a log(log(N)), quindi è nettamente inferiorea quello della ricerca binaria.

Riportiamo la soluzione di massima dell’algoritmo della ricerca binaria espressoin 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:


LEZIONE 3

RICERCA in archivi aORGANIZZAZIONE Sequenziale

e ACCESSO Diretto

Indirizzosconosciuto

Indirizzoconosciuto

1accesso

Archivioordinato

Successo

Ricercabinaria

Ricercainterpolata

Ricercabinaria

Ricercainterpolata

Insuccesso Analogo all’accessosequenziale

Archiviodisordinato

Sia nel casomedio sia in

quello pessimo

log2 N

Caso medio

log2 N (log2 N)

Sia nel casomedio sia in

quello pessimo

log2 N

Solo se le chiavisono

uniformementedistribuite

log2 (log2 N)

L’organizzazionesequenziale con indice


Gli archivi registrati su supporti fisici che permettono l’accesso diretto possono es-sere gestiti anche con una variante dell’organizzazione sequenziale, caratterizzatadalla possibilità di velocizzare la ricerca di un record mediante uno o più indici.

Nell’organizzazione sequenziale a indici (indexed sequential) si possono distin-guere 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 indi-

ci, 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 del-

l’archivio primario.

Questa tipologia di organizzazione prevede, quindi, la suddivisione del file ingruppi di record e la conservazione della chiave, la maggiore o la minore tra tuttequelle dei record presenti in ciascun gruppo, in una sovrastruttura di indici che di-venta un vero e proprio file di indici distinto da quello dei dati. L’acceso indicizza-to a un record avviene in due fasi: prima si ricerca nel file di indici quello del grup-po che lo contiene e poi si leggono in modo sequenziale tutti i record del gruppofino a raggiungere quello cercato.L’indice, quindi, consente di stabilire una corrispondenza tra ogni chiave e la posi-zione del relativo record memorizzato nell’archivio.Analizziamo la seguente figura. Si nota come l’indice debba contenere necessa-riamente tutte le chiavi presenti nell’archivio primario. Per cercare un record dicui si conosce la chiave, si cerca questa nell’indice; se esiste, tramite il puntatore,si accede direttamente all’archivio primario.

Questa soluzione è dispendiosa sia in termini di occupazione di memoria, sia digestione delle informazioni. Per sfruttare la totalità dei vantaggi offerti da questotipo di organizzazione, e in particolare potenziare le operazioni di ricerca dei re-cord, occorre innanzitutto distinguere fra:

• strutture sequenziali con indice ordinate;• strutture sequenziali con indice non ordinate;

e tenere conto del metodo di costituzione dell’indice.

LEZIONE


A 8B 5D 6E 9F 2G 4

O 7X 1Z 3

Chiave

Indice ordinato (dizionario) Archivio primario

Puntat.X Informazioni su XFZ Informazioni su ZGBD

O Informazioni su OAE

123456

789

Chiave Parte informativa

L’organizzazione sequenziale con indice

Nelle strutture ordinate, l’archivio primario viene implementato in una struttura apagine (o sottoarchivi che sono costituiti da blocchi contigui con ugual numero direcord) e l’indirizzo della chiave più alta di ciascun sottoarchivio è contenuto nel-l’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 deivari sottoarchivi. Analizziamo la seguente figura:

In pratica, il valore della chiave nell’indice indica esplicitamente la chiave di valo-re più alto contenuta all’interno del sottoarchivio, mentre il puntatore indica im-plicitamente la posizione della chiave più bassa poiché rappresenta l’indirizzo delsottoarchivio e, quindi, il primo record presente, cioè quello con la chiave di valo-re più basso.Generalmente, la ricerca di una chiave K avviene rispettando la seguente proce-dura:

• 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 ri-cerca (sequenziale, binaria, interpolata e così via). In questo tipo di organizzazio-ne, 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 col-legano i sottoarchivi sono state appositamente inserite per suggerire che, nono-stante la suddivisione, è possibile eseguire la scansione sequenziale dell’archivioprimario utilizzando diverse tecniche. Si può, ad esempio, ricorrere a un puntato-re esplicito, per mezzo dello stesso archivio indice, oppure sfruttare la contiguitàdelle pagine.


LEZIONE 4

Sottoarchivio1

2 ...5 ...20 ...

Sottoarchivio2 48 ...

52 ...85 ...


154 ...190 ...


211 ...214 ...

Chiave Altri dati

20 185 2190 3214 4

Chiave Puntat.

L’organizzazionesequenziale con indice:l’aggiornamento


Poiché l’archivio primario è pur sempre un archivio sequenziale, le operazioni checomportano qualche problema nella loro implementazione sono quelle di inseri-mento e di cancellazione di record, le quali richiedono successive riorganizzazionidell’archivio. Queste operazioni vengono eseguite nello stesso modo previsto perl’organizzazione sequenziale, ossia servendosi di apposite aree di overflow.Una tra le tecniche più frequentemente utilizzate prevede che il record dell’archi-vio indice sia così strutturato:

(Kh, P, Kovf, Povf)

dove Kovf e Povf indicano, rispettivamente, la chiave più alta presente nell’area dioverflow e il puntatore di accesso a tale area.Durante l’esecuzione delle varie operazioni logiche relative a un record di chiaveK, l’area di overflow sarà consultata solo se la pagina P è piena e se la chiave K ri-sulta compresa tra Kh e Kovf.Riprendiamo l’esempio riportato nella precedente lezione e proviamo a inserire ilrecord di chiave 58. L’inserimento verrà effettuato nel sottoarchivio 2 che, essen-do pieno, provocherà il trabocco del record di chiave 85.Dopo l’inserimento la situazione sarà la seguente:

LEZIONE


Sottoarchivio1

2...5...20...

Sottoarchivio2

48...52...58...

Sottoarchivio3

125...154...190...

Sottoarchivio4

199...211...214...

Sottoarchivio5

(overflow)

85.........

ChiaveAltridati

20 158 2

190 3214 4

Nil85NilNil

Nil5NilNil

Chiave Kovf PovfPunt.

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

L’organizzazione sequenziale con indice:l’aggiornamento

Riportiamo la soluzione di massima relativa all’operazione di inserimento appe-na 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 pos-sono variare in funzione del metodo implementativo adottato. Una delle possibi-li soluzioni prevede di riservare un sottoarchivio di overflow ogni N sottoarchividell’archivio primario.


LEZIONE 5

Indici multiplio a più livelli

Nel caso in cui il numero di sottoarchivi diventi rilevante e, di conseguenza, il nu-mero di record presenti nell’indice cominci a divenire considerevole (appesanten-do la ricerca), è possibile organizzare l’indice a sua volta come un archivio se-quenziale con indice. Si dà così luogo a sottoindici di differente livello, chepermettono di ottenere una diminuzione del tempo di scansione dell’indice stes-so. In presenza di più livelli di indice, nella fase di ricerca la gerarchia viene utiliz-zata per poter individuare (partendo da un indice a livello k) quale indice a livellok + 1 debba essere esaminato al fine di selezionare il sottoarchivio all’interno delquale si trova il record cercato.

Per comprendere l’uso degli indici a più livelli, si può fare riferimento al reperi-mento di un’informazione di un volume mediante il suo indice analitico. Un indi-ce analitico è composto da un insieme di termini accanto ai quali è specificata lapagina del libro all’interno della quale essi sono trattati.

I vari termini sono ordinati alfabeticamente e sono raggruppati secondo le lette-re dell’alfabeto con la quale iniziano. Se, ad esempio, si vuole ricercare il termineindice, 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 in-dici quante sono le lettere e ciascun indice è composto da tutti i termini che ini-ziano con la lettera collegata.

Talvolta, questo tipo di organizzazione viene utilizzato su hard disk, cioè su sup-porti a disco di tipo disk-pack, al fine di ottimizzare i movimenti del pettine.Generalmente, un’organizzazione sequenziale con indice utilizza tre livelli di indi-ce, in particolare:

• un indice di unità, che consente di determinare su quale unità di memoria se-condaria occorre ricercare il record, nel caso in cui l’archivio sia memorizzatosu più unità;

• per ogni unità, un indice di cilindro che consente di determinare su quale ci-lindro dell’unità deve avvenire la ricerca;

• per ogni cilindro, un indice di traccia che consente di determinare su qualetraccia di quel cilindro deve avvenire la ricerca.

Nel caso di strutture non ordinate, l’indice è più complesso e può essere articola-to anche su più livelli. Tuttavia, nonostante il numero di indici e le loro dimensio-ni ragguardevoli, la gestione non ordinata facilita notevolmente l’operazione diinserimento, poiché nuovi record saranno semplicemente aggiunti in coda all’ar-chivio primario, senza che si verifichino appesantimenti dovuti alla gestione del-le aree di overflow.

LEZIONEil libro si estende sul web


Indici multipli o a più livelli LEZIONE 6


INDICE ALLIVELLO 1

ARCHIVOPRIMARIO

INDICE ALLIVELLO 3

INDICE ALLIVELLO 2

152215527900

5678

212152554

...

...

...

...64 ...72 ...98 ...

112

102120125130

...

...

...

...132 ...140 ...152 ...

113

98152

112113

5

202215

114115

6

250527

116117

7

850900

118119

8

10001154

120121

9

65207590

140141

16

1154189623802585

9101112

3

90025857590

234

1

4931565068887590

13141516

4

...

...

...

160200201202

...

...

...

...

114

...

Tutto in test...aPROVE OGGETTIVE PER LA VERIFICA DELLE CONOSCENZE


Che cos’è un archivio sequenziale?

Quali sono le caratteristiche fondamentali dell’orga-nizzazione sequenziale?

Un file di testo

contiene solo semplici caratteri di scrittura

non necessita di sofisticati word processor perla sua lettura

non può contenere simboli di punteggiatura

non può contenere numeri

Che cosa sono i file ini?

Che cosa differenzia il linguaggio HTML dal linguaggioXML?

I file binari

non sono direttamente leggibili dall’utente

possono essere letti solo con word processorsofisticati

possono essere letti con qualsiasi wordprocessor

contengono una sequenza di numeri decimali

Stabilisci se le seguenti affermazioni sono vere o false:

in un archivio sequenziale l’ordinamentologico può coincidere con l’ordinamentofisico --------------------------------------------------------------------------

quando l’ordinamento, logico coincidecon quello fisico l’archivio viene dettosequenziale puro ---------------------------------------------------

le operazioni consentite su un archivio adorganizzazione sequenziale sono la lettura,la scrittura e la riscrittura -----------------------------------

la fase di aggiornamento consentedi apportare delle modifiche ai campidi un record ad eccezione della chiave---------- FV

d

FV

c

FV

b

FV

a

7.

d

c

b

a

6.

5.

4.

d

c

b

a

3.

2.

1. Quando un archivio sequenziale viene detto seriale?

Su un archivio sequenziale non ordinato, l’inserimentonon comporta problemi. Che cosa significa?

In fase di inserimento i problemi sorgono se l’archiviosequenziale è ordinato. Che cosa significa?

Stabilisci se le seguenti affermazioni sono vere o false

in un archivio sequenziale ad accessodiretto la ricerca sequenziale effettualog2N accessi ---------------------------------------------------------

nell’organizzazione ad indici si distinguonotre elementi fondamentali ----------------------------------

le strutture sequenziali possono essere ordinateo no ----------------------------------------------------------------------------

su archivi sequenziali è possibile effettuare lacancellazione logica----------------------------------------------

Che cosa sono le aree di overflow (dette anche areedei trabocchi)?

Che cosa sono le aree di overflow distribuito?

Che cosa sono le aree di overlow concentrato?

Stabilisci se le seguenti affermazioni sono vere o false

nell’organizzazione ad indici, il dizionariopuò non essere ordinato-------------------------------------

gli indici possono essere gestiti solo sudispositivi ad accesso diretto ---------------------------

In un’organizzazione a indice, quando si parla di archi-vio primario non paginato?

In un’organizzazione a indice, quando è necessario uti-lizzare i sottoarchivi?

Generalmente, un’organizzazione sequenziale con in-dice quanti livelli di indice utilizza?

18.

17.

16.

FV

b

FV

a

15.

14.

13.

12.

FV

d

FV

c

FV

b

FV

a

11.

10.

9.

8.

19P. 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à for-mativa. Attribuisci un punto a ogni risposta esatta. Se totalizzi un punteggio:

1. Nell’allocazione contigua:

i file sono memorizzati uno di seguito all’altro,ossia in ordine sequenzialei blocchi che costituiscono il file non sonomemorizzati uno di seguito all’altroi blocchi che costituiscono il file sonomemorizzati uno di seguito all’altro, ossia inordine sequenzialenessuna delle precedenti è corretta

2. Nell’allocazione contigua, la ricerca dello spazio piùgrande per contenere il file da parte del sistema ope-rativo avviene grazie alla tecnica:

best-fitworst-fitnest-fitfirst-fit

3. Nell’allocazione contigua:

qualsiasi tecnica di gestione del disco è valida

qualsiasi tecnica si utilizzi, però, sorgeranno deiproblemi

il disco non sarà mai frammentato

si arriverà a una situazione in cui non esisteràuno spazio contiguo abbastanza capiente dacontenere il file nonostante lo spazio libero siamaggiore di quello necessario.

4. La sigla CSV fa riferimento:

a un formato per Interneta un formato per file di testo utilizzato per loscambio di dati tra sistemi differenti cheoperano su piattaforme incompatibilia un formato per file di testo in cui i campi sonoseparati da virgolea un formato per file di testo in cui i campi sonoseparati da trattini

5. L’archivio differenziale:

è un file XMLè un file binarioè un file che non può essere cancellatoè un file temporaneod

c

b

a

d

c

b

a

d

c

b

a

d

c

b

a

d

c

b

a

6. L’aggiornamento di un archivio sequenziale:

può essere svolto in due modi diversi dipendentidal metodo di accesso.può essere svolto solo riscrivendo l’interoarchivio se l’accesso è sequenzialenon può essere eseguita se l’organizzazione èad accesso direttonon può comunque essere fatto su archivisequenziali

7. L’organizzazione sequenziale con indice:

può essere implementata su qualsiasi supportofisicopuò essere implementata solo su supporti fisiciche permettono l’accesso direttopuò essere implementata solo su nastrinessuna delle precedenti è corretta

8. Nell’organizzazione sequenziale con indice, l’archiviosecondario è anche detto:

archivio indice ordinatodizionariochiave primariaarchivio differenziale

9. Nell’organizzazione sequenziale con indice, l’indiceconsente di stabilire:

una corrispondenza tra una sola chiave e laposizione del relativo record nell’archiviouna corrispondenza tra ogni chiave e laposizione del relativo record nell’archiviouna corrispondenza tra un campo del record e lasua posizione nell’archiviouna corrispondenza tra un archivio e il fileassociato

10. Gli indici a più livelli sono utilizzati quando:

il numero di sottoarchivi diventa rilevantei campi sono moltii record sono composti da un solo campoil numero di record presenti nell’indice divienenotevole e appesantisce la ricerca

d

c

b

a

d

c

b

a

d

c

b

a

d

c

b

a

d

c

b

a

<4 Tra 4 e 6 Tra 6 e 8 >8

Tutto OKRifletti un po’ sulle tue “disgrazie”

Rivedi l’unità formativanelle sue linee generali

Rivedi l’unità formativanelle sue linee generali

Ripeti il questionarioRivedi con attenzionetutta l’unità formativa

Ripeti il questionario

Task Piero Gallo Fabio Salerno -...

Documents

Transcript of Task Piero Gallo Fabio Salerno -...