File e ArchiviIvano Mazzarotto 2010-2011

Indice generale

1 . Aspetti comuni e definizioni..............................................................................11.1 Introduzione: azienda, organizzazione, sistema informativo, sistema informatico...............................11.2 Definizione di archivio........................................................................................................................21.3 Differenza fra archivio e file................................................................................................................21.4 Record logico, chiave primaria e secondaria.......................................................................................21.5 Record logici e record fisici, il concetto di blocco...............................................................................3

1.5.1 Il record logico..........................................................................................................................41.5.2 Il record fisico............................................................................................................................41.5.3 Il fattore di blocco......................................................................................................................4

1.6 Organizzazione degli archivi: organizzazione fisica e logica...............................................................51.7 Fattori che influenzano la scelta dell'organizzazione...........................................................................51.8 Tipologie di organizzazione dei file ....................................................................................................62 . Gli archivi sequenziali.......................................................................................72.1 Archivi ad organizzazione sequenziale................................................................................................7

2.1.1 Operazioni: inserimento, aggiornamento, cancellazione, ordinamento, ricerca.........................73 . Archivi sequenziale con indice..........................................................................93.1 La struttura dell'archivio indice e dell'archivio principale....................................................................93.2 Operazioni: inserimento, aggiornamento, cancellazione, ordinamento, ricerca...................................9

3.2.1 Ricerca e scansione in struttura sequenziale con indice e archivio primario non ordinato.........93.2.2 Ricerca e scansione in strutture sequenziali con indice e archivio primario ordinato...............103.2.3 Inserimento e cancellazione in strutture sequenziali con indice e archivio primario ordinato..11

3.3 Indici multipli o a più livelli (file ISAM)...........................................................................................124 . Gli archivi non sequenziali..............................................................................134.1 Archivi ad organizzazione relative.....................................................................................................134.2 Archivi ad organizzazione hash.........................................................................................................13

4.2.1 Introduzione.............................................................................................................................134.2.2 Tabelle hash.............................................................................................................................134.2.3 Categorie di funzioni hash ......................................................................................................194.2.4 Gestione delle collisioni...........................................................................................................194.2.5 Chaining o metodi di concatenazione......................................................................................204.2.6 Open addressing o metodo di indirizzamento aperto...............................................................20

5 . Organizzazione ad indici B-Tree....................................................................235.1 Introduzione.......................................................................................................................................235.2 BTree.................................................................................................................................................235.3 Obiettivo limitare le operazioni di I/O...............................................................................................235.4 Perché usiamo i BTree?.....................................................................................................................255.5 Perché usare le varianti ottimizzate dei BTree...................................................................................255.6 Caratteristiche ...................................................................................................................................255.7 Costo delle operazioni ......................................................................................................................265.8 Altezza di un Btree.............................................................................................................................26

5.9 Operazioni Base.................................................................................................................................275.9.1 Divisione di un nodo Procedura SplitChild..............................................................................275.9.2 Inserimento .............................................................................................................................275.9.3 Fusione dei nodi Procedura Merge..........................................................................................285.9.4 Cancellazione..........................................................................................................................28

5.10 Codice B-Tree..................................................................................................................................305.10.1 B-Tree-Search(x, k)...............................................................................................................305.10.2 B-Tree-Create(T)...................................................................................................................305.10.3 B-Tree-Split-Child(x, i, y).....................................................................................................315.10.4 B-Tree-Insert(T, k).................................................................................................................315.10.5 B-Tree-Insert-Nonfull(x, k)...................................................................................................31

Indice Analitico

4

1 . Aspetti comuni e definizioni

Il problema dell'organizzazione dei dati in archivi deriva dalla necessità di conservare le informazioni nel tempo e di poterle reperire con facilità. Nella realtà quotidiana abbiamo spesso l’esigenza di trattare problematiche inerente alla conservazione e al reperimento di grandi quantità di dati, i quali, per po-ter essere gestiti correttamente, devono essere memorizzati secondo una logi-ca ben precisa, in modo tale che la ricerca e la consultazione possano essere gestite nel modo più efficiente possibile.

1.1 Introduzione: azienda, organizzazione, sistema informativo, sistema informatico

Informazione, azienda e organizzazione. L'azienda, qualsiasi tipo di azien-da, deve essere vista come un sistema le cui parti (ad esempio: reparto pro-duttivo, vendite, amministrazione personale, marketing, ricerca e sviluppo ec-cetera) devono essere coordinate in modo da raggiungere gli obiettivi per cui l'azienda stessa esiste. Ad esempio: per una classica ditta privata massimizza-re il profitto o, per una ONLUS, la quantità e la qualità dei servizi offerti. L'insieme delle persone che coordinano l'uso di tutte le risorse (capitali, per-sone, strutture, macchinari ecc.) a disposizione dell'azienda si chiama orga-nizzazione. L'organizzazione può svolgere efficacemente ed efficientemente il suo compito solo se ha a disposizione le informazioni necessarie. E per questa necessità fa affidamento sul cosiddetto sistema informativo.Il Sistema Informativo di un'organizzazione è l'insieme di procedure manua-li e automatiche e di risorse umane e materiali finalizzate alla gestione di in-formazioni (dati) rilevanti per la vita e la gestione dell'organizzazione. Ormai da decenni il sistema informativo è stato informatizzato. Il componente soft-ware più importante di ogni sistema informativo informatizzato è il DBMS (Data Base Management System) un software che gestisce gli archivi azien-dali.Il sistema informativo non va confuso quindi con la sua informatizzazione che si identifica usando la parola Sistema Informatico; quest'ultimo è un sottoinsieme del primo. In effetti possiamo definire il sistema Informativo come un insieme di procedure manuali ed automatiche e di risorse materiali (PC, rete dati, stampanti, fax,...) finalizzate alla gestoine su supporto elettro-nico di informazioni (dati) rilevanti per l'organizzazione. Le procedure auto-matiche in questo caso saranno svolte dai calcolatori.

1.2 Definizione di archivioUn archivio è una raccolta organizzata di informazioni, che possono essere elaborate in modo manuale (archivi cartacei), oppure automatico (nel caso di elaborazione tramite calcolatori).L’archivio, pertanto, è una struttura di dati astratta, costituita da un insieme di record. Ogni record all’interno di un archivio è identificato per mezzo della sua posizione, che costituisce il suo indirizzo logico.

1.3 Differenza fra archivio e fileGli archivi memorizzati su memoria di massa prendono il nome di file. Un file è un insieme di registrazioni omogenee, memorizzate in modo permanen-te su memoria di massa.Il file è quindi una struttura fisica di memoria in cui è possibile memorizzare informazioni sotto forma di sequenza di byte (file di byte) o sequenza di re-cord (file di record). Rappresenta, pertanto, la struttura concreta idonea a im-plementare la struttura astratta archivio. All’interno di un file ogni record è individuato tramite un indirizzo fisico.Un archivio è sempre implementato mediante uno o più file, ma un file non sempre è un archivio. Spesso nel gergo informatico, viene usato il termine “archivio” come sinoni-mo di “file”, ma tra i due termini c’è una differenza sostanziale.Ad esempio, i dati anagrafici degli studenti, una rubrica telefonica sono ar-chivi di dati e possono essere memorizzati su un disco come file di dati. Un programma scritto in linguaggio di programmazione, un documento scritto con Word, un foglio di Excel, pur essendo memorizzati come file, non costi-tuiscono un archivio, in quanto i dati contenuti non sono memorizzati secon-do una precisa organizzazione, come avviene invece negli esempi precedenti.

1.4 Record logico, chiave primaria e secondariaRecord: sono gli elementi che compongono il file. Più record si dicono omogenei se contengono tutti le stesse informazioni, nel-lo stesso ordine.Un record è formato da un insieme di campi (o attributi), ciascuno dei quali contiene una informazione. Si può pensare ad un file come a una tabella, le cui righe rappresentano le registrazioni (cioè ciascun record) e le cui colonne rappresentano sequenze di uno stesso campo.Esempio: archivio anagrafico relativo a un insieme di persone:Figura: AnagraficoCodice fiscale COGNOME NOME DATA DI NASCITA PROFESSIONE

