B-Albero

Da Wikipedia, l'enciclopedia libera.

I B-Alberi (o B-Tree) sono strutture dati ad albero, vengono comunemente utilizzati nell'ambito di database e filesystem. Essi derivano dagli alberi di ricerca, in quanto ogni chiave appartenente al sottoalbero sinistro di un nodo è di valore inferiore rispetto a ogni chiave appartenente ai sottoalberi alla sua destra; derivano anche dagli alberi bilanciati perché tutte le foglie si trovano alla stessa distanza rispetto alla radice. Il vantaggio principale dei B-Tree è che essi mantengono automaticamente i nodi bilanciati permettendo operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente.

Struttura del B-tree

Indice

1 Caratteristiche principali
2 Vantaggi dei B-Tree
3 Struttura del nodo: implementazione in C++
4 Tecniche principali
5 Varianti del B-tree
6 Collegamenti esterni
7 Bibliografia

[modifica] Caratteristiche principali

Assegnare ad un B-tree un ordine n significa dire che i nodi interni (esclusa la radice) conterranno da n/2 (approssimato per difetto) a n-1 chiavi [dif(n/2), n-1].
Una corrispondente lista di puntatori è situata tra le chiavi per indicare dove cercare una chiave se non è nel nodo corrente. Un nodo contenente k chiavi contiene sempre k+1 puntatori. Il numero di puntatori è detto fattore di ramificazione.
La radice contiene almeno una chiave
In un nodo le chiavi sono ordinate secondo ordine crescente.
Ad ogni chiave è associato un puntatore ad una informazione.

[modifica] Vantaggi dei B-Tree

I B-Tree portano forti vantaggi in termini di velocità ed efficienza rispetto ad implementazioni alternative quando la maggior parte dei nodi si trova in una memoria secondaria, ad esempio in un disco fisso. Massimizzando il numero di nodi figli per ogni nodo, l'altezza dell'albero si riduce, l'operazione di bilanciamento è necessaria meno spesso e quindi l'efficienza aumenta. Generalmente questo numero è impostato in modo tale che ogni nodo occupi per intero un gruppo di settori: così, dato che le operazioni di basso livello accedono al disco per cluster, si minimizza il numero di accessi ad esso.

[modifica] Struttura del nodo: implementazione in C++

Si ricorda che R è l'ordine dell'albero. È qui esposta una semplificazione della struttura nodo per un albero B-Tree.

struct bNode
{
  int nChiavi;    //livello di riempimento del nodo
 
  long RifPagina [2*R+1];  //vettore di puntatori ai nodi figli
 
  tipoChiave K [2*R];   //vettore ordinato di 2*R chiavi;
 
  long RifInfo [2*R];    //vettore di puntatori a informazioni su archivio
 
};

[modifica] Tecniche principali

Sono qui di seguito trattate tre tecniche fondamentali per l'utilizzo e la comprensione del funzionamento del B-Tree:

Ricerca di una chiave
Inserimento di una chiave - splitting
Cancellazione - merging

[modifica] Ricerca

La ricerca di un record di chiave k è svolta in modo analogo all'albero binario:

Ricerca di una chiave

Trasferimento in memoria della radice
Ricerca di K nella pagina trasferita: se è presente, la ricerca è terminata.
Altrimenti, se K è minore della chiave più a sinistra del nodo, allora trasferimento della pagina puntata dal puntatore di sinistra (se non è nullo); se K è maggiore della chiave più a destra allora trasferimento della pagina puntata dal puntatore più a destra (se non è nullo); se è compreso tra due chiavi del nodo allora trasferimento della pagina puntata dal puntatore compreso tra le due chiavi (se non è nullo). Ritorno al punto 2.
Se il puntatore in questione è nullo, la chiave non è presente.

In questo modo, il numero massimo di pagine da leggere per la ricerca coincide con l'altezza dell'albero. Poiché è possibile dimostrare che l'altezza dell'albero dipende dal logaritmo del numero di record del file, la lunghezza (o costo) della ricerca è una funzione logaritmica del numero di record del file. Il B-tree è inoltre tanto più conveniente quanto più il file è grande e la ricerca è più veloce tanto più sono piene le singole pagine.

$l\leq \log R\left[\frac{N+1}{2}\right]$

