Indici

Scritto il 28 maggio 2012 da Marco

Gli indici sono strutture di accesso alternative utilizzate per migliorare l’efficienza del recupero di registri sulla base di particolari condizioni di ricerca.

Concettualmente, una struttura di accesso secondaria è simile all’indice di un libro: tutti i termini principali sono listati in ordine alfabetico, e cercando un termine nell’indice otteniamo una lista di indirizzi (pagine), che ci permettono di localizzare velocemente il testo richiesto.

  • Indici di singolo livello

    1. Indice primario (es:l’indice di un libro)

      Un primary index è un file ordinato di record a Iunghezza fissa con due campi.

      Ogni record, detto index entry, ha due campi strutturati così:

      • il 1° campo contiene il valore della chiave primaria;
      • il 2° campo contiene il puntatore al record del file.

       
      I valori dei due campi si indicano con < K ( i ) , P ( i ) > .

      Ovviamente ne segue che il numero di index entry è uguale al numero di blocchi del file.

      Ricerca: ricerca binaria.
      Inserimento e Cancellazione: costosi.

    2. Indice di clustering (di raggruppamento)

      Gli indici di clustering si costruiscono su un campo d’ordinamento che può ammettere valori ripetuti (non chiave).

    3. Indice secondario

  • Indici multilivello

    1. Statici

    2. Dinamici (B-tree, B+-Tree)

  • Indici basati su hash


  •  
     
     
     
     
     

Categoria: Appunti università | Ultimo aggiornamento: 1 giugno 2012


Back to top
Copyright © Salatin Marco 2009-2013