RSSCRL…. Rossi Carlo 01/11/1961 avvocato

RSSCRL…. Rossi Carlo 18/02/1965 medico

2

BNCLST…. Bianchi Elisabetta 19/03/1970 insegnante

NRIGVN…. Neri Giovanni 31/07/1988 studente

Parlando genericamente di campo o attributo occorre sempre distinguere fra il suo VALORE ed il suo NOME. Ad esempio, con riferimento alla Figura - Ana-grafico, il nome di un attributo è PROFESSIONE, il suo valore può essere ad es. “avvocato”, “insegnante”, “medico”.

Un campo può essere formato da sottocampi. Ad esempio DATA DI NASCITA, potrebbe essere formato dai sottocampi: giorno, mese, anno. La struttura di un record è l'insieme dei campi che formano il record stesso. Tutti i record di uno stesso file hanno la stessa struttura. L'articolazione dei campi all'interno del record si chiama tracciato record, il quale informa sui dati registrati nel file, sul loro tipo e quindi sulle operazioni possibili.

Es. di tracciato record:Codice fiscale Cognome Nome Data di nascita Professione

Alfanumerico (20) Alfabetico (20) Alfabetico (15) Alfanumerico (10) Alfabetico (20)

Viene definita chiave primaria (Primary Key) un campo mediante il quale è possibile identificare in modo univoco i record all'interno di un file.Sono esempi di chiave primaria:

• il numero di matricola di uno studente universitario;• il numero del conto corrente bancario di un cliente; • il codice dell'articolo di magazzino;• il codice fiscale di una persona.

Viene definita Chiave Secondaria un campo mediante il quale è possibile identificare uno o più record all'interno dell'archivio; la chiave viene detta se-lettiva se il numero dei record selezionati è basso.Riepiloghiamo:

1. l'elenco anagrafico è un insieme di record contenente le informazioni sulle persone, quindi è un archivio;

2. ogni elemento dell'elenco, cioè l'insieme di tutte le informazioni relative allo stesso soggetto, è un record;

3. ogni informazione è un campo;4. la struttura fisica che contiene l'archivio elettronico dell'elenco anagrafico è il file;5. un programma memorizzato in un file di byte non costituisce un archivio.

Un archivio viene sempre creato, usato, aggiornato e distrutto, quando diven-ta obsoleto.

1.5 Record logici e record fisici, il concetto di bloccoI file sono memorizzati in memoria di massa, che è considerata una memoria aggiunta all’elaboratore. Per poter elaborare tramite un programma i dati pre-senti nel file è necessario prima trasferirli nella memoria centrale. È compito

3

del sistema operativo (file system) trasportare fisicamente i dati dalla memo-ria di massa alla memoria centrale e viceversa. Il trasferimento dei dati dalle unità di memoria periferica (memoria di massa) alla memoria centrale è detta operazione di INPUT (o LETTURA); l'opera-zione inversa (dalla memoria centrale alla periferica) è un'operazione di OUTPUT (SCRITTURA). In particolare, con l’operazione di lettura viene fatto un accesso alla memoria di massa e viene ricopiato una record dalla me-moria di massa alla memoria centrale. Con l'operazione di scrittura avviene il contrario e cioè il record presente nella memoria centrale viene copiato nella memoria di massa.Questa operazione riguarda un insieme di caratteri (e non un solo carattere alla volta) e viene detta blocco.Per quest'operazione di trasferimento tra periferica e memoria centrale, il computer utilizza una particolare zona di lavoro della memoria centrale detta buffer di I/O.

1.5.1 Il record logico

Finora abbiamo parlato di record come insieme di dati informativi relativi all'entità logica, definita a seconda delle esigenze dell'applicazione. Questa definizione coincide con quella di record logico, ossia la descrizione di come il programmatore vuole suddividere il gruppo di informazioni che ca-ratterizzano l'oggetto osservato (tracciato record). Il record logico ha una lunghezza in byte pari alla somma della dimensione dei suoi campi.Sulla memoria di massa dove risiede il file, invece, i record logici sono rag-gruppati in blocchi o record fisici (di lunghezza prefissata) e costituiscono l'unità di trattamento fisico.

1.5.2 Il record fisicoIl record fisico (o blocco) rappresenta l'insieme dei byte che possono essere letti o scritti in memoria di massa con una singola operazione di lettura o scrittura.Un blocco può contenere più record logici.Quindi le operazioni di lettura/scrittura su un file riguardano gruppi di record logici: in questo modo diminuisce il numero di accessi alla periferica (perché ogni volta che si accede alla periferica vengono letti o scritti più record alla volta), che sono operazioni più lente rispetto agli accessi ai dati contenuti nel-la memoria centrale.

1.5.3 Il fattore di bloccoSi chiama fattore di blocco il numero di record logici contenuti in un blocco.Tale numero può essere maggiore, minore o uguale a uno. In particolare:

4

• se è maggiore di uno, ossia se ogni record fisico contiene più record logici, i record si dicono bloccati;

• se è = 1, i record si dicono sbloccati;• se < 1, ossia se sono necessari più record fisici per memorizzare un record

logico, si parla di multiblocco.

Riportiamo un esempio di come un record logico costituito da due campi ri-spettivamente di 7 caratteri per il nome e da 2 caratteri per l'eta viene visto dal programmatore e dal file system:mentre il file system vedrà dei blocchi (record fisici) di 18 caratteri.

… R O S S I 5 7 B I A N C H I 4 2 V E R D I 2 4 …

1.6 Organizzazione degli archivi: organizzazione fisica e logicaGli archivi sono dati strutturati e formano un sistema organizzato per la con-servazione e il trattamento dei dati. Tale struttura è quindi caratterizzata da una organizzazione.Per organizzazione o implementazione di un archivio si intende sia il modo in cui esso è rappresentato sul supporto fisici di memoria, sia il modo in cui è elaborato.L’organizzazione, pertanto, si distingue in:FISICA: riguarda il supporto fisico di memorizzazione → dalla parte della macchina.LOGICA: riguarda le modalità di gestione dei file → dalla parte del pro-grammatore.Il supporto su cui sono memorizzati i dati individua l'organizzazione fisica e condiziona l'organizzazione logica. L'utente interagisce sempre con l'ar-chivio logico, ma deve sapere che questo si basa su un archivio fisico.

OrganizzazioneFisica Logica Supporti ad accesso sequenziale (Nastri) sequenziale Supporti ad accesso diretto (Dischi) sequenziale ad indici ad accesso diretto

1.7 Fattori che influenzano la scelta dell'organizzazioneLa scelta del tipo di organizzazione dell'archivio dipende da:

• il tipo di supporto fisico su cui sarà memorizzato il corrispondente file che rappresenta l'archivio astratto;

5

Record logico 1

Record fisico

Record logico 2 Record logico 3

• il tipo di operazioni che devono che devono essere effettuate sui file che rap-presentano l'archivio astratto;

• tempi e metodi di elaborazione: se le operazioni compiute sui file avvengono in modalità interattiva (online), occorre garantire tempi di risposta immediati; se, invece, le operazioni non sono interattive (offline), è accettabile un tempo di risposta più lungo;

• linguaggio di programmazione utilizzato: non tutti i linguaggi sopportano tut-ti tipi di organizzazione.

