Appunti: Indici B tree e hash

Cos'è un B tree?

È una struttura dati auto-bilanciata che mantiene i dati ordinati e consente ricerche, inserimenti e cancellazioni efficienti.

Caratteristica principale dei B tree

I B tree sono progettati per minimizzare il numero di accessi al disco grazie alla loro altezza ridotta.

Vero o falso: i B tree possono avere più di due figli per nodo.

Vero, i B tree possono avere un numero variabile di figli per nodo, aumentando l'efficienza.

Qual è l'ordine di un B tree?

L'ordine di un B tree è il numero massimo di figli che un nodo può avere. Un B tree di ordine m può avere al massimo m-1 chiavi.

Cosa significa che un B tree è bilanciato?

Significa che tutti i fogli si trovano alla stessa profondità, garantendo tempi di accesso uniformi.

Vantaggi dei B tree

- Accesso rapido ai dati - Efficienza nelle operazioni di ricerca - Crescita dinamica senza ridimensionamento

Inserimento in un B tree

Quando un nodo supera il numero massimo di chiavi, si divide in due, e la chiave centrale viene promossa.

Qual è la formula per calcolare la profondità di un B tree?

La profondità massima è $\displaystyle d = \frac{ ext{numero totale di nodi}}{m}$, dove m è l'ordine del B tree.

Differenza tra B tree e B+ tree

In un B+ tree, solo i fogli contengono i dati, mentre i nodi interni servono solo per la navigazione.

Cosa succede durante la cancellazione in un B tree?

Se un nodo scende sotto il numero minimo di chiavi, può fondersi con un nodo vicino o prendere in prestito una chiave.

B tree e accesso sequenziale

I B tree supportano l'accesso sequenziale ai dati grazie alla struttura dei nodi foglia collegate tra loro.

Vero o falso: i B tree sono sempre più lenti dei B+ tree.

Falso, i B tree possono essere più lenti in alcune operazioni, ma la differenza dipende dall'uso specifico.

Cos'è un nodo interno in un B tree?

Un nodo interno è un nodo che non è un foglio e contiene punteggiature per dirigere la ricerca.

Cosa sono le chiavi in un B tree?

Le chiavi sono gli elementi utilizzati per ordinare i dati all'interno dei nodi del B tree.

Efficienza del B tree

La complessità temporale per ricerca, inserimento e cancellazione è $\displaystyle ext{O}( ext{log}_m n)$.

Qual è la struttura di un nodo in un B tree?

Un nodo in un B tree contiene: - Un certo numero di chiavi - Puntatori ai nodi figli - Una chiave rappresentativa che permette di mantenere l'ordinamento delle chiavi nel nodo.

Inserimento in un B tree

L'inserimento comporta trovare la posizione corretta per un nuovo nodo e, se necessario, splittare i nodi per mantenere l'equilibrio.

Cosa accade durante la cancellazione?

La cancellazione potrebbe richiedere il merging di nodi per mantenere le proprietà del B tree.

Cosa è un nodo foglia?

Un nodo foglia è un nodo che non ha figli. Contiene valori e serve per il recupero dei dati.

Ricerca in un B tree

La ricerca è effettuata seguendo i puntatori dai nodi fino a trovare il valore cercato.

Vero o falso: I B tree sono sempre bilanciati.

Vero. I B tree mantengono una struttura bilanciata per garantire una complessità di ricerca logaritmica.

Qual è la complessità dell'inserimento?

La complessità dell'inserimento in un B tree è $\displaystyle O( ext{log}_b(n))$, dove $\displaystyle b$ è il numero massimo di figli.

Cosa è un nodo interno?

Un nodo interno è un nodo che ha almeno un figlio. Contiene puntatori e chiavi per la navigazione.

Esempio di splittaggio

Se un nodo ha 4 chiavi e deve inserire una quinta, si splitta e si promuove la chiave centrale.

Quali operazioni possono causare il rifacimento del B tree?

L'inserimento e la cancellazione possono causare operazioni di rifacimento per mantenere la struttura bilanciata.

Cancellazione di una chiave

