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

modifica

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

modifica
 
Esempio di 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

modifica
K1 P1 K2 P2 ... KM PM

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

ISAM: Organizzazione fisica

modifica

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

modifica

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

modifica

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

modifica

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
3 226 227 230 236 unused
...
9 213 Overflow area

Index Area

modifica

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

  • Track index
  • Cylinder index
  • Master index (Opzionale)

Track Index

modifica

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

modifica

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

modifica

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.

Bibliografia

modifica
  • Paolo Ciaccia, Dario Mario, Lezioni di basi di dati, 2013, Editrice Esculapio, ISBN 978-8874887187

Voci correlate

modifica

Altri progetti

modifica