Movatterモバイル変換

Vai al contenuto

B-albero

Modifica collegamenti

Da Wikipedia, l'enciclopedia libera.

(Reindirizzamento daB-Albero)

Niente fonti!

Questa voce o sezione sull'argomento programmazionenon cita le fonti necessarie o quelle presenti sono insufficienti.

Puoimigliorare questa voce aggiungendo citazioni dafonti attendibili secondo lelinee guida sull'uso delle fonti.

Rappresentazione di un B-albero

UnB-albero (in ingleseB-tree) è unastruttura dati che permette la rapida localizzazione dei file (record o chiavi), specie nellebasi di dati, riducendo il numero di volte che un utente necessita per accedere alla memoria in cui il dato è salvato. Essi derivano daglialberi binari 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; inoltre, la loro struttura ne garantisce ilbilanciamento: per ogni nodo, le altezze dei sottoalberi destro e sinistro differiscono al più di una unità. Questo è il vantaggio principale del B-albero, e permette di compiere operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente.

Sono utilizzati spesso nell'ambito dellebasi di dati, in quanto permettono di accedere ai nodi in maniera efficiente sia nel caso essi siano disponibili in memoria centrale (tramite unacache), sia qualora essi siano presenti solo sulla memoria di massa.

Definizione

[modifica |modifica wikitesto]

Un B-Albero è unalbero radicato (la cui radice può essere indicata come $root[T]$ ) che soddisfa le seguenti proprietà:

