ISAM
# ISAM

ISAM è l'acronimo di Indexed Sequential Access Method (metodo di accesso sequenziale indicizzato), ed è un modo per immagazzinare dati da estrarre rapidamente. Sviluppato originariamente da IBM, costituisce oggi la base per l'immagazzinamento dei dati in molti database, relazionali e non.

## Descrizione

In un sistema ISAM i dati sono suddivisi in record composti da campi a lunghezza fissa. I record sono immagazzinati in sequenza, come si faceva in origine per velocizzare l'accesso da una periferica a nastro. Vi è poi un set secondario di tabelle hash chiamate indici, che contengono puntatori ai record, in modo che un record possa essere estratto senza dover scorrere l'intero insieme di dati. Questa è una differenza rispetto ai database navigazionali, nei quali i puntatori ad altri dati si trovavano dentro i record stessi. Il miglioramento in ISAM è dovuto al fatto che gli indici sono di piccole dimensioni e consentono ricerche veloci, perché il database accede soltanto ai record di cui ha bisogno. Inoltre eventuali modifiche ai dati richiedono che si modifichino i record e gli indici in questione, ma non altri dati come i puntatori.

I database relazionali possono essere facilmente costruiti su un framework ISAM con l'aggiunta della logica per mantenere validi i collegamenti tra le tabelle. In genere il campo utilizzato come collegamento, detto chiave esterna, è indicizzato per permettere ricerche veloci. Questo metodo è più lento che immagazzinare il puntatore ai dati collegati dentro al record, però se si modifica la struttura fisica dei dati non vi è la necessità di aggiornare i puntatori, in quanto i collegamenti rimangono validi.

ISAM è molto semplice da comprendere e da implementare, perché consiste essenzialmente nell'accesso diretto e sequenziale a un file di database. È anche molto poco costoso in termini di prestazioni. Lo svantaggio è che ogni macchina client deve gestire una sua propria connessione per ogni file a cui accede. Ciò comporta la possibilità che distinte modifiche dei dati entrino in conflitto tra loro, creando così incoerenze. Questo problema viene generalmente risolto con l'implementazione di una piattaforma client-server che gestisce le richieste dei client mantenendo l'ordine. È questo il concetto base che sta dietro l'SQL, che si trova a un livello di astrazione superiore rispetto all'immagazzinamento dei dati.

ISAM è stato rimpiazzato all'IBM da un metodo chiamato VSAM (Virtual Sequential Access Method), utilizzato anche nel DB2, che ancor oggi è il suo DBMS primario.

L’organizzazione ISAM dei file assegna a ciascuna tupla una posizione in base al valore del campo chiave. Questa organizzazione è basata sull’idea di dare alle tuple un ordinamento fisico che rifletta l’ordinamento lessicografico dei valori presenti in un campo chiave. In realtà non è necessario che il campo scelto per definire l’ordinamento delle tuple sia un campo chiave. Per quanto riguarda i criteri di ordinamento, gli usuali domini di valori, come le stringhe di caratteri, gli interi o i reali, seguono un ordinamento convenzionale: per i numeri interi o reali si considera quello numerico, mentre per le stringhe di caratteri abbiamo l’ordine lessicografico. Per aumentare la velocità di accesso al file ordinato (che chiamiamo file principale), si definisce un secondo file (chiamato sparse index, indice rado), che consiste nelle coppie:

(<valore chiave>,<indirizzo del blocco>)

Per ogni blocco del file principale, nel file indice esiste un record (µ,b): µ è un valore non superiore a quello di tutte le chiavi contenute nel blocco b e maggiore (>) dei valori delle chiavi di ogni blocco che precede b. Il primo campo di (µ, b) è una chiave e il file indice è ordinato rispetto ad essa.

## ISAM: Organizzazione Logica

ISAM è una organizzazione statica, soggetta a costose riorganizzazioni periodiche. Essendo statica, occorre predisporre aree di overflow per l'aggiunta di elementi.

### Formato nodo interno

| $K_1$ | $P_1$ | $K_2$ | $P_2$ | ... | $K_M$ | $P_M$ |
| - | - | - | - | - | - | - |

Ogni coppia $(k_i$ ; $p_i)$ è tale per cui $k_i$ è il più alto valore di chiave nel sottoalbero puntato da $p_i.$

## ISAM: Organizzazione fisica

ISAM prevede uno specifico schema di allocazione dei dati e dell'indice sul dispositivo di memoria secondaria. In particolare, si distinguono tre aree:

* Primary area
* Overflow area
* Index area

### Primary Area

Questa è l'area predisposta ad ospitare i dati. Essa è costituita da una serie di cilindri contigui sui quali alcune tracce sono riservate per l'indice e altre per le aree di overflow.

Cylinder 0 :

* Index tracks
* 1 3 5 7
* 9 14 17 18
* Overflow tracks

Cylinder 1 :

* Index tracks
* 19 20 22 25
* 39 40 42 48
* Overflow tracks

Cylinder 2 :

* Independent
* overflow area

### Overflow Area

Quest'area è essenzialmente usata per memorizzare nuovi record, i quali altrimenti non potrebbero essere inseriti nell'area principale senza dover riscrivere la sequenza dei file. Esistono due tipi di overflow area:

* Cylinder overflow area: tracce riservate per gestire l'overflow dei dati di ogni cilindro. I record in overflow sono collegati in catena.
* Independent overflow area: si ricorre all'area comune sull'ultimo cilindro solo quando l'area particolare di overflow è satura.

**Esempio**

Prendiamo come esempio la seguente memorizzazione dei dati nel cilindro 5:

| Track | Data nel Cilindro 5 |
| - | - |
| 1 | 205 206 208 210 213 |
| 2 | 214 219 220 222 225 |
| 3 | 226 227 230 236 unused |

Se si aggiunge il record con chiave 209, esso provoca lo spostamento del record 213 dal track 1 dentro l'overflow area, muovendo il 210 al suo posto ed inserendo il 209 nel posto lasciato libero dal 210.

| Track | Data nel cilindro 5 | Commenti |
| - | - | - |
| 1 | 205 206 208 209 210 | Prime data area |
| 2 | 214 219 220 222 225 | Prime data area |
| 3 | 226 227 230 236 unused | Prime data area |
| ... | | Prime data area |
| 9 | 213 | Overflow area |

### Index Area

Per facilitare la localizzazione random dei record, ISAM mantiene tre livelli di indici sul disco:

* Track index
* Cylinder index
* Master index (Opzionale)

**Track Index**

Vi è un track index per ogni cilindro, che generalmente occupa il track 0 (la prima posizione). Ogni entrata corrisponde a una traccia sul cilindro e memorizza:

* il valore di chiave più alto in area primaria
* il valore di chiave più alto in area di overflow
* il puntatore al primo record nell'area locale di overflow

**Cylinder Index**

Esiste un solo cylinder index per file. Ogni entrata è relativa ad un cilindro e memorizza il valore più alto della chiave in esso contenuto. Per esempio, se il file memorizzato su 6 cilindri, il cylinder index contiene 6 voci.

**Master Index**

Questo indice viene usato solo se il cylinder index risulta troppo grande e non garantisce un'efficiente indicizzazione. Nel master index vi è un'entrata per ogni traccia del cylinder index, per memorizzare il valore più alto di chiave della traccia e l'indirizzo della traccia.