1.8 Tipologie di organizzazione dei file Saltiamo le considerazioni sugli aspetti hardware che concorrono alle presta-zioni di un sistema di memorizzazione e consideriamo quelle non meno im-portanti relative al modo in cui si decide di organizzare lo spazio di memoria dei supporti: sarebbe come avere a disposizione in squadra i migliori giocato-ri di calcio al mondo ma costringerli a giocare con tattiche da cortile! Attenzione però non stupiamoci se alle volte può essere quella da cortile la tattica giusta: è un modo per affermare che non c'è in assoluto “il modo mi-gliore” di organizzare un archivio ma che sono tutti sempre disponibili ai pro-grammatori a seconda delle situazioni. Fondamentalmente si hanno quattro possibilità: organizzazione sequenziale, organizzazione ad accesso diretto (chiamata anche random o relative), orga-nizzazione ad indici, hashing, BTree. Nel proseguo vedremo in dettaglio tutti questi argomenti.

6

2 . Gli archivi sequenziali

2.1 Archivi ad organizzazione sequenziale

2.1.1 Operazioni: inserimento, aggiornamento, cancellazione, ordinamento, ricerca

3 . Archivi sequenziale con indice

Vediamo le proprietà di questo tipo di organizzazione. Questo tipo di archivi possono essere registrati solo su supporti di memoria di massa, supporti fisi-ci, ad accesso diretto. Quindi sebbene abbiano una struttura logica sequenzia-le l'accesso ai record ammesso è sia sequenziale che diretto.

3.1 La struttura dell'archivio indice e dell'archivio principaleSi possono distinguere, principalmente, due elementi fondamentali detti in gergo rispettivamente archivio indice e archivio primario.L'archivio primario è caratterizzato da record consecutivi (sequenziali) che possono essere registrati in modo non ordinato, ordinato, non ordinato e rag-gruppato (per pagine), ordinato e raggruppato (per pagine).L'archivio indice o dizionario, necessariamente ordinato, ad un livello oppure anche costruito su più livelli (gerarchia di indici). Gli elementi dell'archivio indice/indici sono generalmente composti da due campi: un campo chiave kh contenente la chiave del record, e un campo puntatore P contenente la posi-zione del record all'interno dell'archivio.

3.2 Operazioni: inserimento, aggiornamento, cancellazione, ordinamento, ricerca

Per questo tipo di archivi vedremo quindi tutte le operazioni come sono logi-camente implementate.

3.2.1 Ricerca e scansione in struttura sequenziale con indice e archivio primario non ordinatoQuindi con questo tipo di organizzazione, accanto alla zona dove sono regi-strati i record nell'ordine di immissione, viene gestita una tabella delle chiavi: la ricerca del record avviene leggendo la tabella delle chiavi e non i record come succede nei file sequenziali. In questo modo l'utente può accedere diret-tamente al record specificandone solo la chiave, senza dover scorrere tutti quelli che lo precedono.Si utilizza questa organizzazione quando si deve elaborare un solo record alla volta, cioè quando si devono effettuare operazioni locali (ad es. modificare l'indirizzo di un cliente). È possibile comunque accedere a tutti i record del file leggendoli in modo sequenziale a partire dal primo, sempre seguendo l'ordine delle chiavi.

Possiamo notare come la dimensione dell'archivio indice è pari alla dimensione dell'archivio primario in quanto la funzione è biunivoca.

Si tratta però di una soluzione dispendiosa sia in termini di occupazione di memoria che di tempo di accesso.

3.2.2 Ricerca e scansione in strutture sequenziali con indice e archivio primario ordinatoSe però manteniamo ordinato anche l'archivio primario allora è possibile an-che la seguente implementazione che prevede la suddivisione dell'archivio primario in pagine o sottoarchivi.L'archivio indice, ordinato nelle chiavi, non contiene più tutte le chiavi ma solo la chiave più alta per ciascuna pagina; il record ora è del tipo (Kh,P) dove Kh è la chiave più alta che troviamo nel sottoarchivio con numero P (ovvero nell'implementazione fisica si tratterà ancora di un puntatore che punta all'ini-zio della pagina di memoria).

Algoritmo di ricerca di una chiave K:Vediamo quindi in linguaggio naturale l'algoritmo di ricerca di un record nel file primario usando come entry la chiave K.

1. Ricerca nell'archivio indice la prima chiave Kh>=K2. Accedi al sottoarchivio P associato alla chiave Kh3. Ricerca (binaria, sequenziale, interpolata) della chiave K

nel sottoarchivio P

Algoritmo di scansione sequenziale di tutti i recordNel caso si voglia la semplice elencazione di tutti i record ordinati secondo la chiave Kh l'algoritmo di visita è rappresentato da:

1. Finchè ci sono chiavi Kh nell'archivio indice2. accedi al sottoarchivio P associato alla chiave Kh3. scandisci in sequenza tutti i record della pagina

10

Testo 3.1: Disegnare un esempio di figura che mostri il mapping fra Archivio Indice e Sottoarchivi o Archivio primario paginato.

3.2.3 Inserimento e cancellazione in strutture sequenziali con indice e archivio primario ordinatoOra le operazioni di inserimento e di cancellazione avvengono comunque in un archivio sequenziale ordinato e che come sappiamo sono fonte di proble-mi. Ma la soluzione che abbiamo visto in precedenza fa uso di apposite aree di overflow (distribuite o concentrate) e che periodicamente poi saranno sog-gette a “fusione” come si è detto.Una delle tecniche che viene usata più frequentemente prevede che l'archivio indice sia strutturato con record del tipo (Kh,P, Khovf, Povf), dove Kovf e Povf indicano rispettivamente la chiave più alta e il puntatore di accesso a tale area (kovf chiave di overflow, Po\vf puntatore all'area di overflow).

Se ora proviamo ad inserire il record di chiave 58 possiamo vedere che l'inse-rimento andrebbe eseguito nel sottoarchivio P=2 ma questa pagina risulta es-sere piena ecco allora che dobbiamo procedere all'inserimento di un record nell'area di trabocco o overflow e questo lavoro può essere fatto seguendo questa soluzione di massima:

Algoritmo di inserimentoSono verificate le seguenti due ipotesi:- Siano Kh' l'ultima chiave presente nella pagina P- Ktrab la chiave traboccata ovvero che non può essere inserita nella pagina P perché ormai piena.

