Cap.5 Struttura di indici per i file Flashcards
Campo chiave e campo di ordinamento:
Il campo chiave è un attributo o una combinazione di attributi che identifica univocamente ogni record o tupla all’interno di una struttura dati o di un database. Può essere considerato come un identificatore unico per ogni record. Il campo chiave può essere scelto in base alle caratteristiche dei dati stessi, ad esempio un codice univoco associato a ciascun record. Un campo chiave ben scelto dovrebbe avere proprietà come l’unicità, la stabilità (ovvero non cambiare frequentemente) e la facilità di ricerca.
Il campo di ordinamento, invece, è un attributo o una combinazione di attributi utilizzati per definire l’ordine dei record all’interno di una struttura dati o di un database. Esso determina come i record vengono organizzati e recuperati quando si effettuano operazioni di ricerca, ordinamento o interrogazione sui dati. Ad esempio, si può scegliere un campo di ordinamento che rappresenta una data di registrazione o un valore numerico, in modo da poter organizzare i record in ordine cronologico o in ordine crescente/decrescente.
Esistono molti tipi di indici ordinati, come l’indice primario che è specificato sul campo chiave di ordinamento di un file ordinato di record.
Il campo chiave di ordinamento è utilizzato per ordinare fisicamente i record dei file su disco e tutti i record hanno un valore univoco per quel campo.
Se il campo di ordinamento non è un campo chiave, cioè se molti record nel file possono avere lo stesso valore del campo di ordinamento, può essere
usato un altro tipo di indice, chiamato indice di cluster.
indice denso e indice sparso
Un indice denso contiene una voce per ogni valore della chiave di ricerca (e quindi ogni record) nel file di dati, mentre un indice sparso (o non denso)
contiene voci solo per alcuni valori di ricerca
Cosa e quali sono gli Indici + indici primari, cosa sono a cosa servono e come sono strutturati + Indice multilivello (perché indice primario su livelli
successivi?)
Gli indici sono strutture ausiliarie di accesso, essi velocizzano la ricerca dei record, fornendo percorsi di accesso secondari, e non influenzano la
posizione fisica dei record sul disco. Permettono un accesso efficace sulla base di campi d’indicizzazione che vengono utilizzati per costruire l’indice.
Esistono diversi indici:
▪ Indici ordinati, simile all’indice di un libro, definiti su un unico campo, chiamato campo di indicizzazione. L’indice memorizza ogni valore del campo
di indicizzazione corredandolo di un elenco di puntatori a tutti i blocchi del disco che contengono record con quel valore del campo.
▪ Indici primari, esiste una voce (o record dell’indice). Ogni voce è composta da due campi che contengono il valore del campo della chiave primaria
del primo record del blocco e un puntatore al corrispondente blocco su disco. Il numero complessivo di voci dell’indice è uguale al numero di
blocchi su disco nel file di dati ordinato. Il primo record in ciascun blocco del file di dati è chiamato record àncora del blocco. L’indice primario è un
indice non denso, poiché include una voce per ogni blocco del file di dati piuttosto che per ogni valore di ricerca o per ogni record.
▪ Indice di cluster, se i record di un file sono ordinati fisicamente rispetto a un campo che non è chiave, cioè che non ha un valore distinto per
ciascun record, quel campo è chiamato campo di raggruppamento. L’indice di cluster velocizza il recupero dei record che hanno lo stesso valore del
campo di raggruppamento. Questo indice differisce da un indice primario, che richiede che il campo di ordinamento del file di dati abbia un valore
distinto per ogni record. Anche l’indice di cluster è un file ordinato con due campi, il primo è dello stesso tipo del campo di raggruppamento del file
di dati, mentre il secondo è un puntatore a un blocco. Un indice di cluster è un altro esempio di indice non denso.
▪ Indice secondario, è un file ordinato con due campi, il primo è dello stesso tipo di dati di un campo del file di dati, che non viene utilizzato per
effettuare l’ordinamento del file di dati, chiamato campo di indicizzazione, il secondo campo è un puntatore a record. Vi possono essere più indici
secondari (e quindi campi di indicizzazione) per lo stesso file. Vi è una voce dell’indice per ciascun record del file di dati, la quale contiene il valore
della chiave secondaria del record e un puntatore al blocco in cui il record è memorizzato. Questo indice è denso.
▪Un indice multilivello è una struttura dati utilizzata nei database per migliorare le prestazioni delle operazioni di ricerca e recupero dei dati. Si tratta di un indice che organizza le informazioni in più livelli gerarchici, consentendo una navigazione efficiente all’interno dei dati.
Ecco come funziona tipicamente un indice multilivello:
Livello superiore: L'indice multilivello inizia con un livello superiore o radice. Questo livello contiene un elenco di voci o puntatori che puntano ad altri livelli inferiori dell'indice. Livelli intermedi: I livelli intermedi dell'indice suddividono i dati in sottogruppi più piccoli, creando una gerarchia di pagine o blocchi di dati. Ogni livello intermedio contiene puntatori o informazioni che consentono di individuare i dati corrispondenti in modo più specifico. Livello inferiore: L'ultimo livello dell'indice è costituito dalle pagine o dai blocchi di dati reali che contengono le informazioni dettagliate o i record. Questi blocchi di dati sono organizzati in base a un criterio specifico, come ad esempio un valore di chiave.
Durante la ricerca dei dati tramite un indice multilivello, si segue una procedura gerarchica per raggiungere i dati desiderati:
Ricerca nel livello superiore: La ricerca inizia dal livello superiore dell'indice. Qui viene individuata una voce o un puntatore che corrisponde all'intervallo o al valore di ricerca desiderato. Passaggio ai livelli intermedi: Utilizzando il puntatore o l'informazione ottenuta dal livello superiore, si passa ai livelli intermedi dell'indice. Questo processo viene ripetuto fino a raggiungere il livello inferiore appropriato. Ricerca nel livello inferiore: Nel livello inferiore, i dati sono organizzati in blocchi più piccoli o pagine. La ricerca viene effettuata in base al valore di chiave o al criterio di ordinamento specificato. Il risultato della ricerca restituisce il dato o i dati desiderati.
L’uso di un indice multilivello consente di ridurre il numero di accessi ai dati effettuati sul disco, migliorando così le prestazioni delle operazioni di ricerca e recupero dei dati.
Quali sono i problemi che si verificano con un indice primario?
Un problema che si verifica con l’indice primario è l’inserimento e l’eliminazione dei record.
Se si tenta di inserire un record nella sua posizione corretta nel file di dati, si devono non solo spostare gli altri record per creare spazio per quello nuovo, ma anche cambiare
alcune voci dell’indice, perché lo spostamento dei record modificherà i punti di aggancio di alcuni blocchi. Usando un file di overflow non ordinato si può limitare questo problema.
Un’altra possibilità è utilizzare una lista di record di overflow per ciascun blocco del file di dati, simile al metodo di gestione dei record di overflow. I record all’interno di ogni blocco e la corrispondente lista di overflow possono essere ordinati per migliorare il tempo di recupero. L’eliminazione dei record è gestita utilizzando degli indicatori di eliminazione
Cos’è un albero?
Un albero è formato da nodi, ognuno di essi ha un padre e zero o più nodi figlio, tranne un nodo chiamata radice che non ha il nodo padre e un nodo che non ha alcun nodo figlio chiamato foglia, mentre un nodo che non è foglia è un nodo interno.
Il livello di un nodo è sempre superiore di una unità rispetto al livello del suo nodo padre, mentre il livello del nodo radice è zero.
Un sottoalbero di un nodo è costituito da quel nodo e da tutti i suoi nodi discendenti. Una precisa definizione ricorsiva di un sottoalbero dice che un sottoalbero è costituito da un nodo n e dai sottoalberi di tutti i nodi figli n
Cos’è un albero di ricerca?
Un albero di ricerca è un tipo di albero speciale che viene usato per guidare la ricerca di un record, dato il valore di uno dei suoi campi
Ogni nodo dell’indice multi livello può avere fino a fo puntatori e fo valori chiave, dove fo è il fan-out dell’indice.
I valori dei campi dell’indice di ciascun nodo guidano l’utente al nodo successivo finché raggiunge il blocco del file di dati che contiene i record richiesti.
Seguendo un puntatore si limita a ogni passo la ricerca a un sottoalbero dell’albero di ricerca e si ignorano tutti i nodi che non sono di quel sottoalbero.
Un albero di ricerca di ordine p è un albero tale che ogni suo nodo contiene al massimo p-1 valori di
ricerca e i p puntatori sono nell’ordine <P1, K1, P2, K2, …, Pq-1, Kq-1, Pq >, in cui q ≤ p, ogni Pi è un puntatore a un nodo figlio (o puntatore vuoto) e ogni Ki è un valore di ricerca preso da un insieme ordinato di valori
Com’è definito un albero B di ordine P?
un albero B di ordine p, quando è usato come una struttura di accesso su un campo chiave per cercare i record in un file di dati, può essere definito nel seguente modo:
- Ogni nodo interno dell’albero B ha la forma: <P1, <K1, Pr1>, P2, <K2, Pr2>, …, Pq-i, <Kq-1, Prq-1>, Pq>, dove q ≤ p. Ogni Pi è un puntatore a un albero, cioè un puntatore a un altro nodo nell’albero B. Ogni Pri è un puntatore ai dati, cioè un puntatore al record il cui valore del campo chiave è uguale a Ki (o al blocco del file di dati che contiene quel record);
- All’interno di ogni nodo, K1 < K2 < … < Kq-1;
- Per tutti i valori X del campo chiave di ricerca nel sottoalbero a cui si è fatto riferimento da Pi, si ha: Ki-1<X<Ki per 1<i<q, X<Ki per i=1, Ki-1<X per i=q;
- Ogni nodo contiene al massimo p puntatori dell’albero;
- Ogni nodo, tranne i nodi radice e i nodi foglia, ha almeno [(p/2)] puntatori dell’albero, il nodo radice ha almeno due puntatori dell’albero a meno che sia l’unico nodo dell’albero;
- Un nodo con q puntatori dell’albero, dove q ≤ p, contiene q–1 valori del campo chiave di ricerca (e quindi ha q–1 puntatori ai dati);
- Tutti i nodi foglia sono allo stesso livello e hanno la medesima struttura dei nodi interni, a parte il fatto che tutti i loro puntatori a un albero Pi sono nulli
Cos’è un albero B+?
Gli alberi B+ sono una variante degli alberi B in cui i puntatori ai blocchi dei dati di un file sono memorizzati solo nei nodi foglia, questo può richiedere meno livelli e permette di ottenere indici di capacità più elevata
In un albero B+ i puntatori ai dati sono memorizzati solo nei nodi foglia dell’albero, quindi la struttura dei nodi foglia differisce dalla struttura dei nodi interni.
I nodi foglia contengono una voce per ogni valore del campo di ricerca, insieme a un puntatore al record dei dati (o al blocco che contiene il record) se il campo di ricerca è un campo chiave.
Per un campo di ricerca non chiave, il puntatore fa riferimento a un blocco che contiene i puntatori ai record del file di dati, creando un livello ulteriore di indici.
I nodi foglia dell’albero B+ di solito sono collegati tra loro per fornire un accesso ordinato al campo di ricerca e ai record. Questi nodi foglia sono simili al primo livello (base) di un indice.
I nodi interni dell’albero B+ corrispondono agli altri livelli di un indice multilivello. Alcuni valori del campo di ricerca dai nodi foglia sono ripetuti nei nodi interni dell’albero B+ per guidare la ricerca
Com’è la struttura di un nodo interno in un albero B+?
La struttura dei nodi interni di un albero B+ di ordine p è la seguente:
1. Ogni nodo interno ha la seguente forma: <P1, K1, P2, K2, …, Pq-1, Kq-1, Pq>, in cui q ≤ p e ogni Pi è un puntatore a un albero;
- All’interno di ogni nodo interno, K1 < K2 < …. < Kq-1;
- Per tutti i valori X del campo di ricerca nel sottoalbero a cui si fa riferimento da Pi, si ha Ki-1<X≤Ki per 1<i<q, X≤Ki per i=1, Ki-1<X per i=q;
- Ogni nodo interno ha al massimo p puntatori ad un albero;
- Ogni nodo interno, tranne la radice, ha almeno [ (p/2) ] puntatori dell’albero. Il nodo radice ha almeno due puntatori dell’albero se è un nodo interno;
- Un nodo interno con q puntatori, q ≤ p, ha q – 1 valori del campo di ricerca.