La chiave viene rimossa, e se necessario, i nodi vengono fusi o redistribuiti.

Cosa succede se un nodo ha pochi figli?

Se un nodo ha meno del numero minimo di figli, può essere unito con un nodo vicino.

Qual è il massimo numero di chiavi in un nodo?

Il massimo numero di chiavi è definito dall'ordine del B tree, che è un parametro della struttura.

Tipi di operazioni sui nodi

- Inserimento - Cancellazione - Ricerca - Splittaggio

Cosa determina l'ordine di un B tree?

L'ordine determina il numero massimo di figli che un nodo può avere, influenzando direttamente le prestazioni.

Ricerca di una chiave: Procedure

1. Inizia dal nodo radice. 2. Confronta le chiavi. 3. Scendi nel nodo figlio appropriato.

Qual è il vantaggio principale dei B tree?

I B tree riducono il numero di accessi al disco, migliorando così le prestazioni nella gestione dei dati.

Cos'è una struttura hash?

È una struttura dati che mappa chiavi a valori, consentendo accessi rapidi.

Vantaggi delle strutture hash?

- Accesso veloce ai dati - Efficienza nella ricerca - Riduzione delle collisioni

Qual è la funzione hash?

Una funzione che trasforma una chiave in un indirizzo di memoria, permettendo l'accesso ai valori.

Cosa sono le collisioni?

Si verificano quando due chiavi diverse generano lo stesso indirizzo tramite la funzione hash.

Come si risolvono le collisioni?

- Chaining: liste collegate - Open addressing: ricerca di spazi liberi

Qual è la complessità di ricerca?

In generale è $\displaystyle O(1)$ in media, ma può diventare $\displaystyle O(n)$ in caso di molte collisioni.

Vero o falso: Le strutture hash sono ordinate.

Falso. Le strutture hash non mantengono un ordine tra gli elementi.

Cosa migliora la funzione hash?

Una buona funzione hash riduce le collisioni e distribuisce uniformemente le chiavi.

Esempio di funzione hash semplice:

h(k) = k \bmod n, dove k è la chiave e n è la dimensione dell'array.

Qual è l'overhead di memoria?

Le strutture hash possono richiedere spazio extra per gestire le collisioni e l'allocazione.

Cosa si intende per carico?

Il rapporto tra il numero di elementi e la dimensione dell'array, importante per la performance.

Confronta hashing e ricerca binaria.

Hashing: accesso $\displaystyle O(1)$ Ricerca binaria: accesso $\displaystyle O( ext{log } n)$ ma richiede dati ordinati.

B tree

Struttura dati bilanciata che mantiene ordinati gli elementi. Permette ricerche, inserimenti e cancellazioni efficienti.

Hashing

Tecnica per mappare dati in una tabella. Utilizza una funzione hash per l'accesso diretto ai dati.

Vantaggi B tree

- Buona gestione dello spazio - Ottimizzato per accesso su disco - Bilanciato in modo dinamico

Vantaggi Hash

- Accesso molto rapido - Semplice implementazione - Buona gestione delle collisioni

Accesso B tree vs Hash

B tree: O(log n) Hash: O(1) nel caso migliore

Quando usare B tree?

Quando sono richiesti accessi ordinati e intervalli di ricerca, come in database con query complesse.

Quando usare Hash?

Quando è necessario un accesso rapido ai dati basato su chiavi uniche, come nelle tabelle di ricerca.

B tree è più lento di Hash?

Vero. B tree ha tempi di accesso più lunghi rispetto a una tabella hash in media.

Hash collision

Si verifica quando due chiavi diverse producono lo stesso indice. Richiede strategie di risoluzione.

B tree e memoria

B tree è più efficiente in termini di uso della memoria rispetto a hash in scenari di grandi dataset.

Cosa succede se B tree è sbilanciato?

La sua efficienza di accesso diminuisce, rendendo le operazioni più lente, vicino a O(n).

B tree supporta quali tipi di operazioni?

Supporta inserimenti, cancellazioni, ricerche e scansioni di intervallo, mantenendo l'ordine degli elementi.