NB: R è l'ordine dell'albero ed N il numero di record presenti nell'archivio.

[modifica] Inserimento

L'inserimento di una nuova chiave all'interno di un B-Tree può presentare più difficoltà rispetto a come visto per il Binary Tree, in quanto è fondamentale mantenere il in due nodi.

[modifica] Cancellazione (merging)

Il procedimento relativo alla cancellazione di una chiave è inverso rispetto a quello per l'inserimento. Se la cancellazione va eseguita per una chiave di una foglia, essa viene eliminata e si compatta il vettore di chiavi. Se la chiave non si trova su una foglia, essa deve essere sostituita da una delle due chiavi adiacenti che si trovano in una foglia (generalmente si tratta della chiave successiva nell'ordinamento). Se nel rimuovere una chiave si hanno meno di R chiavi all'interno del nodo, le chiavi vengono distribuite presso nodi vicini, ma se questa operazione di ribilanciamento non fosse ancora sufficiente a mantenere R chiavi in una pagina, si procede alla tecnica del merging, ovvero alla fusione di due pagine. Se la somma del numero delle chiavi delle due pagine è minore di 2R, il merging fa sì che gli elementi delle due pagine ed il loro separatore confluiscano in un'unica pagina.

Se il merging si propaga fino al nodo radice, l'altezza dell'albero diminuisce di 1.

[modifica] Varianti del B-tree

Esistono diverse varianti al B-Tree che abbiamo appena preso in considerazione, le tre più diffuse sono:

Il B+Tree
Il B-*Tree
Il prefix B-Tree

[modifica] B+Tree

A differenza del B-Tree, nel B+Tree tutti i dati sono salvati nelle foglie. I nodi interni contengono solamente chiavi e puntatori. Tutte le foglie sono allo stesso livello. I nodi foglia sono inoltre collegati assieme come una lista per rendere il recupero di informazioni più semplici. Il numero massimo di chiavi in un record è detto ordine R del B+Tree. Il numero minimo di chiavi per record è R/2. Il numero di chiavi che può essere indicizzato utilizzando un B+Tree è in funzione di R e dell'altezza dell'albero. Per un B+Tree di ordine n-esimo e di altezza h:

Il massimo numero di chiavi è: $n h$
Il minimo numero di chiavi è: $2(n / 2) h - 1$

Di tutte le varianti del B-Tree, questa è la più usata, perché tutti i primi nodi interni che la memoria centrale può contenere vengono mantenuti su di essa mentre il resto dei nodi e le foglie vengono lasciate su memoria di massa. Ciò permette una maggior velocità di ricerca.

[modifica] B*Tree

Un B*Tree è una struttura dati sviluppata per la gestione di grandi quantità di informazioni, è composta da 2 parti: il direttorio e l'archivio.

L'archivio è costituito di record, ognuno dei quali può essere visto come una coppia chiave-informazione.
Il direttorio è organizzato ad albero: le foglie contengono gli indici, cioè le coppie chiave-puntatore che consentono di individuare i record nell'archivio, mentre la parte superiore dell'albero ha il solo compito di condurre alla rapida individuazione dell'indice contenente la chiave cercata.

La variante principale sta però nelle foglie dell'albero, le quali sono collegate tra loro tramite una catena di puntatori, in modo da consentire una scansione sequenziale dell'archivio.

Questo tipo di struttura trova applicazione nei file system Reiser4, HFS e HFS Plus.

[modifica] Prefix B-Tree

Il prefix B-Tree è un'evoluzione del B*Tree. Nei prefix B-Tree i nodi del direttorio non contengono necessariamente chiavi intere, ma generici separatori, cioè chiavi che possono essere state private della loro parte iniziale (il prefisso); l'intera chiave può essere ricostruita a partire dal separatore corrispondente, conoscendo la posizione nell'albero del nodo in cui esso è contenuto. Le foglie dell'albero contengono invece chiavi intere, al fine di rendere più efficace la ricerca sequenziale.

[modifica] Collegamenti esterni

[modifica] Bibliografia

Renato Conte; Il Mondo Degli Oggetti Vol.2

Categoria: Strutture dati

See also ebooksgratis.com: no banners, no cookies, totally FREE.