Ogni nodo $x {\displaystyle x}$ ha i seguenti attributi:
- $n[x]$ , il numero di chiavi memorizzate in $x {\displaystyle x}$
- indicando con $key_{i}[x]$ l'i-esima chiave del nodo $x {\displaystyle x}$ si ha $key_{1}[x]\leq key_{2}[x]\leq ...\leq key_{n[x]}[x]$
- $leaf[x]$ è un valore booleano che può assumere valore ${\mbox{true}}$ se il nodo $x {\displaystyle x}$ è una foglia, ${\mbox{false}}$ altrimenti.
Ogni nodo interno ha $n[x]+1$ puntatori $c_{1}[x],c_{2}[x],...,c_{n[x]+1}[x]$ ai suoi figli.
Vale $c_{1}[x]\leq key_{1}[x]\leq c_{2}[x]\leq key_{2}[x]\leq ...\leq key_{n[x]}[x]\leq c_{n[x]+1}[x]$
Tutte le foglie hanno la stessa profondità (l'albero ècompletamente bilanciato)
Il numero di chiavi per nodo è limitato superiormente ed inferiormente. $t\geq 2$ è il grado minimo dell'albero
- Ogni nodo contiene almeno $t-1$ chiavi
- Ogni nodo contiene al massimo $2t-1$ chiavi

Vantaggi dei B-Alberi

[modifica |modifica wikitesto]

I B-Alberi portano forti vantaggi in termini di velocità ed efficienza rispetto ad implementazioni alternative quando la maggior parte dei nodi si trovano 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.Offrono ottime prestazioni per quanto riguarda sia le operazioni di ricerca che quelle di aggiornamento, poiché entrambe possono avvenire con complessità logaritmica e attraverso l'utilizzo di procedure alquanto semplici. Su di essi è anche possibile effettuare elaborazioni di tipo sequenziale dell'archivio primario senza alcuna necessità di sottoporlo a riorganizzazione.

Struttura del nodo

[modifica |modifica wikitesto]

Si indica con $R {\displaystyle R}$ l'ordine dell'albero. È qui esposta una semplificazione della struttura nodo per un albero B-Tree implementata in C++.

structbNode{intnChiavi;//livello di riempimento del nodobNode*RifPagina[2*R+1];//vettore di puntatori ai nodi figlitipoChiaveK[2*R];//vettore ordinato di 2*R chiavi;longRifInfo[2*R];//vettore di puntatori a informazioni su archivio};

Altezza di un B-Albero

[modifica |modifica wikitesto]

Supponendo che il numero di chiavi di un B-Albero sia pari ad $n {\displaystyle n}$ e il suo grado minimo sia $t\geq 2$ , l'altezza $h {\displaystyle h}$ , nel caso peggiore, sarà

$h\leq \log _{t}{n+1 \over 2}$

Del resto, se un B-Albero ha altezza $h {\displaystyle h}$ , risulta evidente che il numero dei suoi nodi è minimo se la radice contiene una chiave e tutti gli altri nodi contengono $t-1$ chiavi: si avranno, così, $2 {\displaystyle 2}$ nodi a profondità 1, $2t$ nodi a profondità 2, $2t^{2}$ a profondità 3 e così via. Fissata $h {\displaystyle h}$ l'altezza del B-Albero si avrà che alla profondità h vi saranno $2t^{h}-1$ nodi. Quindi il numero di chiavi sarà

$n\geq 1+2(t-1)\sum _{i=1}^{h}t^{i-1}=2t^{h}-1$

Creazione di un B-Albero

[modifica |modifica wikitesto]

L'operazione di creazione di un B-Albero (inizialmente senza chiavi) richiede solo la creazione di un nodo radice.

B-Tree-Create(T) alloca un nuovo nodo x n[x] ← 0 leaf[x] ← TRUE scrivi su disco il nodo x root[T] ← x

Operazioni principali

[modifica |modifica wikitesto]

Sono qui di seguito trattate le tre operazioni fondamentali eseguibili su un B-Tree:

Ricerca di una chiave
Inserimento di una chiave (necessita dell'operazione di splitting del nodo)
Cancellazione (necessita dell'operazione di merging dei nodi)

Ricerca

[modifica |modifica wikitesto]

La ricerca di un record di chiavek è svolta in modo analogo all'albero binario, con l'unica differenza che, ad ogni passo, le possibili scelte non sono due ma coincidono con il numero di chiavi di ciascun nodo. Posto $n[x]$ il numero di chiavi di un generico nodo $x {\displaystyle x}$ del B-Albero, avremo che ad ogni nodo interno $x {\displaystyle x}$ si presenteranno $n[x]+1$ scelte alternative.

Ricerca di una chiave

La procedura di ricerca si suddivide nei seguenti passi:

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.

La proceduraB-Tree-Search(x,k) effettua la ricerca di una chiave $k {\displaystyle k}$ del B-Albero a partire da un nodo $x {\displaystyle x}$ .

B-Tree-Search(x,k) i ← 1 while i <= n[x] && k > key_i[x] do   i ← i+1 if i <= n[x] && k = key_i[x] then   return (x,i) if leaf[x] then   returnNIL else   leggi dal disco il nodo c_i[x]   return B-Tree-Search(c_i[x],k)

Poiché nella procedura di ricerca il B-Albero viene percorso lungo un cammino dalla radice ad una foglia, il numero di accessi al disco è pari a $\Omega (h)=\Omega (\log _{t}n)$ . Inoltre $n[x]<2t$ , quindi il tempo di esecuzione dell'algoritmo è, banalmente, $O(th)=O(t\log _{t}n)$ .

Inserimento

[modifica |modifica wikitesto]

L'inserimento di una nuova chiave può presentare più difficoltà rispetto alla medesima procedura per unalbero binario in quanto è fondamentale mantenere l'albero bilanciato. Operazione preliminare, che deve essere opportunamente implementata, per poter realizzare una funzione per l'inserimento di una chiave in un B-Albero è l'operazione di divisione di un nodo pieno. Un nodo di un B-Albero si definiscepieno se contiene esattamente $2t-1$ chiavi: essendo pieno, in fase di inserimento di una chiave, essa non può, per la definizione stessa di B-Albero, essere eventualmente inserita all'interno di esso. L'operazione di divisione viene effettuata in corrispondenza della chiave mediana $key_{t}[y]$ del nodo $y {\displaystyle y}$ pieno. Successivamente alla divisione, il nodo pieno $y {\displaystyle y}$ viene suddiviso in due nodi differenti ciascuno con $t-1$ chiavi. In concreto, la chiave mediana del nodo $y {\displaystyle y}$ viene spostata nel padre del nodo $y {\displaystyle y}$ (non pieno). L'operazione di divisione di un nodo, chiaramente, aumenta l'altezza dell'albero.

B-Tree-Split-Child(x,i,y) alloca il nodo z leaf[z] ← leaf[y] n[z] ← t-1 for j ← 1 to t-1do key_j[z] ← key_j+t[y] if not leaf[y]then for j ← 1 to t do c_j[z] ← c_j+t[y] n[y] ← t-1 for j ← n[x]+1 downto i+1do c_j+1[x] ← c_j[x] c_i+1[x] ← z for j ← n[x] downto ido key_j+1[x] ← key_j[x] key_i[x] ← key_t[y] n[x] ← n[x]+1 scrivi su disco i nodi y,z,x

L'operazione di inserimento di una chiave viene realizzata grazie ad una visita dell'albero che, sfruttando la procedura di splitting del nodo, evita che essa venga inserita in un nodo già pieno. Al primo passo della procedura di inserimento si verifica se la radice del B-Albero sia piena: in tal caso essa viene divisa all'altezza della chiave mediana; quest'ultima diverrà l'unica chiave di un nuovo nodo radice; a questo punto si può effettuare la procedura vera e propria di inserimento mediante un'apposita funzione ricorsiva che si occupa di inserire la chiave nella posizione corretta. Nel caso in cui la radice dell'albero, invece, non sia piena si può procedere direttamente con l'inserimento. A tal scopo si possono implementare due procedure:B-Tree-Insert che si occupa di verificare se la radice sia piena o meno eB-Tree-Insert-Nonfull che si occupa di effettuare la visita ricorsiva dell'albero per inserire la chiave nella corretta corrispondenza. Quest'ultima procedura viene invocata comunque dalla prima procedura, ma se la radice è piena viene preliminarmente effettuato il suo split. Si supponga di voler inserire una chiave $k {\displaystyle k}$ in un B-Albero $T {\displaystyle T}$ .

B-Tree-Insert(T,k) //se la radice è piena if n[r] = 2t-1then alloca un nodo s root[t] ← s //il nodo s sarà la nuova radice leaf[s] ← FALSE n[s] ← 0 c₁[s] ← r //splitting del nodo r (precedentemente era la radice) B-Tree-Split-Child(s,1,r) //chiamata alla procedura ricorsiva di inserimento a partire da s B-Tree-Insert-Nonfull(s,k)//se la radice non è pienaelse //chiamata alla procedura ricorsiva di inserimento a partire da r B-Tree-Insert-Nonfull(r,k)

La proceduraB-Tree-Insert-Nonfull inserisce la chiave $k {\displaystyle k}$ in un nodo $x {\displaystyle x}$ non pieno del B-Albero.

 B-Tree-Insert-Nonfull(x,k)//se il nodo x è una fogliaif leaf[x] then  //si scorrono le chiavi di x per trovare la posizione corretta per k  while i >= 1 && k < key_i[x] do  key_i+1[x] ← key_i[x]  i ← i-1  //inserimento della chiave  key_i+1[x] ← k  //aggiornamento del campo n[x]  n[x] ← n[x]+1  scrivi su disco il nodo x //se il nodo x non è una foglia occorre determinare in quale //sottoalbero procedere ricorsivamente a seconda del valore di k else  while i >= 1 && k < key_i[x] do  i ← i-1  i ← i+1  //il nodo è stato trovato  leggi dal disco il nodo c_i[x]  //se il nodo è pieno  if n[c_i[x]] = 2t-1 //splitting del nodo then B-Tree-Split-Child(x,i,c_i[x])  if k > key_i[x]then  i ← i+1  //se il nodo non è pieno o è già stato diviso si può  //procedere ricorsivamente con la visita  B-Tree-Insert-Nonfull(c_i[x],k)

La complessità dell'algoritmo di inserimento in un B-Albero va valutata in funzione del numero di accessi al disco sia per la lettura dei nodi che per la scrittura. Supponendo che l'altezza del B-Albero sia $h {\displaystyle h}$ la proceduraB-Tree-Insert effettua $O(h)$ accessi al disco. Il tempo di esecuzione è pari a $O(th)=O(t\log _{t}n)$ .

Cancellazione

[modifica |modifica wikitesto]

Il procedimento relativo alla cancellazione di una chiave è inverso rispetto a quello per l'inserimento. Si supponga di dover eliminare una chiave $k {\displaystyle k}$ da un sottoalbero con radice $x {\displaystyle x}$ : in questo caso una procedura di cancellazione viene chiamata ricorsivamente sul nodo $x {\displaystyle x}$ solo se il numero di chiavi di $x {\displaystyle x}$ è pari al grado minimo del B-Albero $t {\displaystyle t}$ . I casi che si possono riscontrare quando si vuole cancellare una chiave da un B-Albero sono svariati.

Se la chiave $k {\displaystyle k}$ si trova nel nodo $x {\displaystyle x}$ ed $x {\displaystyle x}$ è una foglia allora è sufficiente eliminare la chiave $k {\displaystyle k}$ senza ulteriori operazioni (caso banale).
Se la chiave $k {\displaystyle k}$ si trova in un nodo interno $x {\displaystyle x}$ allora la procedura è più complessa. Si presentano tre sottocasi differenti (di cui due simmetrici).
- Sia $y {\displaystyle y}$ il figlio di $x {\displaystyle x}$ cheprecede $k {\displaystyle k}$ ; se $y {\displaystyle y}$ ha almeno $t {\displaystyle t}$ chiavi è necessario trovare ilpredecessore di $k {\displaystyle k}$ nel sottoalbero che ha come radice $y {\displaystyle y}$ ; trovato quest'ultimo e indicato con $k^{'}$ esso si cancella e successivamente si sostituisce $k {\displaystyle k}$ con $k^{'} {\displaystyle k'}$ in $x {\displaystyle x}$ .
- Caso simmetrico al precedente. Sia $z {\displaystyle z}$ il figlio di $x {\displaystyle x}$ chesegue $k {\displaystyle k}$ ; se $z {\displaystyle z}$ ha almeno $t {\displaystyle t}$ chiavi è necessario trovare ilsuccessore di $k {\displaystyle k}$ nel sottoalbero che ha come radice $z {\displaystyle z}$ ; trovato quest'ultimo e indicato con $k^{'}$ esso si cancella e successivamente si sostituisce $k {\displaystyle k}$ con $k^{'} {\displaystyle k'}$ in $x {\displaystyle x}$ .
- Siano $y {\displaystyle y}$ e $z {\displaystyle z}$ rispettivamente i figli cheprecedono esuccedono $k {\displaystyle k}$ e si supponga che abbiano $t-1$ chiavi. Allora si devono inserire nel nodo $y {\displaystyle y}$ sia la chiave $k {\displaystyle k}$ che tutte le chiavi di $z {\displaystyle z}$ ; in questo caso i figli di $z {\displaystyle z}$ divengono figli di $y {\displaystyle y}$ . Tuttavia il nodo $x {\displaystyle x}$ perde $k {\displaystyle k}$ e il puntatore a $z {\displaystyle z}$ e il nodo $y {\displaystyle y}$ diviene pieno. Quindi si deve necessariamente procedere ricorsivamente ad eliminare $k {\displaystyle k}$ da $y {\displaystyle y}$ .
Se $k {\displaystyle k}$ non è presente in $x {\displaystyle x}$ allora si determina la radice $c_{i}[x]$ del sottoalbero che contiene $k {\displaystyle k}$ . Si presentano due sottocasi.
- Se $c_{i}[x]$ ha $t-1$ chiavi ed un nodo fratello con $t {\displaystyle t}$ chiavi allora a $c_{i}[x]$ una chiave del padre di $x {\displaystyle x}$ e poi si prende una chiave o del fratello di destra o del fratello di sinistra di $c_{i}[x]$ . Successivamente si sposta il figlio opportuno dal fratello e si inserisce in $c_{i}[x]$ .
- Se $c_{i}[x]$ e i suoi fratelli hanno $t-1$ si fonde $c_{i}$ con uno dei suoi fratelli. Una chiave di $x {\displaystyle x}$ scenderà nel nuovo nodo divenendone mediana.

La complessità dell'algoritmo di cancellazione in termini di accesso al disco è pari a $O(h)$ mentre la complessità temporale è $O(th)=O(t\log _{t}n)$ .

Varianti del B-tree

[modifica |modifica wikitesto]

Esistono diverse varianti al B-tree. Le tre più diffuse sono:

Il B+tree
Il B*tree
Il prefix B-tree
Il predictive B+tree

B+tree

[modifica |modifica wikitesto]

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. Tale collegamento consente di svolgere in maniera efficiente anche interrogazioni su un intervallo di valori ammissibili. 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.

Questo tipo di struttura trova applicazione neifile system Journaled File System,HPFS,Be File System,ReFS,ReiserFS eXFS.

B*tree

[modifica |modifica wikitesto]

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 neifile system Reiser4,HFS,HFS Plus eBtrfs.

Prefix B-tree

[modifica |modifica wikitesto]

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.

Predictive B+ tree

[modifica |modifica wikitesto]

Lo stesso argomento in dettaglio:Predictive B+ tree.

Bibliografia

[modifica |modifica wikitesto]

Renato Conte,Il Mondo Degli Oggetti Vol. 2
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,Introduzione agli algoritmi. Jackson Libri, 2003,ISBN 88-256-1421-7.

Voci correlate

[modifica |modifica wikitesto]

Altri progetti

[modifica |modifica wikitesto]

Altri progetti

Wikimedia Commons

Wikimedia Commons contiene immagini o altri file sulB-albero

Collegamenti esterni

[modifica |modifica wikitesto]

(EN) Eric W. Weisstein,B-Tree, suMathWorld, Wolfram Research.
Semaphore Corporation - B-tree algorithms, susemaphorecorp.com.URL consultato il 18 marzo 2006(archiviato dall'url originale il 15 marzo 2006).
Peter Neubauer - Balanced Tree Data Structures, subluerwhite.org.URL consultato il 18 marzo 2006(archiviato dall'url originale il 5 marzo 2010).

V · D · M Strutture dati
Tipi	Collezione ·Container
Astratte	Array associativo (Multimap) ·Lista ·Pila ·Coda (Deque) ·Coda di priorità ·Set (Multiset ·Mfset)
Array	Bit array ·Buffer circolare ·Array dinamico ·Hash table ·Array sparso
Collegate	Lista di associazioni ·Lista concatenata ·Skip list ·Unrolled linked list ·Lista concatenata tramite XOR
Alberi	B-albero ·Albero binario di ricerca (Albero AA ·Albero AVL ·RB-Albero ·Albero binario di ricerca bilanciato ·Albero splay) ·Heap (Heap binario ·Heap binomiale ·Heap di Fibonacci) ·Albero di Merkle ·Albero SPQR ·Albero PQ ·Albero indicizzato binario
Grafi	Diagramma binario di decisione ·Digrafo aciclico ·Automa a stati finiti deterministico aciclico
Alberi di partizionamento dei dati spaziali	Albero quadramentale ·M-tree ·R-tree (R* tree ·R+ tree) ·X-tree
Lista di strutture dati

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

Estratto da "https://it.wikipedia.org/w/index.php?title=B-albero&oldid=140852011"

Alberi di ricerca

Categorie nascoste:

[8]ページ先頭

©2009-2025 Movatter.jp