11 : Archivi e file Vers . 2.0 – Dicembre 2020
A questo punto in base alla tecnica della scansione lineare con passo unitario dobbiamo spostarci sul record successivo per vedere se la posizione è libera : dobbiamo andare sulla posizione 10 . Ovviamente ciò non è possibile avendo supposto che l ’ archivio sia composta da 9 record . Occorre pertanto applicare il metodo della divisione modulo 9 anche per il risultato prodotto . k = 71 H ( k ) = ( 71 MOD 9 ) + 1 = 8 + 1 = 9 collisione con la chiave 35 . Si continua usando 9 ( 9 MOD 9 ) = 0 + 1 = 1 collisione con la chiave 9 . Si continua usando 1 ( 1 MOD 9 ) = 1 + 1 = 2 collisione con la chiave 28 . Si continua usando 2 ( 2 MOD 9 ) = 2 + 1 = 3 collisione con la chiave 29 . Si continua usando 3 ( 3 MOD 9 ) = 3 + 1 = 4 collisione con la chiave 48 . Si continua usando 4 ( 4 MOD 9 ) = 4 + 1 = 5 Non c ’ è più collisione . La chiave 35 viene memorizzata in posizione 5 . Ora analizziamo l ’ ultima chiave : k = 64 H ( k ) = ( 64 MOD 9 ) + 1 = 1 + 1 = 2 collisione con la chiave 28 . Si continua usando 2 ( 2 MOD 9 ) = 2 + 1 = 3 collisione con la chiave 29 . Si continua usando 3 ( 3 MOD 9 ) = 3 + 1 = 4 collisione con la chiave 48 . Si continua usando 4 ( 4 MOD 9 ) = 4 + 1 = 5 collisione con la chiave 71 . Si continua usando 5 ( 5 MOD 9 ) = 5 + 1 = 6 Non c ’ è più collisione . La chiave 64 viene memorizzata in posizione 6 . Come si può notare la chiace 64 ha dovuto attraversare una parte della catena precedente pur sapendo che i record individuati da questi indirizzi erano occupati .
b ) Scansione non lineare o pseudo-random Tale tecnica è una variante dell ’ indirizzamento aperto . Questo metodo ricorre ad una tecnica di memorizzazione che non prevede una scansione sequenziale dell ’ archivio poiché al posto di utilizzare il passo di scansione genera un numero casuale ( o meglio pseudo-casuale ) ogni qualvolta si verifica una collisione . Tale metodo si definisce scansione non lineare o pseudo-random .
In altri termini si calcola l ’ indirizzo per iniziare la scansione : se su tale indirizzo si verifica una collisione , non ci si sposta sulla posizione immediatamente successiva , bensì si ricalcala un nuovo indirizzo , detto indirizzo di rehash servendosi di una nuova funzione detta funzione di rehash . L ’ indirizzo di rehash può essere calcolato con una qualsiasi funzione che generi numeri pseudocasuali e che , per ogni passo , definisca un incremento differente per l ’ indirizzo .
N . B . Ribadiamo che l ’ indirizzo di rehash deve essere necessariamente pseudo-casuale in quanto in fase di ricerca di una chiave devono essere ricalcolati gli stessi indirizzi prodotti per la memorizzazione , ossia deve essere ripetuta la stessa sequenza di indirizzi .
C ) L ’ ORGANIZZAZIONE A B-ALBERI
Abbiamo visto in precedenza come l ’ utilizzo degli indici possa essere di valido aiuto per implementare archivi dinamici . La gestione di tali indici viene resa molto efficiente se si utilizzano gli alberi binari per le chiavi e può essere ancora ottimizzata se si mantiene l ’ albero bilanciato . ( N . B . L ’ operazione di ricerca diventa più rapida ).
I B-alberi ( in inglese Balanced trees ) sono strutture dati nate nei primi anni 70 proprio per venire incontro all ’ esigenza di creare modelli implementativi efficienti per la gestione dinamica ed ordinata di archivi di dati . Sono alberi binari ordinati secondo la chiave e perfettamente bilanciati in altezza ( ossia con tutte le foglie allo stesso livello ).
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 28