ORGANIZZAZIONE NON SEQUENZIALE

Organizzazione non sequenziale = è una tecnica di organizzazione che consente di accedere a un record senza dover attraversare tutti quelli che lo precedono.

Infatti si deduce che:

L'organizzazione non sequenziale non ha bisogno che i record siano memorizzati in maniera contigua.

E' necessario che un campo del record abbia un ruolo di chiave primaria, in modo che sia possibile individuare univocamente il record al quale accedere.

Su archivi non sequenziali sono consentite le operazioni di: lettura, scrittura, riscrittura, cancellazione e posizionamento.

I passi da seguire per accedere ad un record nell'organizzazione non sequenziale sono:

organizzazione relative;

organizzazione hash;

organizzazione B-alberi.

Organizzazione relative = è quando la chiave primaria di un record identifica univocamente sia il record stesso sia l'indirizzo logico in cui il record e registrato.

I vantaggi dell'organizzazione relative, sono:

a ogni record corrisponde una chiave numerica che corrisponde alla posizione occupata dal record all'interno dell'archivio.

l'organizzazione relative può essere usata solo su supporti ausiliari ad accesso diretto.

in tale tipo di organizzazione è consentito l'accesso diretto che quello sequenziale, quindi può essere gestita indifferentemente come archivio sequenziale o come archivio non sequenziale.

inoltre risulta molto vantaggiosa per le per le operazioni interattive.

utilizzando puntatori in questo tipo di organizzazione, è possibile ottenere un ordine logico diverso da quello fisico.

infine l'organizzazione relative consente la possibilità di accedere ai record con una chiave alfanumerica.

I svantaggi dell'organizzazione relative, ricordiamo che, spesso è difficile riuscire a impostare una relazione univoca tra la chiave primaria e la posizione nella quale memorizzare il record. Questo inconveniente obbliga il programmatore a utilizzare chiavi legate strettamente alla posizione relativa del singolo record all'interno dell'archivio, oppure a utilizzare particolari metodi di randomizzazione.

Organizzazione Hash = è una tecnica che si basa sull'utilizzo di funzioni che, partendo dalla chiave primaria di ciascun record, trasformano quest'ultima in un numero intero, che rappresenta l'indirizzo logico, detto indirizzo Hash.

La funzione Hash

Scegliere una funzione ottimale Hash significa scegliere una funzione che:

Sia facilmente calcolabile, cioè compostala calcoli che siano i più semplici possibili;

Produca sempre lo stesso indirizzo a partire dalla stessa chiave;

Generi indirizzi uniformemente distribuiti nell'ambito dell'archivio;

Generi indirizzi casualmente distribuiti nell'ambito dell'archivio;

Cerchi di coprire l'intero intervallo degli indirizzi evitando , che ci siano indirizzi che non vengono mai generati;

Generi indirizzi diversi se le chiavi sono diverse.

Trasformazione perfetta = accade quando la funzione ideale è quella che ad ogni valore della chiave primaria fa corrispondere sempre un indirizzo diverso, di modo che ogni record possa essere raggiunto tramite un solo accesso.

Collisione = quando due o più chiavi in fase di trasformazione, possono generare lo stesso indirizzo,  per risolvere questo problema occorre disporre di particolari procedure che collochino le registrazioni in conflitto, dette sinonimi.

Metodo di troncamento = questo metodo viene utilizzato quando la chiave numerica è composta da un elevato numero di cifre e il numero di record che possono essere memorizzati e abbastanza limitato.

E' un metodo molto efficace nel caso in cui le chiavi numeriche siano consecutive e con poche interruzioni. Gli svantaggi risiedono nel fatto che produce sinonimi ogni volta che si incontrano chiavi aventi le ultime tre cifre uguali e che l'indirizzo che calcola è sempre dato da una potenza di 10.

Metodo Folding = questo metodo consiste nel dividere la chiave numerica in due o più parti. Successivamente, tali parti vengono sommate tra loro e il numero ottenuto viene utilizzato come indirizzo. Il nome Folding ("piegare") si spiega se si immagina di piegare la chiave se si immagina di piegare la chiave congiungendo le sue estremità.

Metodo della divisione modulo N = con questo metodo l'indirizzo del record si ottiene dal resto della divisione della chiave numerica per il numero massimo di record memorizzabili nell'archivio.

Anche questo metodo genera dei sinonimi, il vantaggio è quello di poter essere applicato anche in presenza di un numero massimo di record che non è multiplo di 10.

Gestione delle collisioni = le tecniche di gestione delle collisioni sono metodi che consentono di individuare un indirizzo libero per la chiave k nel caso in cui la funzione hash H(k) restituisca un valore già ottenuto per un'altra chiave.

La gestione corretta di questa tecnica riveste importanza sia in fase di inserimento dei record sia in quella di ricerca di una chiave.

Nel caso di inserimento, si applicherà ad ogni chiave da inserire nell'archivio uno dei metodi prima descritti.

Nel caso della ricerca il discorso è analogo: si applicherà la funzione alla chiave da ricercare accedendo al record indicato dal valore restituito dalla funzione. Se la chiave da esso contenuta coincide con quella cercata, il problema è risolto, altrimenti si scandirà l'archivio andando su altre posizioni.

Scansioni lineare o indirizzamento aperto = questa tecnica consiste nello scandire l'archivio in modo da ricercare il primo posto libero in cui sistemare la chiave che ha generato la collisione.

Passo di scansione = numero di posizioni per ricercare il posto libero in cui sistemare la chiave che collide.

L'indirizzo di rehash = può essere calcolato con una qualsiasi funzione che generi numeri pseudocasuali e che, definisca un incremento differente per l'indirizzo.

Organizzazione a B-alberi =

Un B-albero di ordine M può essere:

un B-albero vuoto oppure una ina.

Una ina è:

un B-albero al cui interno sono presenti ine caratterizzate da voci tutte minori di quelle presenti nella ine;

una sequenza di N voci.

Una voce è:

una chiave;

un riferimento a una struttura di dati;

un puntatore a B-albero.

Le qualità specifiche dei B-alberi possono:

offrire ottime per quanto riguarda per quanto riguarda sia le operazioni di ricerca che quelle di aggiornamento;

su di essi è anche possibile effettuare elaborazioni di tipo sequenziali dell'archivio primario.

A ogni B-albero è attribuito un preciso ordine M che rappresenta il massimo numero di li di ciascun nodo. I nodi (ine) possono ospitare fino a 2M record (voci) dell'archivio.

Proprietà:

è perfettamente bilanciato in altezza, cioè ha tutte le foglie allo stesso livello;

ogni nodo, esclusa la radice, deve contenere almeno M chiavi;

ogni nodo, inclusa la radice, deve contenere al massimo 2M chiavi;

la radice può essere una foglia, oppure deve avere almeno due li;

un nodo può essere una foglia, ossia una ina terminale;

tra le chiavi più grandi di una chiave presente in una ina non foglia;

tra le chiavi più piccole di una chiave presente in una ina non foglia.

Ricerca nel B-albero = la ricerca di una chiave all'interno di un B-albero avviene secondo le regole previste per gli alberi binari, cioè si parte dalla radice e si attraversano i nodi dei sottoalberi, fino a quando non si trova la chiave desiderata.

L'inserimento nel B-albero = l'operazione di inserimento, ma anche quella di cancellazione, rappresentano le operazioni più complesse e delicate, poiché devono avvenire nel rispetto del bilanciamento, ossia devono garantire che la struttura rimanga sempre bilanciata. Nel caso in cui si vada a inserire una chiave all'interno di una ina satura occorrerà allocarne una nuova.