FILE SEQUENZ. ORDINATO Per la ricerca non devo scorrere tutto, 636b18g basta il logaritmo di ricerca binaria log₂ n . Archivio ordinato in base alla chiave primaria (Non posso inserire nel mezzo)

ALGORITMO DI HASH

OPERAZIONI BASE

OPERAZIONI STRAORDINARIE

Creazione ho delle schede e le organizzo in un archivio

Riorganizzazione se l'organizzazione che ho non mi soddisfa la modifico in base a nuove esigenze

OPERAZIONI ORDINARIE

Consultazione reperire un informazione all'interno del file e si effettua in base alle chiavi

Inserimento necessità di inserire un nuovo record nell'archivio

Cancellazione di una registrazione in archivio LOGICA I dati non sono cancellati fisicamente ma segno il fatto che li ho cancellati ( agg. Al record un campo booleano che quando chiedo Cancellato? SI oppure do alla chiave primaria un valore che non potrebbe assumere es. **) FISICA cancello effettivamente i dati dal disco (dopo aver fatto + di 1 cancellazione logica, riorganizzo l'archivio cioè lo leggo e lo copio su un nuovo file, lo ricompatto e faccio Rewrite)

Aggiornamento/modifica voglio modificare 1 dato, (se un fornitore cambia indirizzo..)cambio 1 o + campi di una voce già presente

Visita Guardare l'archivio x recuperare un insieme di informazioni su + voci di esso es. statistiche..)

FUSIONE DI 2 FILE DI CUI UNO ORDINATO E L'ALTRO NO

Ordinre file inserimento m² /2 operaz.

"merge" (fusione) dei 2 file  2(n+m) operazioni

ALGORITMO DI HASH Tecnica che funziona attraverso una chiave primaria univoca.(kp>indirizzi) Organizzazione di archivi, data una chiave, associo un indirizzo.

H mi dice dove devo scrivere gli elementi ma poi li trova anche.

Ho un record di KP + INFO e lo devo inserire (voce x voce) in un file, in modo da trovarlo subito. (insieme delle possib. Kp)---H---(insieme dei possib. Indirizzi hash) .Tecnica che consente di gestire in modo efficiente gli archivi. CREAZIONE: 1)Conoscere il n° di record da gestire (700 studenti li sovrastimo 1000) 2)Inserire tutti i dati nel file Hash da 1000 posizioni 3) uso dell'archivio (consultaz, cancellaz,insrimento..)  4)Quando ha capienza max Eventuale riorganizzazione

CARATTERISTICHE

STIMA DEL NUMERO RECORD (sapere quanti record ci vanno dentro)

SPRECO LIMITATO DI SPAZI CONTRO L'EFFICIENZA (devo sovrastimare + spreco spazi + la tecnica funziona bene e meno collisioni)

OTTIMA EFFICIENZA (solo x operaz. Standard inserim,cancellaz,modifica,consultaz)

SUPPORTA MOLTO BENE ARCHIVI VOLATILI in cui il n° complessivo di elementi è circa costante altrimenti bisogna riorganizzare (archivio dove ho molte cancellaz, cambiamenti di dati)

ABBASTANZA COMPLESSA (funzione hash- gestione collisioni-riorganizzazione)

COLLISIONI K1, K2 / K1 K2 &  h(K1) = h(K2)

TECNICHE DI RISOLUZIONE

Sequenza di scansione lineare unitaria dopo aver ricevuto l'indirizzo, vado nella posizione indicata. Se questa è già piena andrò avanti (giù) fino a quando ne trovo una libera. (es i--i+1--i+2)ma quando utilizzerò la funzione hash mi indicherà ugalmente i.

Catene confluenti (tracciato record + grande di 1 campo: link    (K, INFO, LINK (seek(fl,4))) Collisione di k1 con k2. Collisione della posizione i. Cerco un posto libero (ovunque) per esempio w e creo un campo aggiuntivo LINK che mi indica , quando andrò alla posiz. I, dove è stato inserito k2. Collegamento che mi dice "se non è qui vai a W"

CATENA ciascuno dice dov'è il suo successivo

CONFLUENTI se la hash mi assegna un posto già occupato andrò a vedere il link dove mi manda e quando trovo l'ultimo elemento della catena cerco un nuovo posto libero

CATENE CONFLUENTI perché esistono più chiavi di indirizzi hash differenti che confluiscono fra loro

Catene distinte (rispettano sempre un indirizzo) Si utilizzano 2 file e nel 2° si effettuano le catene confluenti. La prima volta che c'è una collisione la inserisco in un nuovo file dedicato alle collisioni.

CANCELLAZIONE LOGICA ELEMENTI (CATENE CONFLUENTI) h(k1)=i h(k2)=i il posto per h(k2) lo trovo con la LISTA LIBERA (variabile che mi dice dove trovo posti vuoti) è una variabile globale "j" e quando vado ad inserire l'ultimo nella pos. Link ci andrà X che è uguale a x=-1 (x=nil) cioè la catena è ferma. Se cancello un elemento la catena però deve andare avanti allora si mette 0 nella chiave primaria ma lascio l'indirizzo che aveva per raggiungere le altre posizioni.