PROCEDURE Inserimento (record chiave K)BEGIN Ricerca nell'archivio indice la prima chiave Kh o Kovf > di K IF K < Kh Then Inserisci il record nella pagina P osservando l'ordinamento If c'è trabocco di pagina con Ktrab Then inserisci in testa all'area di overflow il record traboccato If è il primo trabocco Then sostituisci (Kh,P,Nil,Nil) con (Kh',P,Ktrab,Povf)

11

20

85

190

214

1 Nil Nil

Kh P Kovf Povf

2

3

4

Nil Nil

Nil Nil

Nil Nil

2

5

20

... ... ...

K Altri dati info

... ... ...

... ... ...

SOTTOARCHIVIO1

48

52

85

... ... ...

k Altri dati info

... ... ...

... ... ...

SOTTOARCHIVIO2

Else sostituisci Kh con Kh' EDNIF ENDIF Else Inserisci il record nell'area di overflow rispettando l'ordinamento ENDIFEND;

N.B. Questo algoritmo non prevede la gestione di quando l'area di trabocco viene completamente riempita!

Inoltre l'area di trabocco può essere distribuita o concentrata come si è detto ma in genere nelle implementazioni si preferisce riservare un'area di overflow ogni N sottoarchivi dell'archivio primario.

3.3 Indici multipli o a più livelli (file ISAM)Nel caso in cui il numero di sottoarchivi diventi rilevante e, di conseguenza, il numero di record presenti nell'indice (al livello 1) cominci a diventare con-siderevole (appesantendo la ricerca), è possibile organizzare l'archivio indice come un archivio sequenziale con indice. Si dà così luogo a sottoindici di differente livello, che permettono una dimi-nuzione del tempo di scansione dell'indice stesso.Un indice a due livelli è costituito per esempio dall'indice analitico di un li-bro:

1. si ricerca la lettera corrispondente alla parola che si vuole trovare2. nel blocco che racchiude tutte le parole che iniziano per la lettera in questione si cer-

ca la parola e si preleva il numero di pagina3. si apre il libro alla pagina ottenuta e si leggono le informazioni

Il primo livello è rappresentato dalle lettere dell'alfabetoIl secondo livello è costituito da tanti indici quanti sono le lettere e ciascun indice è composto da tutti i termini che iniziano con la lettera collegata.

12

4 . Gli archivi non sequenziali

4.1 Archivi ad organizzazione relative...

4.2 Archivi ad organizzazione hashBibliografia

Pag. 263 “Niklausus Wirth Algoritmi+Strutture Dati = Programmi” - Ed. Tecniche Nuove (versione italiana)Pag. 307 Paolo Camagni “Algoritmi Strutture dati e programmazione ad oggetti” - vol. 2 - Ed. Hoepli.

4.2.1 IntroduzioneL'idea di organizzare gli archivi sfruttando la tecnica hash nasce dalle tabelle di hash. Una tabella di hash è una struttura di dati costruita in RAM e la sua idea parte dalle seguenti considerazioni:

• Una tabella hash è una struttura di dati dinamica efficace per realiz-zare i dizionari.

• Una tabella hash è la generalizzazione del più semplice concetto di array ordinario.

È una tecnica di accesso diretto all'informazione memorizzata (su array e/o file).

La tecnica Hash si basa sull'utilizzo di funzioni che, partendo dalla chiave primaria Kh di ciascun record, trasforma quest'ultimo in un numero intero, che rappresenta l'indirizzo logico, detto indirizzo Hash, del record stesso.

Più in generale, applicare la tecnica Hash significa definire una funzione di randomizzazione H (funzione Hash) che associ a ogni record l'indirizzo di un record logico in cui è possibile memorizzarlo, attraverso la trasformazione della chiave Kh in un numero intero x:

H k =x

4.2.2 Tabelle hashSono strutture di memorizzazione interna alle quali si accede alla posizione di

memorizzazione del dato di interesse con tecnica ad indirizzamento immedia-to. Questa proprietà è garantita da un opportuno algoritmo di randomizzazio-ne.

4.2.2.1 Algoritmi di randomizzazioneIl problema è quello di memorizzare un certo oggetto (in genere un record) avente una chiave o numerica o alfanumerica all'interno di un array (o tabella1) o più in generale un archivio non sequenziale (implementato poi come file ad accesso diretto). Essendo la chiave numerica o alfanumerica distribuita casualmente in un cer-to intervallo o insieme2 e dal momento che l'elaboratore non tratta diretta-mente tali chiavi3 è necessario inserire nel programma un algoritmo di ran-domizzazione per ottenere chiavi numeriche uniformemente distribuite. In questi casi l'algoritmo precede l'operazione di seek(record, n) in quanto n esprime il valore calcolato.

Es. Gestione automatizzata di una biblioteca. Codice a 4 cifre: armadio, scaffale e due cifre per la posizione del libro nello scaffale. Il codice 2304 indica che il libro è il 4 del 3 scaffale nel 2 armadio. Provare a pensare ad un tracciato record per l'archivio dei libri.

L'algoritmo deve produrre una corrispondenza biunivoca tra il codice “logi-co” del libro e l'indirizzo fisico del record. Se indichiamo con K la chiave nu-merica e con N la posizione nel file la formula che fornisce la corrispondenza biunivoca è: N=(C1-1)*S*L+(C2-1)*L+C dove C1, C2, C sonoC1 = INT(K/1000)C2 = INT((K-C1*1000)/100)C = K – C1*1000-C2*100Dove in questa formula si sarà fissato il numero massimo di libri per scaffale L, il numero massimo di scaffali per armadio S.Se poi fisicamente i record devono essere allocati a partire dall'indirizzo I, la determinazione di N si ottiene dall'assegnazione N = (I-1) + N.

4.2.2.2 Introduzione agli Algoritmi di hashingSono algoritmi di randomizzazione che trattano chiavi alfanumerica e l'idea di fondo è quella di trattare i caratteri della chiave come se fossero numeri, e di associare ad ogni chiave il numero ottenuto mediante un qualche procedi-mento di calcolo. Il numero è l'hash-indirizzo del record ed indica la posizio-ne del record all'interno dell'archivio-file (o del vettore o della tabella).L'esempio che propongo è tratto da un articolo di D. E. Knuth.L'idea è quella di trattare le parole come se fossero dei numeri a=1, b=2,... e quindi ottenere da ogni parola un singolo numero mediante un qualche proce-dimento di calcolo. Se consideriamo come chiavi di un record le 31 parole

1 Una tabella è semplicemente un array di record.2 L'insieme U di distribuzione delle chiavi ha un sua dimensione dim(U) che può essere minore maggiore o uguale alla

dim(T) dell'array/tabella/archivio sul quale andiamo a depositare i record vedere successivamente per una spiegazione maggiormente dettagliata.

3 Non è in grado di far corrispondere una posizione a partire da una chiave alfanumerica, è necessario operare una qualche trasformazione per ottenere così un numero n naturale.

14

più comuni della lingua inglese si può convertire ogni chiave in un numero compreso fra 1 e 32 sommando il valore delle rispettive lettere e prendendo il resto della divisione per 32 (definizione della funzione hash!).“the” = (20+8+5) mod 32 =1“of”=(15+6) mod32 = 21 e così via per tutte le 31 chiavi.La condizione di funzionamento dell'algoritmo richiede che il numero di re-cord m della tabella sia maggiore almeno di una unità rispetto alle 31 chiavi; nell'esempio prendiamo m = 32.

ALGORITMO DI INSERIMENTON = H(z)fino a quando l'indirizzo N è pieno (collisione) se N = 1 poni N = 32 altrimenti N = N-1scrivi il record di chiave z nella posizione N

Suppongo di immetterle ordinate secondo la loro frequenza: the[1], of[21], and[19], to[3], a[1,32] (non si hanno collisioni fino alla 'a' ) .Dopo aver riempito il file avremo che la posizione 5 è libera e se cerco 'do' che vale 19 scorrendo tutto il file a ritroso mi fermo nella posizione 5 e dico che non c'è!

ALGORITMO DI RICERCACalcola N = H(z)esegui fintanto che non Trovato o Vuoto;

se la chiave in N è x allora Trovato se la chiave in N non esiste è Vuotoaltrimenti scorri a ritroso N.

SvantaggiQuesta tecnica che organizza i file in modo direct presenta l'indubbio vantag-gio di consentire un accesso veloce ad un qualsiasi record ma ha come suo li-mite il vincolo che impone record di lunghezza prefissata e quindi in sede di creazione del file risulta fissata la sua lunghezza e la conseguente occupazio-ne nella memoria di massa che lo ospita: N·L byte è la lunghezza del file di N record lunghi L byte. Tale spazio è sempre occupato anche se il numero dei record è molto inferiore a N.Per risolvere questo problema si passa ai file sequenziali con indice ....

4.2.2.3 La funzione H(.) e il suo fattore di caricoQuindi la tecnica si basa su una funzione detta di hashing H(.) (tecnica di hash) che mappa un certo insieme di chiavi (Universo delle chiavi) U in un secondo insieme T (tabella[0, ... , m-1]).Gli insiemi o spazi U e T possono avere diversi rapporti fra le loro dimensio-ni; il parametro fondamentale α viene definito fattore di carico o di riempi-mento:

15

= n ,numero di chiavi K al momento memorizzatem ,dimensione tabella T al momento disponibile

L'ordine di complessità di questi algoritmi è O(1).Classe di complessità4: O(1) o O(C), che indica la complessità degli algorit-mi che eseguono lo stesso numero di operazioni indipendentemente dalla di-mensione dei dati di input. Quindi questa tecnica garantisce un tempo di accesso costante all'informazio-ne.La tecnica di hash è usata non soltanto della gestione degli archivi ma trova largo impiego in informatica come ad esempio negli algoritmi di cifratura delle firme digitali (MD5 Rivest 1992, un messaggio M in input di lunghezza arbitraria genera in output un message digest (128 bit); questo indirizzo x viene visto come una rappresentazione non ambigua e non falsificabile del messaggio M), nei compilatori di linguaggi (le parole chiave del linguaggio sono viste come chiavi stringa, vedi l'esempio introduttivo sopra esposto di D.E. Knuth!), in programmi di crittografia (il famoso PGP pretty good priva-cy ideato nel 1991 dallo statunitense Philip Zimmermann)

Come funziona la tecnica hash?

Consiste nell'individuare una funzione chiamata funzione di hash che faccia passare dalla chiave k alla posizione x di una tabella T[0..m-1] chiamata ta-bella di hash. Quindi l'elemento di chiave k viene memorizzato nella tabella proprio in posizione x.Facciamo ora un esempio. Supponiamo che h(k)=2·(k-1) e che le chiavi k sia-no numeri interi nel range 1 – 100 (universo di valori U). Possiamo osserva-re le posizioni x di memorizzazione dei dati associati alle chiavi 1,2,10,90,100. Calcoliamole: 0, 2, 18, 178, 198.In questo esempio possiamo osservare che abbiamo un raddoppio della di-mensione della tabella dim(T) = m rispetto alla dimensione dim(U) = n del-l'universo delle chiavi. Verificare che la metà delle posizioni della tabella non sono occupate mai da nessun dato (quelle con indirizzo dispari);

Dare la definizione del fattore di carico α?

Definizio fattore di carico o di riempimento di una tabella è il rapporto dim(U)/dim(T) = α Il suo significato è legato al valore medio del numero di chiavi che mediante la funzione h( ) vengono mappate nella medesima posizione o indirizzo della tabella T, si tratta delle collisioni di indirizzamento.

α < 1Nell'esempio abbiamo che α=100/200 =0,5 e quindi nessuna chiave genera

4 pag. 15 Piero Gallo Fabio Salerno “Informatica Generale Teoria e tecnologie digitali dell'informazione e della comunicazione” - vol. 2 - Ed. Minerva

16

mai il medesimo indirizzo.

α = 1Se invece usiamo una funzione iniettiva del tipo h(k)=k-1 si ha che α=100/100 =1 e quindi nessuna chiave genera mai il medesimo indirizzo e nessuna posizione della tabella rimane vuota: si tratta di una tabella a indiriz-zamento diretto del tipo “tabelle con indice”.

Quale scopo ha la funzione di hash?

La funzione h() ha lo scopo di ridurre drasticamente la dimensione U ovvero di mappare le chiavi k in una tabella T molto più piccola della dimensione di U. Quindi indipendentemente dalla dimensione n=dim(U) del problema avre-mo una complessità O(1) costante, ovvero un tempo costante per l'accesso ad ogni elemento associato alla chiave k da cercare in T.

Le collisioni che cosa sono?

Le collisioni entrano in gioco proprio a causa di questa diversità nelle dimen-sioni fra U e T. La funzione di hash non è più iniettiva e quindi ora può acca-dere con sempre maggior probabilità che k1 e k2 abbiano lo stesso indirizzo nella tabella T. Le collisioni vanno gestite opportunamente e vedremo le di-verse tecniche ma possiamo dire fin d'ora che le soluzioni dovranno essere tali da limitare la perdita delle prestazioni che la tecnica subisce anche con elevati coefficienti di collisione.

Come viene scelta una buona funzione di hash?

1. Sia facilmente calcolabile; cioè composta da calcoli che siano i più semplici possibile, in modo da non appesantire il procedimento di conversione della chiave e diminuire, così, il tempo di accesso;

2. Deterministica cioè produca sempre lo stesso indirizzo o posizione a partire dalla stessa chiave K;

3. Criterio dell'uniformità semplice deve generare gli indirizzi x unifor-memente distribuiti nell'ambito dell'archivio ovvero vengono generati indirizzi in modo equiprobabile in T;

4. Generare indirizzi casualmente distribuiti nell'ambito dell'archivio an-che quando le chiavi sono simili (ad esempio X1,X2,... oppure chiavi anagramma o quasi anagramma DARE, MARE, CARE);

5. Copra per quanto possibile l'intero intervallo degli indirizzi nell'archi-vio evitando, se possibile, che ci siano indirizzi che non vengono mai generati;

6. Criterio di generazione completa: deve utilizzare tutte le cifre della chiave (che nel caso di chiavi alfanumeriche è un criterio più diffici-le da rispettare)

7. Generi indirizzi diversi se le chiavi sono diverse.

17

Trasformazione perfetta.

Relativamente all'ultimo punto, quindi, la funzione ideale è quella che a ogni valore della chiave primaria fa corrispondere sempre un indirizzo diverso, di modo che ogni record possa essere raggiunto tramite un solo accesso. Quan-do ciò accade si parla di trasformazione perfetta.

Se la chiave alfanumerica è solo chiave numeriche

Per queste chiavi la funzione è semplice: x = K mod n; le collisioni prendono anche il nome di sinonimi.

Chiavi alfanumeriche

Un metodo molto usato è quello di stabilire la conversione tra sequenze di simboli interpretati come numeri in sistemi di numerazione in base diversa che permetta di rappresentare tutti i simboli alfanumerici utilizzati nella chia-ve. In genere si usa la codifica ASCII come sistema di numerazione in base a 128.ali (97,108,105) = 1.603.177baba (98,97,98,97)=205.041.890

97⋅1282108⋅1281105⋅1280 è cioè un polinomio di grado 2 nella base 128L'algoritmo che trasforma una chiave alfanumerica in un numero intero com-preso fra 0 e n dimensione della tabella T.

- trasformare ogni carattere nel corrispondente codice ASCII decimale- sommare i singoli termini con il loro peso ( 128n )- applicare la funzione di hash

Per esempio chiave k alfanumerica= “ali” chiave numerica = 1.603.177 si corrisponde con l'indirizzo k mod 1024 = 617.

NB. mod 1024 mi da i resti che vanno da 0 fino a 1023: quindi un vettore con 1024 posti da gestire.

Perché è necessario spezzare le chiavi troppo lunghe?

La funzione di hash in questo caso è detta funzione di hash modulare infat-ti questa trasforma un pezzo di chiave alla volta e somma i risultati parziali. Si basa sull'algoritmo di Horner che sfrutta le proprietà aritmetiche dell'ope-razione di modulo. s⋅12811a⋅12810Partendo dalla prima lettera della chiave alfanumerica:

- numeric_key=(“s”*128+“a”)- ripetendo (numeric_key * 128 + prossimo_car_chiave_alfa)

Ma a noi non interessa il risultato anche perché produrrei comunque un over-flow, ma soltanto il re sto della divisione per m (con m=1024 in questo esem-pio)

- x=(“s”*128+“a”) MOD 1024

18

- ripetendo (x * 128 + prossimo_car_chiave_alfa) MOD 1024

4.2.3 Categorie di funzioni hash

Quali tipi o categorie di funzione hash ci sono?

4.2.3.1 A divisione Sono quelli che abbiamo visto appena sopra; bisogna prestare attenzione ai valori di m che devono essere diversi dalle potenze del 2 o del 10, l'esperien-za mostra che una buona scelta per m è un numero primo non troppo vicino alle potenze del 2.PRO e CONTRO: Molto veloce ma ci sono valori critici per m dimensione della tabella T.

4.2.3.2 A moltiplicazione La chiave k viene moltiplicata per una costante A compresa in [0,1] e si estrae la parte frazionaria del risultato (MOD 1), il risultato viene poi moltiplicato per m e se ne prende la sua parte intera.PRO e CONTRO: Il vantaggio del metodo della moltiplicazione rispetto a quello della divisione è di non avere valori critici per m.

4.2.3.3 Metodo della funzione universale Dato che al verificarsi di una collisione è necessario attuare una tecnica di ge-stione particolare per generare un nuovo indirizzo sulla medesima chiave in modo che sia diverso dal precedente e questo potrebbe richiedere numerose operazioni aggiuntive e, quindi, all'aumentare della frequenza delle collisioni viene rallentato l'accesso alla struttura dati, peggiorando le prestazioni allora l'idea è quella di usare una seconda funzione hash eventualmente una terza ... (ho una famiglia di h( ) ciascuna con una sua particolare proprietà e sono scelte in modo pseudocasuale). Con questo metodo si riduce a zero la proba-bilità che esista un insieme di chiavi che porti al caso peggiore: tutte le chiavi sono sinonimi.

4.2.4 Gestione delle collisioniRicordiamo ancora la definizio di fattore di carico o di riempimento di una ta-bella è il rapporto dim(U)/dim(T) = α Come abbiamo detto questo valore esprime la probabilità media di collisione. La soluzione si basa principalmente sulle seguenti due strategie:

1. metodo di concatenazione (chaining)2. metodo di indirizzamento aperto (open addressing)

Ci sono diverse varianti nel metodo di concatenazione a seconda che i record che collidono vengano poi memorizzati in un'area di overflow oppure nella stessa area primaria.

19

4.2.5 Chaining o metodi di concatenazione

4.2.5.1 Tramite liste separate α qualunqueLa tabella si riduce cioè ad un vettore di puntatori a record; ogni elemento del vettore punta quindi alla testa di una lista di elementi. In ogni lista il numero medio di elementi memorizzati è pari al fattore di carico. Nel caso in cui tutti gli elementi collidono, caso peggiore, il tutto si riduce ad un'unica lista di lunghezza n e in questo caso la complessità di calcolo diventa O(n). Ma tale caso non viene contemplato se la funzione di hash verifica il criterio dell'uni-formità semplice così ogni lista ha lunghezza α e il tempo medio di accesso risulta essere O(1+ α).

4.2.5.2 Chaining tramite liste confluenti α qualunqueGenero una unica lista per ogni gruppo di p chiavi non sinonimi, in questo caso la lista ha una lunghezza media pari a pα. Introduco un ritardo rispetto al caso precedente nel recupero dell'informazione.Usato raramente.

4.2.5.3 Chaining in area separata (area di overflow o dei trabocchi) α < 2Si tratta del caso limite della precedente: si usa una unica lista e la si memo-rizza in un'apposita area di overflow diversa da quella primaria. Questa tecnica è usata in archivi in cui si ha un numero limitato di chiavi m e il valore di α è inferiore a 2. Il tempo medio di accesso per ritrovare un ele-mento è O(1+m α/2).

4.2.6 Open addressing o metodo di indirizzamento aperto

4.2.6.1 tecniche di scansione: lineare, quadratica, hashing doppio α < 1In questa seconda soluzione si sfrutta l'idea di memorizzare tutti gli elemen-ti nella tabella stessa e quindi si evita la complicazione di dover gestire liste oppure aree aggiuntive: al verificarsi di una collisione si registra l'elemento nell'area “successiva”; sembrerebbe paradossale in quanto forse vado ad au-mentare il numero di collisioni! È infatti necessario dire subito che questa considerazione è vera ma se si sceglie una condizione su α che deve essere sempre inferiore a 1 allora il metodo funziona bene. Questa condizione sul fattore di carico significa che il numero totale degli elementi n è sempre mi-nore del numero totale delle posizioni m nella tabella e dunque anche se fos-sero presenti tutti i record nella tabella sarebbero lasciate libere molte posi-zioni.

La funzione che genera la scansione è pseudocasuale

Le funzioni che determinano la sequenza di scansione devono soddisfare allo stesso principio di uniformità che la funzione hash verifica: la sequenza di scansione deve essere in certa misura pseduocasuale in modo da limitare la sovrapposizione delle catene ovvero limitarne la loro intersezione.

20

Le soluzioni che si propongono possono essere classificate nelle seguenti tre famiglie:

1. scansione lineare (linear pobing)2. scansione quadratica3. hashing doppio

• Nella scansione lineare come si inserisce un elemento che ha subito una collisione?

• Nella scansione lineare esiste il problema della agglomerazione (clustering) primaria di che cosa si tratta? ... si creano lunghi tratti in cui tutte le posizioni sono occupate

• Nella metodo a scansione lineare come si cerca un elemento?• Nella scansione lineare che cosa si deve fare quando si cancella un elemento

compreso in una sequenza dal vettore? • Nella scansione lineare si ottiene un miglioramento se si cambia il passo di

scansione da 1 a 2 o 3 perché non si generano più posizioni adiacenti ma rimane un problema quale? ... le catene si sovrappongono o si intersecano!

Esempio: h(k)= K MOD 31 e s=2 le chiavi 1206 e 218 generano le se-quenze:

(28; 30; 1; 3; 5; 7; 9; ...) e (1; 3; 5; 7; 9; ...) dove è immediato comprendere che le due sequenze si intersecano nel punto “1” e poi da li in avanti coincido-no!

• Nella tecnica della scansione quadratica quale formula genera le sequenze dei posti dopo una collisione? ... c1⋅ic2⋅i2 dove c1 e c2 sono costanti vincolate, da determinarsi volta per volta, per poter utilizzare tutte le posizioni della tabella!Esempio: c1=0 e c2=1 allora la formula che permette di determinare la se-quenza è: h k =k MOD 311⋅i2MOD 31 e le due chiavi dell'esempio precedente ora generano le sequenze: (28; 29; 1; 6; 13; ...) e (1; 2; 5; 10; 17; ...) che si intersecano ma non si sovrappongono.

Per risolvere il problema delle agglomerazioni e approssimare in modo mi-gliore la proprietà di uniformità, si ricorre al metodo dell'hashing doppio il quale ha:

1. h1 usata per la prima posizione

2. h2 per generare i valori di salto ( s=h2 k )

Esempio: una tabella di 13 elementi con le seguenti funzioni di hash: h1=k mod 13 e h2=1k mod 8 .

21

5 . Organizzazione ad indici B-Tree

5.1 IntroduzioneInnanzitutto precisiamo che si tratta di una variante dell'organizzazione ad in-dici multilivello.Sappiamo infatti che l’indice è mantenuto in una forma che rende assai velo-ce trovare i valori che interessano (un certo codice o un certo cognome ecc.): ad esempio potrebbe essere ordinato (per sfruttare una ricerca dicotomica) ed eventualmente strutturato come un albero binario di ricerca; è proprio in que-sto contesto che nasce la fortunatissima tecnica che sfrutta una forma modifi-cata degli alberi binari, i “Btree” per l'appunto, che oltre a beneficiare in ri-cerca delle caratteristiche di un albero bilanciato ha una idea organizzativa fondamentale: quella di raggruppare più chiavi in uno stesso nodo dell'albero in modo che questo blocco di dati corrisponda per dimensione a quel del blocco fisico che il dispositivo di memorizzazione può leggere o scrivere con una sola operazione in modo da ottimizzare il numero di queste ultime.

NB. I B+tree sono utilizzati da tutti i principali DBMS.

5.2 BTreeI BTree sono alberi bilanciati di ricerca progettati per essere memorizzati su memorie esterne tipicamente più lente rispetto a quelle interne. Quindi la mi-sura di efficienza (principale) non è il tempo necessario per accedere ad un determinato dato, ma la quantità di operazioni di I/O effettuate. In un BTree esistono strategie per mantenere bassa l'altezza dell'albero dato che, in tutte le operazioni effettuate, il numero di I/O aumenta con l'aumentare dell'altezza.Esistono poi delle varianti ottimizzate dei BTree come B*Tree, Btree+, Btree++.

5.3 Obiettivo limitare le operazioni di I/OIn informatica quando si cerca di risolvere un problema l'analisi è una parte vitale dell'intero processo di progettazione. I due aspetti da considerare prin-cipalmente sono:

• i tipi di dati sui quali lavorare• le operazioni da eseguire su quei dati per ottenere il risultato voluto.

I due aspetti sono strettamente legati fra loro e la scelta della struttura dati in-fluenza l'algoritmo in modo significativo. In molti casi sono possibili più strutture dati alternative tutte apparentemente idonee a risolvere ugualmente bene il problema. L'analisi preliminare dei costi in termini di operazioni necessarie, consente di preferire una struttura rispetto alle altre: infatti nel caso in cui viene scelta una struttura dati non ottimale potrebbe accadere di dover scrivere degli algo-ritmi estremamente complessi in casi in cui questo è evitabile. Tra le operazioni che i calcolatori sono in grado di svolgere, la memorizza-zione delle informazioni comporta l'utilizzo di una unità esterna (oltre la RAM che viene intesa memoria interna). La memoria esterna più comune è l'Hard Disk la cui struttura è costituita da uno o più piatti ricoperti da materia-le magnetico su entrambe le facce. Le unità possono avere dieci o più piatti disposti uno sull'altro su un asse passante per il centro del piatto. Ciascuna delle superfici è fornita di una propria testina di lettura e tutte le te-stine si muovono insieme verso l'interno o verso l'esterno, per leggere l'infor-mazione che si trova a differenti distanze dal centro. Per leggere o scrivere un determinato byte su un disco, dobbiamo:

1. posizionare le testine in modo che una di esse stia sopra la traccia del byte prescelto;

2. aspettare che, per la rotazione del disco, il byte prescelto si posizioni sotto la testina. Ciascuna operazione può impiegare, in media, qualche centesimo di secondo; il tempo, in realtà, dipende non solo dalle caratteristiche dell'unità a disco, ma anche dal numero di tracce che le testine devono attraversare e dalla posizio-ne del byte rispetto alle testine, nel momento in cui queste raggiungono la traccia. Spesso il tempo necessario per accedere e leggere una informazione memo-rizzata in un disco magnetico è superiore al tempo necessario all'elaboratore per esaminare tutta l'informazione letta!

Proprio per questo motivo, quando occorre lavorare con grandi quantità di dati è spesso impossibile (o non opportuno) mantenere l'intera struttura dati all'interno della RAM.

Invece è fortemente consigliato tenere in RAM una piccola porzione di strut-tura dati e quando necessario recuperarne altre porzioni dalla memoria di massa. I dati inseriti in RAM possono venire manipolati con una maggior ve-locità grazie ai tempi di accesso 105 volte superiori a quelli della memoria secondaria. In conclusione possiamo dedurre che la performance globale dipende non più dalla velocità di accesso di un “singolo dato (item)” ma dalla quantità di ope-razioni di Input/Ouput che vengono eseguite per risolvere l'intero problema.

24

5.4 Perché usiamo i BTree?I BTree sono alberi bilanciati di ricerca progettati per le operazioni sui dischi magnetici o altri dispositivi di memoria secondaria ad accesso diretto. Grazie all'uso della struttura dati ad albero e la caratteristica di poter memorizzare più chiavi in un nodo-pagina, il BTree (o Balanced Tree) è la struttura dati migliore per la gestione sia delle memorie interne che di quelle esterne. Infatti il BTree è ottimizzato per mantenere più elementi in un singolo nodo-pagina (infatti può corrispondere ad una pagina della memoria virtuale da qui il nome usato in questo contesto) cosicché vengono minimizzati i tempi di accesso al disco per trovare la chiave richiesta. Il numero di elementi in un nodo è legato al “grado t di ramificazione” dell'albero. Un grado di ramificazione elevato riduce sensibilmente sia l'altezza dell'albe-ro, che il numero di accessi necessari a trovare una chiave qualsiasi.

5.5 Perché usare le varianti ottimizzate dei BTreeLe varianti dei BTree hanno l'obiettivo di diminuire il tempo di accesso per letture sequenziali dei dati, al fine di incrementare le prestazioni in quelle ap-plicazioni che richiedono sia un accesso random che sequenziale (per es. streaming Video/Audio o grandi database).

5.6 Caratteristiche

I BTree sono alberi bilanciati di ricerca, i cui nodi possono avere anche parec-chi figli, da poche decine a diverse centinaia, a seconda dal valore del grado minimo t, o fattore di ramificazione dell'albero che può variare da 3 a molte centinaia. Un nodo che contiene n chiavi avrà n+1 figli. Le chiavi sono sostanzialmente punti di divisione: dividono l'intervallo di chiavi gestite dal nodo in n+1 sot-to-intervalli, dove ciascun sotto-intervallo è gestito da un figlio. Il grado minimo t, o fattore di ramificazione, definisce i limiti superiori e in-feriori del numero di chiavi presenti in un nodo, con la seguente regola:

Nel caso in cui il numero di elementi in un nodo è uguale al limite inferiore/superiore il nodo stesso si dice magro/pieno.

25

I nodi a profondità massima vengono chiamati foglie, tutte le foglie sono alla stessa profondità che coincide con altezza dell'albero. In un BTree con n chiavi il più lungo percorso dalla radice ad una foglia qual-siasi è al più:

logt n1

2

Il bilanciamento è garantito dal metodo di inserimento e cancellazione delle chiavi ed è molto importante. Infatti se consideriamo che un nodo può essere contenuto nella memoria pri-maria e che per leggere un altro nodo bisogna effettuare una lettura in memo-ria esterna, il bilanciamento aiuta ad ottimizzare lo spazio contenuto in un nodo risparmiando il costo di un'eventuale lettura su un albero sbilanciato.

5.7 Costo delle operazioni Poiché la visita di un nodo in un BTree richiede un accesso alla memoria se-condaria, il numero di nodi visitati durante un'operazione forniscono una mi-sura dei costi che è quasi sempre proporzionale all'altezza.

5.8 Altezza di un BtreeConsiderando un albero minimo, ad eccezione della radice, ogni nodo in un BTree ha al più t-1 discendenti diretti, mentre la radice ne ha almeno 2. Cosicché il numero di nodi è in relazione con l'altezza nel seguente modo:

Quindi il numero totale di chiavi è:

n=1∑i=1

h

2 ti−1t−1

n12

≥t h

h≤logt n1

2

Da ciò possiamo dedurre che in un BTree con grado minimo t=50 e circa 1.000.000 di record, una chiave può essere cercata con al più 4 accessi al di-

26

sco!

5.9 Operazioni BaseLe operazioni effettuate in un BTree rispecchiano quelle di un qualunque al-bero binario con, in aggiunta, la gestione dei nodi magri e pieni. Si possono schematizzare nel seguente modo:

1. Creazione di un BTree2. Inserimento di una chiave

• Gestione dei nodi pieni (operazione di SplitChild)3. Eliminazione di una chiave

• Gestione dei nodi magri (operazione di Merge)4. Ricerca di una chiave 5. Visita del BTree

5.9.1 Divisione di un nodo Procedura SplitChildLa procedura divide un nodo y pieno, all'altezza della mediana, in due nodi magri. La chiave mediana viene spostata nel padre x del nodo y, che natural-mente non deve essere pieno, in modo tale si possa identificare il punto di di-visione dei due nuovi sotto-alberi. Se il nodo y è la radice, allora l'albero au-menta di una unità in altezza.N.B. L'operazione di Split è un'operazione di crescita degli alberi.

5.9.2 Inserimento Quando si vuole inserire una chiave in un BTree il concetto è semplice. Se durante lo scorrimento dell'albero per trovare il nodo interessato, viene incon-trato un nodo pieno avviene uno split (divisione). Algoritmo in linugaggio naturale:

1. Scorrere l'albero a partire dalla radice2. se “la radice” è piena allora avviene uno split con un nuovo

nodo (vuoto) e viene chiamata ricorsivamente la procedura di inserimento facendola partire dal sottoalbero dove dovrebbe essere inserita la chiave N.B. In questa fase viene incrementata l'altezza dell'albero.

3. Viene controllato se il nodo di partenza è foglia, se lo è viene inserita la chiave all'interno del nodo

4. Altrimenti, se il valore non è presente nel nodo e la radice del corrispondente sottoalbero è piena, viene eseguito lo Split della radice del sottoalbero

5. Viene chiamata ricorsivamente la funzione di inserimento facendola partire dal sottoalbero corrispondente

Al più la funzione di inserimento viene richiamata h volte.

27

5.9.3 Fusione dei nodi Procedura MergeLa fusione tra due nodi avviene quando i nodi interessati sono magri, così che il nodo ottenuto dalla fusione risulti pieno.

5.9.4 CancellazioneAnalogamente all'operazione di inserimento, quando viene incontrato un nodo magro si cerca di effettuare un merge con il fratello oppure una dona-zione dal fratello. Naturalmente la donazione tra fratelli nodi interni avviene coinvolgendo anche i sottoalberi interessati.

Proceura DeleteRecord

28

Casi:Nei casi 2a, 2b, 2c la chiave da cancellare è in un nodo interno magro.

• case_2a:Il nodo ha un fratello dx non magro. Avviene quindi uno scambio di chiavi che porta l'incremento aggiornamento della chiave nel padre e l'incremento del numero di chiavi nel nodo interessato.

• case_2b: Analogo al case_2a con la differenza che il nodo ha un fratello sx non magro.

• case_2c:Avviene quando entrambi i nodi sono magri (viene richiamato un merge) Nei casi 3a, 3b la chiave non è nel nodo preso in considerazione durante la cancellazione e la radice del sottoalbero interessato è magra.

• case_3aavviene una donazione da dx rendendo così� la radice del sottoalbero non ma-gra.

• case_3banalogo al case_3a considerando la radice del sottoalbero sx. Fasi:

1. Si controlla se il valore da cancellare è presente nel nodo preso in considera-zione (nel primo caso è la radice).

2. Se è presente avvengono ulteriori controlli per individuare la funzione da uti-

29

lizzare (case_2a, case_2b, case_2c) 1. Nel caso in cui è foglia, non magra e uguale alla radice si effettua una

cancellazione del valore in quel nodo. 2. Altrimenti se la foglia è magra ed il sottoalbero fratello dx non è magro

siamo nel case_2a. 3. Invece se il sottoalbero fratello sx non è magro siamo nel case_2b. 4. Altrimenti entriamo nel case_2c.

3. Se invece il valore non è presente nel nodo preso in considerazione:1. Se non siamo in foglia viene controllato il sottoalbero relativo e se non è

magro viene richiamata la funzione di cancellazione facendola partire dal quel sottoalbero.

2. Altrimenti se il sottoalbero corrispondente ha fratello dx o sx, viene chia-mato rispettivamente il case_3a o case_3b e poi la funzione di cancella-zione (ricorsivamente).

N.B. Se il sottoalbero ha solo il fratello sx siamo in case_3b altrimenti se ha solamente il fratello dx siamo in case_3a. [Per approfondimenti si veda 4]

5.10 Codice B-Tree

5.10.1 B-Tree-Search(x, k)i <- 1while i <= n[x] and k > keyi[x] do i <- i + 1if i <= n[x] and k = keyi[x] then return (x, i)if leaf[x] then return NIL else Disk-Read(ci[x]) return B-Tree-Search(ci[x], k)

5.10.2 B-Tree-Create(T)x <- Allocate-Node()

30

leaf[x] <- TRUEn[x] <- 0Disk-Write(x)root[T] <- x

5.10.3 B-Tree-Split-Child(x, i, y)z <- Allocate-Node()leaf[z] <- leaf[y]n[z] <- t - 1for j <- 1 to t - 1 do keyj[z] <- keyj+t[y]if not leaf[y] then for j <- 1 to t do cj[z] <- cj+t[y]n[y] <- t - 1for j <- n[x] + 1 downto i + 1 do cj+1[x] <- cj[x]ci+1 <- zfor j <- n[x] downto i do keyj+1[x] <- keyj[x]keyi[x] <- keyt[y]n[x] <- n[x] + 1Disk-Write(y)Disk-Write(z)Disk-Write(x)

5.10.4 B-Tree-Insert(T, k)r <- root[T]if n[r] = 2t - 1 then s <- Allocate-Node() root[T] <- s leaf[s] <- FALSE n[s] <- 0 c1 <- r B-Tree-Split-Child(s, 1, r) B-Tree-Insert-Nonfull(s, k) else B-Tree-Insert-Nonfull(r, k)

5.10.5 B-Tree-Insert-Nonfull(x, k)i <- n[x]if leaf[x] then while i >= 1 and k < keyi[x] do keyi+1[x] <- keyi[x] i <- i - 1 keyi+1[x] <- k n[x] <- n[x] + 1 Disk-Write(x) else while i >= and k < keyi[x] do i <- i - 1 i <- i + 1 Disk-Read(ci[x]) if n[ci[x]] = 2t - 1 then B-Tree-Split-Child(x, i, ci[x])

31

if k > keyi[x] then i <- i + 1 B-Tree-Insert-Nonfull(ci[x], k)

32

Indice analiticoAagglomerazione, problema nella tecnica hashing..................................21Algoritmi di randomizzazione.............14Algoritmo di Hash........................13algoritmo di Horner, vedi algoritmo di hashing..................................18archivio indice...........................9archivio primari..........................9aree di overflow, vedi inserimento archivi sequenziali ordinati.....................11Bblocco....................................4blocco, lettura di un.....................4buffer di I/O.............................4Ccategorie di funzione hash ..............19chiave primaria...........................3Chiave Secondaria.........................3chiave selettiva..........................3collisioni di indirizzamento, vedi hashing.........................................16Collisioni, chaining in area separata....20Collisioni, chaining tramite liste confluenti...............................20Collisioni, chaining tramite liste separate.........................................20collisioni, gestione chaining, gestione open addressing..........................19Collisoni, open addresing hashing doppio.20Collisoni, open addresing scansione lineare.........................................20Collisoni, open addresing scansione quadratica...............................20concentrate, vedi aree di overflow.......11DD. E. Knuth, esempio di hashing..........14distribuite, vedi aree di overflow.......11dizionario, vedi archivio indice..........9Ffattore di blocco.........................4fattore di carico, vedi hashing..........16funzione di hash modulare (per chiavi lunghe)..................................18Ggerarchia di indici, vedi livelli indice..9HHash, indirizzo di ......................13hashing, categoria a divisione...........19

hashing, categoria a moltiplicazione.....19hashing, funzione di scansione pseudocasuale............................20hashing, metodo della funzione universale19IISAM, file con indici multipli...........12Llivelli di indice.........................9MMD5, algoritmo di cifratura..............16metodo polinomiale 128, vedi algoritmo di hashing..................................18Oorganizzazione fisica.....................5organizzazione logica.....................5organizzazione, implementazione di un archivio..................................5overflow, aree concentrate o aree distribuite..............................11Ppagine di un archivio primario...........10PGP, algoritmo di crittografia...........16Philip Zimmermann, vedi PGP..............16proprietà aritmetiche delle operazioni modulari, vedi hashing modulare..........18Qqualità, bonta di una funz di hash.......17Rrecord bloccato...........................5record fisico.............................4record logico.............................4record multibolocco.......................5record sbloccato..........................5Sselettiva, chiave selettiva...............3sinonimi, chiavi sinomini, vedi collisionioni hash.......................18Sistema Informatico.......................1Sistema Informativo.......................1sottoarchivi, vedi pagine di un archivio primario.................................10sottoindici, vedi indici multipli o file ISAM.....................................12Ttabella hash.............................13Tabelle hash.............................13tempo di accesso costant.................16tracciato record..........................3