Indice
Gli indici sono strutture aggiuntive che migliorano l'efficienza delle operazioni di ricerca su un file, senza modificare l'organizzazione fisica dei dati
Analogia: simile all'indice di un libro, dove i termini sono ordinati e associati a numeri di pagina
Tipi di organizzazione:
- Primaria: heap file, file ordinati, hashing
- Secondaria: indici che forniscono percorsi di accesso alternativi
Tipi di indici
- Indice primario:
- Definito su un campo chiave di ordinamento (ordering key field) di un file ordinato
- Struttura:
- Entry:
<valore_chiave, puntatore_al_blocco>
- Sparso: una entry per blocco (basato sul primo record del blocco)
- Indice clustering:
- Definito su un campo non chiave di ordinamento (ordering non-key field)
- Sparso: una entry per ogni valore distinto del campo
- Utilizzo: blocchi separati per gruppi di record con lo stesso valore di clustering
- Indice secondario:
- Definito su un campo non di ordinamento (non-ordering field)
- Denso: una entry per ogni record nel file
- Tipi:
- Chiave secondaria: campo con valori univoci
- Non chiave: campo con valori duplicati, gestiti con liste di puntatori
Proprietà
| Tipo Indice |
Numero Entry |
Denso/Sparso |
Ancoraggio Blocchi |
| Primario |
Numero blocchi |
Sparso |
Sì |
| Clustering |
Valori distinti |
Sparso |
Sì/No |
| Secondario (chiave) |
Numero record |
Denso |
No |
| Secondario (non chiave) |
Valori distinti o record |
Denso/Sparso |
No |
Indici multilivello
- Obiettivo: ridurre la dimensione dell'indice per accelerare la ricerca binaria
- Struttura:
- Livello base: file indice ordinato
- Livelli superiori: indici primari sui livelli inferiori
- Fan-out (fo): numero di entry per blocco
- Accessi necessari: $log_{fo}(b_i)$, dove $b_i$ è il numero di blocchi del livello